정수론 4대 정리는 다음과 같다.

  1. 페르마 정리
  2. 중국인의 나머지 정리
  3. 윌슨의 정리
  4. 오일러 정리

그 중 하나인 윌슨의 정리에 대해 정리해보자.

윌슨의 정리Permalink

Theorem 5.4 윌슨의 정리Permalink

pp가 소수이면 (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod p

증명

p=2,p=3p=2, p=3 인 경우는 분명하므로 p>3p>3 이라 하자.

aa를 p−1p-1 개의 양의 정수 1,2,3,…,p−11,2,3,\dots,p-1 중 하나라 가정하고, ax≡1(modp)ax \equiv 1 \pmod p 를 생각하자.

gcd(a,p)=1gcd(a,p)=1 이므로 Theorem 4.7에 의해 유일한 해가 존재한다.

xx는 aa의 법 pp에 대한 모듈러 역원이다.

pp가 소수이므로 a2≡1(modp)a^2 \equiv 1 \pmod p 일 때의 필요충분조건은 a=1a=1 혹은 a=p−1a=p-1 이다.

11과 p−1p-1를 제외하면, 2,3,…,p−22,3,\dots,p-2 는 a≠xa \ne x 이고 그들의 곱 ax≡1(modp)ax \equiv 1 \pmod p 인 쌍 aa와 xx를 짝지을 수 있다.

이러한 (p−3)/2(p-3)/2 개의 합동식을 서로 곱하고 약수를 재배열하자.

2⋅3⋯(p−2)≡1(modp)(p−2)!≡1(modp) \begin{gathered} 2 \cdot 3 \cdots (p-2) \equiv 1 \pmod p\\ (p-2)! \equiv 1 \pmod p \end{gathered}

이제 양변에 p−1p-1 를 곱하면,

(p−1)!≡p−1(modp)↓(p−1)!≡−1(modp) \begin{gathered} (p-1)! \equiv p-1 \pmod p\\ \downarrow\\ (p-1)! \equiv -1 \pmod p \end{gathered}

□\square

예시를 보자.

p=13p=13 일 때, 1⋅1≡1(mod13)1 \cdot 1 \equiv 1 \pmod {13}과 12⋅12≡1(mod13)12 \cdot 12 \equiv 1 \pmod {13} 를 논외로 하고,

2⋅7≡1(mod13)3⋅9≡1(mod13)4⋅10≡1(mod13)5⋅8≡1(mod13)6⋅11≡1(mod13) \begin{gathered} 2 \cdot 7 \equiv 1 \pmod {13}\\ 3 \cdot 9 \equiv 1 \pmod {13}\\ 4 \cdot 10 \equiv 1 \pmod {13}\\ 5 \cdot 8 \equiv 1 \pmod {13}\\ 6 \cdot 11 \equiv 1 \pmod {13} \end{gathered}

의 양변을 모두 곱하자.

11!≡1(mod13)12!≡12≡−1(mod13)∴12!≡−1(mod13) \begin{aligned} 11! &\equiv 1 \pmod {13} \\ 12! &\equiv 12 \equiv -1 \pmod {13}\\ \therefore 12! &\equiv -1 \pmod {13} \end{aligned}

윌슨의 정리의 역Permalink

윌슨의 정리는 역도 참이다.

즉, (p−1)!≡1(modp)(p-1)! \equiv 1 \pmod p 이면, pp는 소수이다.

증명

(n−1)!≡−1(modn)(n-1)! \equiv -1 \pmod n 이면, nn은 소수이다.

nn이 소수가 아니라고 가정하면,

$$ n=ds(1 < d \le s

이라 하자.

d∣nd \mid n이므로 (n−1)!≡−1(modd)(n-1)! \equiv -1 \pmod d 도 성립해야 한다.

그런데 d∣(n−1)!d \mid (n-1)! 이므로 (n−1)!≡0≡−1(modd)(n-1)! \equiv 0 \equiv -1 \pmod d 가 된다.

d∣1d \mid 1 이 되고 d>1d > 1 이라 모순이다.

그러므로 nn은 소수이다. □\square

이차합동식과 윌슨의 정리Permalink

Theorem 5.5Permalink

홀수인 소수 pp에 대해 이차 합동식 x2+1≡0(modp)x^2+1 \equiv 0 \pmod p 가 해를 가질 조건은 p≡1(mod4)p \equiv 1 \pmod 4 이다.

이는 역도 성립한다.

증명

aa를 x2+1≡0(modp)x^2+1 \equiv 0 \pmod p의 임의의 해라고 하면, a2≡−1(modp)a^2 \equiv -1 \pmod p

p∤ap \nmid a 이므로 페르마의 정리에 의해

1≡ap−1≡(a2)(p−1)/2≡(−1)(p−1)/2(modp) \begin{aligned} 1 \equiv a^{p-1} \equiv (a^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \pmod p \end{aligned}

따라서 p=4k+3p=4k+3 형태는 불가능하다. 그렇지 않다면,

(−1)(4k+2)/2=(−1)2k+1=−1(-1)^{(4k+2)/2} = (-1)^{2k+1} = -1 이기 때문에,

1≡−1(modp)1 \equiv -1 \pmod p 가 되어 모순이다.

따라서 pp는 4k+14k+1의 형태를 갖는다.

역 증명

p≡1(mod4)⟹x2+1≡0(modp)p \equiv 1 \pmod 4 \Longrightarrow x^2+1 \equiv 0 \pmod p 가 해를 가진다.

를 증명해보자.

다음과 같은 곱을 보자.

(p−1)!≡1⋅2⋯(p−1)/2⋅(p+1)/2⋯(p−1)p−1≡−1(modp)p−2≡−2(modp)⋮(p+1)/2≡−(p−1)/2(modp) \begin{aligned} (p-1)! &\equiv 1 \cdot 2 \cdots (p-1)/2 \cdot (p+1)/2 \cdots (p-1)\\ p-1 &\equiv -1 \pmod p\\ p-2 &\equiv -2 \pmod p\\ \vdots\\ (p+1)/2 &\equiv -(p-1)/2 \pmod p \end{aligned}

인수를 재배열하여 (p−1)/2(p-1)/2 개의 음수가 포함되어 있어서

(p−1)!≡1⋅(−1)⋅2⋅(−2)⋯((p−1)/2)(−(p−1)/2)≡(−1)(p−1)/2[(p−12)!]2(modp) \begin{aligned} (p-1)! &\equiv 1 \cdot (-1) \cdot 2 \cdot (-2) \cdots \left((p-1)/2\right)\left( -(p-1)/2 \right)\\ &\equiv (-1)^{(p-1)/2}\left[ \left( \dfrac {p-1}2 \right)! \right]^2 \pmod p \end{aligned}

윌슨의 정리를 이용해 (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod p 이므로,

−1≡(−1)(p−1)/2[(p−12)!]2(modp) \begin{aligned} -1 \equiv (-1)^{(p-1)/2}\left[ \left( \dfrac {p-1}2 \right)! \right]^2 \pmod p \end{aligned}

p=4k+1p=4k+1 라고 가정하면,

−1≡[(p−12)!]2(modp) \begin{aligned} -1 \equiv \left[ \left( \dfrac {p-1}2\right)! \right]^2 \pmod p \end{aligned}

따라서 정수 ((p−1)/2)!((p-1)/2)! 이 x2+1≡0(modp)x^2 + 1 \equiv 0 \pmod p 를 만족하게 된다. □\square

Comments

You may also enjoy