소수를 법으로 하는 합동식은 특별한 구조를 가진다. Fermat’s Little Theorem은 거듭제곱을 크게 단순화하고, Wilson’s Theorem은 소수 자체를 특징짓는다. 하지만 Fermat 정리의 역은 성립하지 않으며, 이 틈에서 pseudoprime과 Carmichael Number가 등장한다.
Fermat’s Little Theorem
가 소수이고 이면
이다.
증명: Complete Residue System의 순열
집합
을 modulo 에서 생각한다. 두 원소 가 합동이면
이다. 이므로 를 약분할 수 있고 이다. 이므로 이다.
따라서 는 modulo 에서 서로 다른 0이 아닌 나머지이며, 의 순열이다. 모든 원소를 곱하면
이다. 는 과 서로소이므로 약분하여 를 얻는다.
동치 형태
모든 정수 에 대해
이다. 이면 Fermat’s Little Theorem에 를 곱하면 된다. 이면 양변이 모두 0과 합동이다.
또 다른 증명은 Binomial Theorem과 귀납법을 이용한다. 에 대해 이므로
이고 에서 시작해 모든 자연수로 확장할 수 있다.
큰 거듭제곱 계산
을 구하자. Fermat’s Little Theorem에 의해 이다. 따라서
이고 , , 이므로 답은 4이다.
지수를 로 단순히 나눌 수 있는 것은 밑이 와 서로소일 때이다. 일반 형태 를 사용하면 서로소가 아닌 경우도 안전하게 다룰 수 있다.
Fermat Primality Test
과 인 밑 를 고른다. 만약
이면 은 반드시 합성수이다. 이때 를 Fermat witness라고 한다.
그러나
이라고 해서 이 반드시 소수인 것은 아니다. 이 검사는 합성수를 증명할 수는 있지만, 한 번 통과한 수를 소수라고 확정하지는 못한다.
Pseudoprime
합성수 이 특정 밑 에 대해
을 만족하면 base- pseudoprime이라고 한다.
예를 들어 은 합성수이지만
이므로
이다. 따라서 341은 base 2에 대한 pseudoprime이다.
Carmichael Number
합성수 이 인 모든 정수 에 대해
을 만족하면 Carmichael Number 또는 absolute pseudoprime이라고 한다. 가장 작은 예는
이다.
Pseudoprime은 특정 밑에만 관련된 개념이고, Carmichael Number는 가능한 모든 서로소 밑에 대해 Fermat 검사를 통과한다.
Carmichael Number는 square-free이다
이 Carmichael Number인데 어떤 소수 에 대해 이라고 가정하자. 다음 정수를 선택한다.
이므로 는 의 모든 소인수로 나누어진다. 따라서 는 의 모든 소인수에 대해 1과 합동이고 이다.
Binomial Theorem을 적용하면 두 번째 항 이후에는 가 포함된다. 이므로 이고
이다. 그런데 이므로 이다. 따라서 이 되어 Carmichael 성질에 모순이다. 그러므로 Carmichael Number는 square-free이다.
Korselt Criterion의 충분조건
가 서로 다른 소수의 곱이고 모든 에 대해
이라고 하자. 이면 각 에 대해 Fermat’s Little Theorem으로 이다. 이 의 배수이므로
이다. 서로 다른 모든 가 을 나누므로 그 곱 도 나눈다. 따라서 은 Carmichael Number이다.
Korselt Criterion은 실제로 “square-free이고 모든 소인수 에 대해 ”이라는 조건이 필요충분조건임을 말한다. 여기서는 필기 흐름에 맞추어 충분조건의 핵심을 확인했다.
Wilson’s Theorem
가 소수이면
이다.
증명
modulo 의 0이 아닌 각 원소는 곱셈 역원을 가진다. 자기 자신이 역원인 원소는
을 만족한다. 즉 이고 가 소수이므로
이다.
따라서 의 원소들은 서로 다른 역원끼리 짝지어지고 각 쌍의 곱은 1이다. 남는 원소는 1과 이므로
이다.
Wilson 정리의 역
이면 은 소수이다.
이 합성수라고 가정하자. 보통 , 인 두 인수가 에 포함되므로 이다. 제곱수처럼 인 경우에도 를 따로 확인하고 이면 이므로 와 를 이용해 의 배수를 만들 수 있다. 따라서 합성수에서는 이거나 적어도 이 될 수 없으므로 모순이다.
Wilson 정리는 소수의 필요충분조건이지만 factorial 계산이 매우 커지므로 실용적인 소수 판별법은 아니다.
의 해
가 홀수 소수라고 하자.
합동식 이 해를 가질 필요충분조건은
이다.
필요성
인 해가 있다고 하자. 이므로 Fermat’s Little Theorem에 의해
이다. 가 홀수이므로 이고, 따라서 가 짝수이다. 즉 이다.
충분성
이라 하자. Wilson’s Theorem에서
이다. 뒤쪽 인수는 modulo 에서 앞쪽 인수의 음수들과 대응하므로
이다. 가 짝수이고 Wilson’s Theorem에 의해 왼쪽은 이므로
이다. 따라서 가 한 해이다.
정리
Fermat’s Little Theorem은 소수 법에서의 거듭제곱 구조를 설명하지만 그 역은 거짓이다. Pseudoprime과 Carmichael Number는 Fermat test가 소수를 확정하지 못하는 이유를 보여준다. Wilson’s Theorem은 소수를 정확히 특징짓고, 이를 이용하면 이 제곱잉여가 되는 소수의 합동 조건도 증명할 수 있다.
연습 문제
- Fermat’s Little Theorem으로 을 구한다.
- 이 base 3 Fermat test를 통과하는지 확인한다.
- Wilson’s Theorem을 이용하여 을 구한다.
풀이
1번
이고 이다. 따라서
이다. 이므로 이다.
2번
이고 이다. 이므로
이다. 따라서 91은 base 3 Fermat test를 통과하는 합성수, 즉 base 3 pseudoprime이다.
3번
11은 소수이므로 Wilson’s Theorem에 의해
이다.