위키득계정 ↗
과학

윌슨의 정리

윌슨의 정리과학
영문명
Wilson’s theorem
적용 범위
정수 n>1
소수의 필요충분조건
(n−1)!≡−1 (mod n)
계승의 뜻
1부터 n−1까지의 곱
윌슨의 정리는 1보다 큰 정수 n이 소수일 필요충분조건이 (n−1)!≡−1 (mod n)이라는 정리다. 계승에 1을 더한 값이 n의 배수인지로 표현할 수도 있다.

합동식의 해석

법 n에서 −1과 합동이라는 것은 표준 나머지가 n−1이라는 뜻이다. 따라서 (n−1)!을 n으로 나눈 나머지를 확인하거나 (n−1)!+1이 n으로 나누어떨어지는지 확인할 수 있다.

작은 수로 확인

n=7에서는 6!=720이고 721=7×103이므로 조건이 성립한다. 반면 n=6에서는 5!=120의 나머지가 0이어서 −1에 합동이 아니다. 소수 2도 1!+1=2이므로 정리의 범위에 들어간다.

필요충분조건

정수 n>1이 소수이면 합동식이 성립하고 합동식이 성립하면 n은 소수다. 특정 밑의 거듭제곱 조건을 통과한 합성수가 존재하는 페르마의 소정리와 구별되는 부분이다.

계산 방법과 판정식

논리적으로 정확한 판정 조건이라는 사실이 곧 큰 수에 대한 가장 빠른 계산법이라는 뜻은 아니다. 계승은 많은 인수의 곱이므로 실제 계산에서는 정수 전체를 만들지 않고 곱할 때마다 나머지를 취할 수 있다.

관련 문서

소수 (수론) / 합성수 / 계승 / 합동식 / 나머지 / 필요충분조건 / 페르마의 소정리 / 배수