[정수론] 윌슨의 정리 ( Wilson's Theorem)
Math/Numbers/Combinatorics2011. 1. 12. 10:18 |테스트부터 해보자.
p가 소수이면 A = {1 , 2 , ... , p-1 } 에 대하여, A 의 모든 원소들은 p 와 서로소이다.
A 의 각 원소들의 mod p 에 대한 역원을 찾아보자.
즉, A 의 원소 x 에 대해, x x' ≡ 1 ( mod p ) 인 x' 를 찾는것이다. ( 참고 : 선형 합동식 )
우선, x 는 A 의 원소이므로, p 와 서로소이다. 따라서, 임의의 x 에 대해, 역원 x' 은 항상 유일하게 존재한다.
역원은 당연히 0 일 수 없고, A는 0 아닌 모든 나머지를 포함하므로, x 에 대한 역원은 반드시 A 내에 들어있다.
(참고 : x 에서 x' 으로 가는 대응은 일대일이다. 다른 x 에 대해 같은 역원을 가질수 없음은 쉽게 보일수 있다. )
역원이 자기 자신이 되는 경우에는 다음과 같이 쓸 수 있다.
x 2 ≡ 1 ( mod p )
정의에 따라, p | x 2 -1 이고, 따라서, p | (x+1)(x-1) 인데, p 가 소수이므로, x-1 , x+1 과 모두 서로소이다.
따라서, p | x+1 이거나 p | x-1 이다. 즉, x ≡ 1 (mod p ) 이거나 x ≡ -1 (mod p )
A 내에 이를 만족하는 수는 각각 1 과 p-1 이다.
따라서, A에서 1 과 p-1을 제외시킨 집합 B = { 2 , 3 , ... , p-2 } 는 자신의 인버스와 짝을 지을 수있다.
( 참고 : p 는 5 이상이 가정되었기 때문에, A 는 짝수개의 원소를 갖고, 따라서, B 도 짝수개의 원소를 갖는다 .)
B 내에서 각각의 원소와 그 인버스를 짝지어서 곱하면, 정의에 의해 1 과 합동이므로, B 의 모든 원소를 곱한것은 1 과 합동이다.
따라서, 2 × 3 × ... × p-2 ≡ 1 (mod p) , 즉, 따라서 (p-2)! ≡ 1 (mod p)
여기서 양변에 p-1 을 곱하면... (p-1)! ≡ p-1 (mod p) 즉, (p-1)! ≡ -1 (mod p)
윌슨의 정리는 역이 성립한다. (증명은 생략) 즉, 어떤 a 에 대해, ( a-1 ) ! ≡ -1 (mod a ) 이면 a 는 소수이다.
따라서, 윌슨의 정리는 소수 판별에 사용할수 있다. 그러나 팩토리얼이 너무 빠르게 증가하는 탓에 좋은 판별법은 아니다.