윌슨의 정리

정수론의 정리 중 하나로 팩토리얼 값의 나머지를 알 수 있다

윌슨의 정리(영어: Wilson's Theorem)는 1 보다 큰 자연수 에 대해서

위 명제가 성립함은 소수필요충분조건이라는 정수론의 정리이다.

즉, 자연수 에 대해 다음 두 명제가 성립한다:

  • 가 소수이면
  • 가 성립하면 는 소수

증명

편집

필요조건의 증명

편집

만약  가 소수이면,  의 기약잉여계   에 대한 가환환을 이룬다.

이것은  의 임의의 원소  에 대하여,  이 성립하는 역원  가 존재한다는 것이다.

만약  이면,

 

이와 같이   만이 자기 자신을 곱의 역원으로 가지고, 나머지 원소들은 자신이 아닌 다른 원소를 역원으로 갖는다.

따라서,   을 제외한 원소들을 모두 곱하면 법  에 대해 1과 합동이 되고,  의 원소들을 모두 곱한 값, 즉  의 값은 −1과 합동이 된다.

예를 들어,   인 경우:

 

로 성립하며,  인 경우  가 된다.

  (단,  는 소수들의 집합)

충분조건의 증명

편집

  합성수 가 존재한다고 가정하자.

 가 합성수이면   의 약수  를 잡을 수 있다.

  1.  이며  이므로  
  2.  이므로  

즉,    의 공약수인데,

이는   는 서로소임에 모순된다.

따라서 귀류법을 통해 조건을 만족하는  는 모두 소수임을 알 수 있다.

  (단,  는 소수들의 집합)

따름 정리

편집

임의의 소수  에 대해