윌슨의 정리 소수 판별기

p가 2 이상의 정수일 때, (p-1)!을 p로 나눈 나머지가 정확히 p-1(즉 -1과 합동)이면 그리고 오직 그럴 때만 p가 소수라는 정리입니다. 예를 들어 5는 소수이고 (5-1)!=24를 5로 나누면 나머지가 4(=5-1)입니다.

소수면 반드시 이 식이 성립하고, 이 식이 성립하면 반드시 소수라는 뜻입니다. 페르마의 소정리 같은 다른 판별법은 소수면 성립하는 것은 맞지만, 성립한다고 반드시 소수인 것은 아닙니다(카마이클 수가 그 예외입니다). 윌슨의 정리는 예외가 없는 완벽한 판별법입니다.

계승 (p-1)!을 계산하려면 p번의 곱셈이 필요합니다. 반면 시행나눗셈은 √p번의 나눗셈만으로 충분합니다. p가 100만이면 윌슨의 정리는 100만 번, 시행나눗셈은 1000번 정도만 계산하면 되니 속도 차이가 극심합니다. 이론적으로 아름다운 것과 실용적인 것은 다른 문제라는 좋은 예시입니다.

매 곱셈마다 p로 나눈 나머지만 남기며 계산하기 때문에(모듈러 계승) 중간값이 항상 0부터 p-1 사이로 유지됩니다. 계승 자체를 다 계산한 뒤 나누는 것이 아닙니다.