[정수론 입문 시리즈 15편] 합동, 거듭제곱, 그리고 페르마의 소정리

컴퓨터가 $2^{1000} \bmod 7$을 계산할 때 정말 $2$를 1000번 곱할까요? 사실 답은 작은 반복 패턴만 보면 금방 나옵니다. 예를 들어 $2^3\equiv1\pmod7$이라서 지수를 크게 줄일 수 있습니다.

이번 글에서는 이런 아이디어를 소수 mod에서 정리한 페르마의 소정리를 봅니다. 암호, 해시, 큰 수 계산에서도 자주 쓰이는 “거듭제곱을 작게 줄이는 법”입니다.

What this post covers

• 소수 법에서 거듭제곱표가 보이는 규칙성을 관찰합니다.
• 페르마의 소정리의 정확한 내용을 정리합니다.
• 페르마의 소정리가 큰 거듭제곱 계산을 어떻게 줄여 주는지 확인합니다.
• 정리의 증명 아이디어인 “곱하기가 나머지들을 재배열한다”는 관점을 설명합니다.
• 페르마의 소정리가 합성수 판별에 어떻게 쓰일 수 있는지 봅니다.

이번 글에서 새로 나오는 용어

• 페르마의 소정리 (Fermat's Little Theorem): 소수 $p$와 $a\not\equiv 0\pmod p$인 정수 $a$에 대해 $a^{p-1}\equiv 1\pmod p$가 성립한다는 정리입니다.
• 소수 (Prime Number): 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 계승 (Factorial): $1\cdot2\cdot3\cdots n$을 $n!$로 쓰는 표기입니다.

실험: mod 5에서 거듭제곱표 보기

먼저 작은 표부터 봅시다. 소수 $p=5$에서 정수 $a=0,1,2,3,4$의 거듭제곱을 계산하면 다음과 같습니다.

a	a^1 mod 5	a^2 mod 5	a^3 mod 5	a^4 mod 5	a^5 mod 5
0	0	0	0	0	0
1	1	1	1	1	1
2	2	4	3	1	2
3	3	4	2	1	3
4	4	1	4	1	4

0의 거듭제곱을 제외하면 $a^4\equiv1\pmod5$입니다. 즉 5의 배수가 아닌 수들은 4번 거듭제곱하면 나머지가 1로 돌아옵니다.

비슷하게 $p=7$일 때는 0이 아닌 나머지들에 대해 $a^6\equiv1\pmod7$이 됩니다. 더 큰 소수 $p=11$에 대해서도 같은 현상을 확인할 수 있습니다.

$$1^{10}\equiv1, \quad 2^{10}\equiv1, \quad 3^{10}\equiv1, \quad\dots\quad, 10^{10}\equiv1 \pmod {11}.$$

이 관찰을 바탕으로 다음과 같은 추측을 세울 수 있습니다.

소수 $p$에 대해, $1\le a<p$이면 $a^{p-1}\equiv1\pmod p$이다.

사실 $a$를 $1$과 $p-1$ 사이의 수로 제한할 필요는 없습니다. $a$가 $p$의 배수가 아니기만 하면 됩니다.

이론 정리: 페르마의 소정리

정리 9.1. 페르마의 소정리

$p$가 소수이고, $a\not\equiv0\pmod p$인 정수 $a$에 대해

$$a^{p-1}\equiv1\pmod p$$

가 성립합니다.

이 정리는 1640년경 페르마가 프레니클 드 베시에게 보낸 편지에서 처음 언급했지만, 페르마는 증명을 제시하지 않았습니다. 처음 알려진 증명은 라이프니츠의 증명으로 보입니다.

왜 이 정리가 강력할까?

페르마의 소정리는 매우 큰 수에 대한 합동을 작은 소수 하나로 확인하게 해 줍니다.

예를 들어 $2^{20}\pmod7$을 봅시다. 직접 큰 수를 만들지 않아도, 7이 소수이고 $2\not\equiv0\pmod7$이므로

$$2^6\equiv1\pmod7$$

입니다. $20=6\cdot3+2$이므로

$$2^{20}=(2^6)^3\cdot2^2\equiv1^3\cdot4\equiv4\pmod7$$

입니다.

예시 1. $2^{33}\pmod 7$

페르마의 소정리에 의해

$$2^6\equiv1\pmod7$$

입니다. 또

$$33=6\cdot5+3$$

이므로

$$2^{33}=2^{6\cdot5+3}=(2^6)^5\cdot2^3 \equiv1^5\cdot8 \equiv1\pmod7$$

입니다.

큰 거듭제곱을 직접 계산하지 않고, 지수를 $p-1$로 나누어 줄인 셈입니다.

예시 2. $3^{100}\pmod {11}$

이번에는 $3^{100}\pmod {11}$을 계산해 봅시다. 11은 소수이고 $3\not\equiv0\pmod {11}$이므로

$$3^{10}\equiv1\pmod {11}$$

입니다. 그런데 $100=10\cdot10$이므로

$$3^{100}=(3^{10})^{10}\equiv1^{10}\equiv1\pmod {11}$$

입니다. 큰 거듭제곱을 직접 계산하지 않고, 지수를 $p-1$로 나누어 줄인 셈입니다.

합성수 판별에 쓰기

페르마의 소정리는 어떤 수가 소수가 아님을 보여 주는 데도 사용할 수 있습니다. 만약 $n$이 소수라면, $a\not\equiv0\pmod n$인 $a$에 대해 $a^{n-1}\equiv1\pmod n$이어야 합니다.

따라서 어떤 $a$에 대해 이 합동이 깨지면 $n$은 반드시 합성수입니다. 작은 예로 $n=15$를 봅시다. 만약 15가 소수라면 $2^{14}\equiv1\pmod {15}$여야 합니다. 하지만

$$2^{14}=16384\equiv4\pmod {15}$$

이므로 15는 소수가 아니라는 사실을 확인할 수 있습니다. Python에서는 더 큰 수도 같은 방법으로 빠르게 검사할 수 있습니다.

다만 주의할 점도 있습니다. 페르마의 소정리는 “소수이면 이 합동이 성립한다”는 명제입니다. 반대로 어떤 밑 $a$에 대해 $a^{n-1}\equiv1\pmod n$이 성립한다고 해서 $n$이 반드시 소수라고 결론내릴 수는 없습니다.

Common mistakes

1. 법이 소수인지 확인하지 않는 실수

페르마의 소정리는 소수 $p$에 대한 정리입니다. 합성수 법에서는 같은 결론이 일반적으로 성립하지 않습니다.

2. $a$가 $p$의 배수인 경우까지 그대로 적용하는 실수

정리의 조건은 $a\not\equiv0\pmod p$입니다. $a\equiv0\pmod p$이면 $a^{p-1}\equiv0\pmod p$이지 1이 아닙니다.

3. “페르마 테스트를 통과하면 소수”라고 결론내리는 실수

페르마의 소정리를 이용해 합성수임을 보일 수는 있지만, 한 번의 합동이 성립한다고 해서 소수임이 증명되는 것은 아닙니다.

더 깊이 보기 (선택)

페르마의 소정리가 왜 성립하는지 조금 더 엄밀하게 보고 싶은 학생만 읽어도 됩니다. 핵심은 “곱하기는 나머지들을 재배열한다”는 생각입니다.

도우미 정리 9.2

$p$가 소수이고 $a\not\equiv0\pmod p$라고 합시다. 그러면

$$a,2a,3a,\dots,(p-1)a\pmod p$$

는

$$1,2,3,\dots,p-1\pmod p$$

의 재배열입니다.

왜 그럴까요? $ia\equiv ja\pmod p$라고 가정하면 $p\mid(i-j)a$입니다. 그런데 $p$는 소수이고 $p\nmid a$이므로 $p\mid(i-j)$입니다. $1\le i,j\le p-1$에서는 이것이 $i=j$일 때만 가능합니다.

따라서 $a,2a,\dots,(p-1)a$는 0이 아닌 서로 다른 나머지 $p-1$개를 모두 한 번씩 나타냅니다. 즉 $1,2,\dots,p-1$의 재배열입니다.

이제 두 목록의 모든 항을 곱하면

$$a\cdot(2a)\cdot(3a)\cdots((p-1)a) \equiv 1\cdot2\cdot3\cdots(p-1) \pmod p$$

입니다. 왼쪽의 $a$들을 모으면

$$a^{p-1}(p-1)!\equiv(p-1)!\pmod p$$

가 됩니다. $(p-1)!$은 $p$와 서로소이므로 양변에서 나눌 수 있고,

$$a^{p-1}\equiv1\pmod p$$

를 얻습니다. 이것이 페르마의 소정리입니다.

연습 문제

아래 점검 퀴즈에서 페르마의 소정리를 직접 적용해 보세요.

Wrap-up

이번 글에서는 Silverman 9장의 흐름에 따라 소수 법에서 거듭제곱표를 관찰하고, 그 규칙성이 페르마의 소정리로 정리되는 과정을 살펴보았습니다. 핵심 아이디어는 $a$를 곱하는 것이 0이 아닌 나머지들을 재배열한다는 것입니다.

다음 글에서는 오일러 피 함수와 오일러 정리를 보며, 페르마의 소정리가 일반적인 법에서 어떻게 넓어지는지 정리하겠습니다.