윌슨의 정리

개요

윌슨의 정리(Wilson's theorem)는 존 윌슨이 추측하고 조제프루이 라그랑주가 1770년에 증명한 정수론의 정리이다.

진술

정수 [math]\displaystyle{ n\ge 2 }[/math]에 대해

[math]\displaystyle{ (n-1)! \equiv -1\pmod n }[/math]

일 필요충분조건은 [math]\displaystyle{ n }[/math]이 소수인 것이다.

작은 값에서 확인하기

[math]\displaystyle{ n }[/math]	[math]\displaystyle{ (n-1)! }[/math]	[math]\displaystyle{ (n-1)! }[/math]을 [math]\displaystyle{ n }[/math]으로 나눈 나머지	[math]\displaystyle{ n }[/math]은 소수인가?
2	1	1	예
3	2	2	예
4	6	2	아니오
5	24	4	예
6	120	0	아니오
7	720	6	예
8	5040	0	아니오
9	40320	0	아니오
10	362880	0	아니오
11	3628800	10	예
12	39916800	0	아니오
13	479001600	12	예
14	6227020800	0	아니오
15	87178291200	0	아니오

증명

• 도움정리 1: [math]\displaystyle{ \gcd\left(a,m\right)=1 }[/math]이면, [math]\displaystyle{ ax\equiv1\pmod m }[/math]을 만족하는 [math]\displaystyle{ x }[/math]가 법 [math]\displaystyle{ m }[/math]에 대해 유일하게 존재한다.
  • 증명은 디오판토스 방정식을 사용.
• 도움정리 2: [math]\displaystyle{ p }[/math]가 소수일 때, [math]\displaystyle{ a\equiv\bar{a}\pmod p }[/math]일 필요충분 조건은 [math]\displaystyle{ a^2\equiv1\pmod p }[/math]이고, 이는 곧 [math]\displaystyle{ a\equiv\pm1\pmod p }[/math]임과 동치이다.
  • 증명은 합동식의 정의와 나누어떨어짐의 성질을 이용한다.

[math]\displaystyle{ p }[/math]가 소수라 가정하자. [math]\displaystyle{ p=2,\,3 }[/math]일 때는 직접 [math]\displaystyle{ \left(p-1\right)!\equiv-1\pmod p }[/math]임을 쉽게 확인할 수 있다. [math]\displaystyle{ p\gt 3 }[/math]이면, [math]\displaystyle{ 1\leq a\leq p-1 }[/math]인 각 [math]\displaystyle{ a }[/math]에 대해, [math]\displaystyle{ \gcd\left(a,p\right)=1 }[/math]이므로 [math]\displaystyle{ a\bar{a}\equiv1\pmod p }[/math]인 [math]\displaystyle{ 1\leq\bar{a}\leq p-1 }[/math]가 각 [math]\displaystyle{ a }[/math]에 대해 유일하게 존재한다. 또한, [math]\displaystyle{ a\equiv\bar{a}\pmod p }[/math]인 경우는 [math]\displaystyle{ a\equiv1,\,p-1\pmod p }[/math]인 경우밖에 없다. 나머지 [math]\displaystyle{ 2\leq a\leq p-2 }[/math]인 [math]\displaystyle{ a }[/math]에 대해서는 각각의 역수와 묶을 수 있다 ([math]\displaystyle{ p\gt 3 }[/math]인 소수이므로 [math]\displaystyle{ p-1 }[/math]은 짝수라 이게 가능하다). 따라서, [math]\displaystyle{ \left(p-1\right)!\equiv1\cdot2\cdot\cdots\cdot\left(p-1\right)\equiv1\cdot\left(p-1\right)\cdot1\cdot\cdots\cdot1\equiv p-1\equiv-1\pmod p }[/math].

역으로, [math]\displaystyle{ n }[/math]이 합성수고 [math]\displaystyle{ \left(n-1\right)!\equiv-1\pmod n }[/math]이 성립한다 가정하자. [math]\displaystyle{ n }[/math]이 합성수이므로, 적당한 [math]\displaystyle{ 1\lt a,\,b\lt n }[/math]에 대해 [math]\displaystyle{ n=ab }[/math]이다. 따라서, [math]\displaystyle{ a\mid\left(n-1\right)! }[/math]이고, [math]\displaystyle{ a\mid n\mid\left(n-1\right)!+1 }[/math]이므로, [math]\displaystyle{ a\mid 1 }[/math]이다. 이는 모순이고, [math]\displaystyle{ n }[/math]은 합성수가 아니다. 주어진 가정에서 [math]\displaystyle{ n }[/math]은 1이 아니므로, 가능한 경우는 [math]\displaystyle{ n }[/math]이 소수일 경우 뿐이다.

따름정리

• [math]\displaystyle{ p }[/math]가 [math]\displaystyle{ 4k+1 }[/math] (단, [math]\displaystyle{ k }[/math]는 양의 정수) 꼴의 소수이면 [math]\displaystyle{ \left(\left(\frac{p-1}{2}\right)!\right)^2\equiv -1\pmod p }[/math]이다.
• [math]\displaystyle{ p }[/math]가 [math]\displaystyle{ 4k+3 }[/math] (단, [math]\displaystyle{ k }[/math]는 0 이상의 정수) 꼴의 소수라면 [math]\displaystyle{ \left(\frac{p-1}{2}\right)!\equiv \pm1\pmod p }[/math]이다.

확장

• [math]\displaystyle{ n }[/math]이 원시근을 가지는 정수라면, [math]\displaystyle{ n }[/math]보다 작고 [math]\displaystyle{ n }[/math]과 서로소인 정수의 곱은 법 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ -1 }[/math]과 합동이다.