페르마의 소정리
Fermat's little theorem
정리
If p is prime and a is an integer not divisible by p, then
ap−1≡1(modp)
Furthermore, for every integer a we have
ap≡a(modp)
- p 가 소수이고 a 가 p 로 나누어지지 않는 정수이면
- ap−1≡1(modp) 이다.
- 그리고, 모든 a 에 대하여
- ap≡a(modp) 이다.
계산 예제
7222mod11 을 계산하라.
7 보다 큰 소수 11 을 사용해 페르마의 소정리에 적용해보면 다음을 얻을 수 있다.
711−1≡1(mod11)710≡1(mod11)이제 7222mod11을 단순하게 정리할 수 있다.
7222=722×10×72따라서 답은 5 다.
7222≡122×72(mod11)≡49(mod11)≡5(mod11)유사소수
pseudoprime
페르마의 소정리는 편리하지만 주의해야 할 점이 있다.
- p 가 소수이면 페르마의 소정리를 만족한다.
- 하지만 페르마의 소정리를 만족한다고 해서 p 가 반드시 소수인 것은 아니다.
즉, p 가 합성수인데도 ap−1≡1(modp) 를 통과하는 경우가 있다.
이런 합성수들을 유사소수라 부른다.
Let b be a positive integer. If n is a composite positive integer, and bn−1≡1(modn), then n is called a pseudoprime to the base b.
- b 를 양의 정수라 하자.
- n 이 양의 정수인 합성수이고, bn−1≡1(modn) 이면
- n을 b를 밑수로 하는 유사소수라 부른다.
유사소수 예제
b=2일 때, 341 은 유사소수인가?
유사소수인지 확인하려면 두 조건을 체크하면 된다.
- 합성수인가?
- 다음 합동식이 참인지 확인하면 된다.
- 2341−1≡1(mod341).
- 즉, 2340 을 341 로 나눈 나머지가 1 인지 확인하면 된다.
일단 341 은 합성수가 맞다. 341=11×31.
이제 2340을 341로 나누면 나머지가 1 이 나오는지를 확인하면 된다.
2340은 꽤 큰 수이기 때문에 나머지를 구하는 것은 까다로운 일이다.
그러나 페르마의 소정리를 활용하면 210을 11로 나눈 나머지가 1 이라는 사실을 쉽게 확인할 수 있고, 이를 이용해 2340mod341 을 쉽게 풀 수 있다.
211−1≡1(mod11)210≡1(mod11)따라서 다음과 같이 확인할 수 있다.
2341−1≡1(mod341)2340≡1(mod341)(210)34≡1(mod341)134≡1(mod341)1≡1(mod341)341 은 2를 밑수로 하는 유사소수이다.
카마이클 수
Carmichael number
A composite integer n that satisfies the congruence bn−1≡1(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 에 대하여,
- bn−1≡1(modn)을 만족하는 합성수인 정수 n을 카마이클 수라 부른다.
카마이클 수 예제
561 은 카마이클 수인가?
카마이클 수인지 확인하려면 두 조건을 체크하면 된다.
- 합성수인가?
- gcd(b,n)인 모든 양의 정수 b에 대하여 b561−1≡1(mod561) 이 성립하는가?
일단 561 은 합성수가 맞다. 561=3×11×17.
이제 b560≡1(mod561) 을 확인하자.
561 의 소인수를 페르마의 소정리 ap−1≡1(modp) 에 넣어 다음과 같이 정리할 수 있다.
b2≡1(mod3)b10≡1(mod11)b16≡1(mod17)그러므로 b560 에 대해 다음과 같은 사실을 알 수 있다.
b560=(b2)280≡1(mod3)b560=(b10)56≡1(mod11)b560=(b16)35≡1(mod17)따라서 561 과 서로소인 모든 양의 정수 b에 대해 다음이 성립한다.
b560≡1(mod(3×11×17))b560≡1(mod561)(만약 b가 561 과 서로소가 아니라면? 가령 b 가 11 의 배수라면 mod11 의 결과가 1 이 아니라 0 이 된다. 따라서 위의 합동식은 성립하지 않게 된다.)
참고문헌
- Rosen의 이산수학 / Kenneth H. Rosen 저 / 공은배 등저 / 한국맥그로힐(McGraw-Hill KOREA) / 2017년 01월 06일