윌슨의 정리

대수학과 정수론에서 윌슨의 정리는 자연수 n > 1이 n보다 작은 모든 양의 정수의 곱이 n의 배수보다 1보다 작은 경우에만 소수라는 것을 말합니다.즉, (모듈러 산술의 표기법을 사용하여), 계승 $({\displaystyle n}$- ${\displaystyle 1)!}$= ${\displaystyle 1}$ × ${\displaystyle 2\mathrm{}}$× ${\displaystyle 3}$× ⋯ × (n - $1$) ${\displaystyle ($n-1)!$=1\times$ 2\times 3\times \cdots \times (n-1)} 만족

${\displaystyle (n-1)!\ \equiv \;-1{\pmod {n}}$

정확하게 n이 소수일 때.즉, 임의의 숫자 n은 만약에 그리고 오직, (n - 1)! + 1이 n으로 나뉠 때만 소수입니다.^[1]

역사

이 정리는 Ibn al-Haytham (서기 1000년경)에 의해 기술되었고,^[2] 18세기에 영국 수학자 John Wilson에 의해 기술되었습니다.^[3]에드워드 워링은 1770년에 이 정리를 발표했지만, 그나 그의 학생 윌슨은 증명할 수 없었습니다.라그랑주는 1771년에 최초의 증거를 제시했습니다.^[4]라이프니츠도 한 세기 전에 그 결과를 알고 있었다는 증거가 있지만, 그는 그것을 출판하지 않았습니다.^[5]

예

2부터 30까지의 n 값 각각에 대해 다음 표는 수 (n - 1)!을 나타내고, (n - 1)!을 n으로 나누었을 때의 나머지를 나타냅니다. (모듈러 산술 표기법에서는 m을 n으로 나누었을 때의 나머지를 m mod n으로 씁니다.)배경색은 prime 값이 n이면 파란색, composite 값이 gold입니다.

요인 및 나머지 모듈의 표

${\displaystyle n}$	${\displaystyle (n-1)!}$ (OEIS의 시퀀스 A000142)	${\displaystyle (n-1)!\ {\bmod {\}}n}$ (OEIS의 시퀀스 A061006)
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
16	1307674368000	0
17	20922789888000	16
18	355687428096000	0
19	6402373705728000	18
20	121645100408832000	0
21	2432902008176640000	0
22	51090942171709440000	0
23	1124000727777607680000	22
24	25852016738884976640000	0
25	620448401733239439360000	0
26	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30	8841761993739701954543616000000	0

프루프

아래의 증명들(소모수의 경우)은 잔차 클래스 모듈로 소수가 유한한 필드라는 사실을 사용합니다. 자세한 내용은 프라임 필드 기사를 참조하십시오.^[6]라그랑주의 정리는 모든 증명에 대해 n차 다항식이 최대 n차근을 갖는다는 것을 의미합니다.

합성계수

만약 n이 합성이면 그것은 어떤 소수 q로 나뉠 수 있는데, 여기서 2 ≤ q ≤ n - 2.$q$ ${\displaystyle$q}이$($$가$) n ${\displaystyle$ n}을$($를) 분할하므로 일부$$정수 $k$ ${\displaystyle$ k}에 대해 n = ${\displaystyle q}$ ${\displaystyle k}$ {\$displaystyle$ n=$qk$}이라고 합니다.$$모순을 위해 (n$$-${\displaystyle 1}$ ${\displaystyle )!}$ ${\displaystyle$ ($n-1)!$$}$n이 합성인 -1 (modn)과 일치했습니다$$.그러면 (n-1)! ${\displaystyle \mathrm{또한}}$(${\displaystyle \mathrm{n-1})!}$≡ - ${\displaystyle 1}$ ($mod$n ) ${\displaystyle ($n-1)!$\equiv -1\({\text{mod}}\n)}$은$($는)${\displaystyle }$!${\displaystyle }$$=$ ${\displaystyle n\mathrm{m}}$- 1 $=$ (${\displaystyle q}$ k${\displaystyle }$) m$$- 1 $=$ (k m ) - 1 {\displaystyle (n-1)!$일부$ 정수 m {\$displaystyle$ m$}$의 $경우$ $=$nm-1$=(qk)m-1=$q(km)-$1}$이며, 이는 (n-1)!이 -1(mod q)과 일치함을 나타냅니다.하지만 (n - 1)!≡ 0 (mod q) q가 (n-1)! 만들기 (n-1)!의 q의 배수라는 사실에 의해 이제 모순에 도달합니다.

사실 더 많은 것이 사실입니다.단 4를 제외하고, 여기서 3! = 6 ≡ 2 (mod 4), 만약 n이 합성이면 (n - 1)!은 0 (mod n)에 해당합니다.증명은 두 가지 경우로 나뉩니다.먼저, n을 2 ≤ a < b ≤ n - 2인 n = ab의 곱으로 나눌 수 있다면, a와 b는 둘 다 곱 1 × 2 × ... × (n - 1) = (n - 1)!와 (n - 1)!에서 n으로 나뉠 것입니다.만약 n이 그러한 인수분해를 가지지 않는다면, 그것은 어떤 소수 q, q > 2의 제곱이어야 합니다. 그러나 2q < q = n, q와 2q는 모두 (n - 1)!의 인수가 되고, 다시 (n - 1)!의 분할이 됩니다.

소수 계수

기초 증명

p = 2일 때 결과는 사소한 것이므로 p를 홀수 소수, p ≥ 3이라고 가정합니다.잔차 클래스(mod p)는 필드이므로 0이 아닌 모든 a는 고유한 곱셈 역수 a를 갖습니다. 라그랑주 정리는 ≡ a (mod p)가 되는 a의 유일한 값은 ≡ ±1 (mod p)임을 암시합니다 (왜냐하면 ≡ 1이 최대 2개의 근(mod p)을 가질 수 있기 때문입니다).따라서 ±1을 제외하고 (p - 1)!의 인자를 각 쌍의 곱이 1개의 모듈로프와 일치하도록 서로소인 쌍으로 배열할 수 있습니다.이것은 윌슨의 정리를 증명합니다.

예를 들어 p = 11의 경우 다음과 같습니다.

페르마의 작은 정리를 이용한 증명

다시 말하지만 p = 2의 경우 결과는 사소한 것이므로 p가 홀수 소수, p ≥ 3이라고 가정합니다.다항식을 고려합니다.

${\displaystyle g(x)=(x-1)(x-1)(x-1)\cdots(x-1)).}$

g는 차수 p - 1, 선도항 x^{p − 1}, 상수항 (p - 1)!그것의 p - 1 근은 1, 2, ..., p - 1입니다.

이제 생각해보세요.

${\displaystyle h(x)=x^{p-1}-1.}$

h는 또한 차수 p - 1과 선도항 x를^{p − 1} 갖습니다. 모듈로프, 페르마의 작은 정리는 그것이 또한 같은 p - 1 근, 1, 2, ..., p - 1을 갖는다고 말합니다.

마지막으로 생각해보세요.

${\displaystyle f(x)=g(x)-h(x)}$

f 는 최대 p - 2 의 차수를 가지며(선행 항들이 취소되므로), modulop 또한 p - 1 의 근 1, 2, ..., p - 1 을 갖습니다. 그러나 라그랑주 정리에 따르면 p - 2 의 근을 초과할 수 없습니다.따라서 f는 동일하게 0(modp)이어야 하므로 상수항은 (p - 1)! + 1 ≡ 0(modp)입니다.이것이 윌슨의 정리입니다.

Sylow 정리를 사용한 증명

윌슨의 정리는 실로우 정리의 특정한 적용으로부터 추론하는 것이 가능합니다.최고가 되게 해주세요.대칭군 ${\displaystyle {Sp}_{}}$ ${\$이(${\displaystyle 가)}$ 정확히 (${\displaystyle \mathrm{p}}$- 1$)!$ {\$displaystyle$ ($p-1)!$임을 즉시 추론할 수 있습니다.$}$ elements of order p, namely the p-cycles ${\displaystyle C_{p}}$. On the other hand, each Sylow p-subgroup in ${\displaystyle S_{p}}$ is a copy of ${\displaystyle C_{p}}$. Hence it follows that the number of Sylow p-subgroups is ${\displaystyle n_{p}=(p-2)!}$. The third Sylow theorem implies

${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$

양변에 (p - 1)을 곱하면 다음을 얻을 수 있습니다.

${\displaystyle (p-1)!\equiv p-1\equiv -1{\pmod {p}},}$

즉, 결과입니다.

적용들

원시성 검정

실제로 윌슨의 정리는 큰 n에 대한 (n - 1)! 모듈론을 계산하는 것이 계산적으로 복잡하고 훨씬 빠른 원시성 테스트가 알려져 있기 때문에 원시성 테스트로는 쓸모가 없습니다(실제로 시도 분할도 훨씬 더 효율적입니다).^{[citation needed]}

다른 방향으로 사용하면 큰 요인의 계승자의 소수점을 결정하기 위해 매우 빠르고 효과적인 방법입니다.그러나 이것은 제한된 효용입니다.^{[citation needed]}

2차 잔기

윌슨 정리를 사용하여 임의의 홀수 소수 p = 2m + 1에 대하여, 우리는 왼쪽의 를 재정렬할 수 있습니다.

평등을 얻다이것은아니면p ≡ 1(mod 4)이 제곱(2차 잔차) mod p인 소수 p에 대해 이 사실을 사용하여 유명한 결과의 일부를 증명할 수 있습니다.이 경우 일부 정수 k에 대해 p = 4k + 1이라고 가정합니다.그러면 위의 m = 2k를 취할 수 있고, (m!)이 (-1)(modp)와 일치한다고 결론지을 수 있습니다.

소수에 대한 공식

윌슨의 정리는 소수에 대한 공식을 구성하는 데 사용되어 왔지만, 그것들은 너무 느려서 실용적인 가치를 가질 수 없습니다.

p-adic 감마 함수

윌슨의 정리는 p-adic 감마 함수를 정의할 수 있게 해줍니다.

가우스의 일반화

가우스는 다음을 증명했습니다^{[7][non-primary source needed]}.

여기서 p는 홀수 소수를 나타내고 $\alpha {\displaystyle }$ ${\displaystyle \alpha$}는$$양의$$ 정수를 나타냅니다.즉, m보다 작고 상대적으로 소수인 양의 정수의 곱은 m이 4일 때 m의 배수 미만이거나, 홀수 소수의 거듭제곱 또는 홀수 소수의 거듭제곱의 2배입니다.곱이 -1인 m의 값은 정확히 원시근 모듈이 있는 값입니다.

참고 항목

• 윌슨 프라임
• 합동표

메모들

참고문헌

외부 링크

• "Wilson theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Wilson's Theorem". MathWorld.
• Mizar 시스템 증명 : http://mizar.org/version/current/html/nat_5.html#T22
• Ohana, Andrew. "A Generalization of Wilson's Theorem" (PDF).