정리

If p is prime and a is an integer not divisible by p, then
ap11(modp)
Furthermore, for every integer a we have
apa(modp)

  • p 가 소수이고 ap 로 나누어지지 않는 정수이면
    • ap11(modp) 이다.
  • 그리고, 모든 a 에 대하여
    • apa(modp) 이다.

계산 예제

7222mod11 을 계산하라.

7 보다 큰 소수 11 을 사용해 페르마의 소정리에 적용해보면 다음을 얻을 수 있다.

71111(mod11)7101(mod11)

이제 7222mod11을 단순하게 정리할 수 있다.

7222=722×10×72

따라서 답은 5 다.

7222122×72(mod11)49(mod11)5(mod11)

유사소수

pseudoprime

페르마의 소정리는 편리하지만 주의해야 할 점이 있다.

  • p 가 소수이면 페르마의 소정리를 만족한다.
    • 하지만 페르마의 소정리를 만족한다고 해서 p 가 반드시 소수인 것은 아니다.

즉, p 가 합성수인데도 ap11(modp) 를 통과하는 경우가 있다.

이런 합성수들을 유사소수라 부른다.

Let b be a positive integer. If n is a composite positive integer, and bn11(modn), then n is called a pseudoprime to the base b.

  • b 를 양의 정수라 하자.
  • n 이 양의 정수인 합성수이고, bn11(modn) 이면
    • nb를 밑수로 하는 유사소수라 부른다.

유사소수 예제

b=2일 때, 341 은 유사소수인가?

유사소수인지 확인하려면 두 조건을 체크하면 된다.

  1. 합성수인가?
  2. 다음 합동식이 참인지 확인하면 된다.
    • 234111(mod341).
    • 즉, 2340 을 341 로 나눈 나머지가 1 인지 확인하면 된다.

일단 341 은 합성수가 맞다. 341=11×31.

이제 2340을 341로 나누면 나머지가 1 이 나오는지를 확인하면 된다.

2340은 꽤 큰 수이기 때문에 나머지를 구하는 것은 까다로운 일이다.

그러나 페르마의 소정리를 활용하면 210을 11로 나눈 나머지가 1 이라는 사실을 쉽게 확인할 수 있고, 이를 이용해 2340mod341 을 쉽게 풀 수 있다.

21111(mod11)2101(mod11)

따라서 다음과 같이 확인할 수 있다.

234111(mod341)23401(mod341)(210)341(mod341)1341(mod341)11(mod341)

341 은 2를 밑수로 하는 유사소수이다.

카마이클 수

Carmichael number

A composite integer n that satisfies the congruence bn11(modn) for all positive integers b with gcd(b,n)=1 is called a Carmichael number. (These numbers are named after Robert Carmichael, who studied them in the early twentieth century.)

  • gcd(b,n)=1 인 모든 양의 정수 b 에 대하여,
    • bn11(modn)을 만족하는 합성수인 정수 n을 카마이클 수라 부른다.

카마이클 수 예제

561 은 카마이클 수인가?

카마이클 수인지 확인하려면 두 조건을 체크하면 된다.

  1. 합성수인가?
  2. gcd(b,n)인 모든 양의 정수 b에 대하여 b56111(mod561) 이 성립하는가?

일단 561 은 합성수가 맞다. 561=3×11×17.

이제 b5601(mod561) 을 확인하자.

561 의 소인수를 페르마의 소정리 ap11(modp) 에 넣어 다음과 같이 정리할 수 있다.

b21(mod3)b101(mod11)b161(mod17)

그러므로 b560 에 대해 다음과 같은 사실을 알 수 있다.

b560=(b2)2801(mod3)b560=(b10)561(mod11)b560=(b16)351(mod17)

따라서 561 과 서로소인 모든 양의 정수 b에 대해 다음이 성립한다.

b5601(mod(3×11×17))b5601(mod561)

(만약 b가 561 과 서로소가 아니라면? 가령 b 가 11 의 배수라면 mod11 의 결과가 1 이 아니라 0 이 된다. 따라서 위의 합동식은 성립하지 않게 된다.)

참고문헌

  • Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일