페르마의 소정리 증명과 예제 — RSA 암호까지

📐 개념 정리

페르마의 소정리는 소수 p와 p의 배수가 아닌 정수 a에 대해 a의 p−1제곱을 p로 나눈 나머지가 1이라는 정리다. 순열 논법과 이항정리로 하는 두 가지 증명, 큰 거듭제곱의 나머지를 구하는 예제, RSA 암호에 쓰이는 원리까지 정리했다.

페르마의 소정리는 "p가 소수이고 a가 p의 배수가 아니면, a를 p−1번 곱한 수를 p로 나눈 나머지는 항상 1"이라는 정리다. 2를 6번 곱한 64를 7로 나누면 나머지가 1이고, 3을 4번 곱한 81을 5로 나누면 나머지가 1이다. 어떤 소수를 잡고 어떤 밑을 잡아도 예외 없이 성립한다. 이 짧은 정리는 큰 거듭제곱의 나머지를 암산으로 구하게 해 주고, 소수 판정 알고리즘의 뼈대가 되며, 인터넷 보안의 기초인 RSA 암호가 작동하는 이유이기도 하다. 이 글은 정리의 뜻과 표기, 두 가지 증명, 예제 풀이, 그리고 RSA까지 이어지는 흐름을 순서대로 정리한다.

페르마의 소정리란? 뜻과 간단한 예시

17세기 프랑스의 법률가이자 수학자 피에르 드 페르마는 1640년 친구에게 보낸 편지에서 이 성질을 언급했다. 증명은 남기지 않았고, 정식 증명은 1736년 오일러가 발표했다. 페르마의 소정리라는 이름은 같은 사람의 이름이 붙은 페르마의 마지막 정리와 구분하기 위한 것이다. 마지막 정리는 증명에 350년이 걸린 난제였지만, 소정리는 고등학교 수준의 지식으로 증명할 수 있는 정수론의 기본 도구다.

예시로 감을 잡아 보자. 소수 7을 고르고 밑을 2, 3, 4, 5, 6으로 바꿔 가며 6제곱을 7로 나누면 나머지가 모두 1이다. 반면 법이 소수가 아니면 깨진다. 2의 3제곱인 8을 4로 나누면 나머지는 0이다. 밑이 소수의 배수여도 깨진다. 7의 6제곱은 7의 배수라 나머지가 0이다. 그래서 정리에는 "p는 소수", "a는 p의 배수가 아님"이라는 두 조건이 붙는다.

합동식 표기와 페르마의 소정리 두 가지 형태

두 정수 $x$, $y$를 $p$로 나눈 나머지가 같을 때 $x \equiv y \pmod p$라 쓰고 "법 $p$에 대해 합동"이라 읽는다. 합동식은 등식처럼 양변에 같은 수를 더하거나 곱할 수 있지만, 나누기는 법 $p$와 서로소인 수로만 가능하다. 이 표기로 페르마의 소정리를 적으면 다음과 같다.

$$a^{p-1} \equiv 1 \pmod p \quad (p\text{는 소수},\ \gcd(a,p)=1), \qquad a^{p} \equiv a \pmod p \quad (\text{모든 정수 } a)$$

첫 식이 원래 형태이고 $\gcd(a,p)=1$은 $a$가 $p$의 배수가 아니라는 조건이다. 둘째 식은 첫 식의 양변에 $a$를 곱한 것으로, $a$가 $p$의 배수일 때는 양변이 모두 $p$의 배수라 자동으로 성립하므로 조건이 사라진다. 두 형태는 동치다. 페르마의 소정리 증명은 여러 가지가 알려져 있는데, 여기서는 순열 논법과 귀납법 두 가지를 끝까지 보인다.

페르마의 소정리 증명 1 — 순열 논법

보조정리부터 세운다. $p$가 소수이고 $a$가 $p$의 배수가 아닐 때, $a, 2a, 3a, \ldots, (p-1)a$를 각각 $p$로 나눈 나머지는 모두 다르고 0이 아니다. 0이 아닌 이유는 $ka$가 $p$의 배수가 되려면 $k$나 $a$가 $p$의 배수여야 하는데 둘 다 아니기 때문이다. 서로 다른 이유는 $ia \equiv ja \pmod p$이면 $(i-j)a$가 $p$의 배수이고, $a$가 아니므로 $i-j$가 $p$의 배수여야 하는데 $i$, $j$가 1 이상 $p-1$ 이하라 $i=j$일 수밖에 없기 때문이다. 그러므로 이 $p-1$개의 나머지는 $1, 2, \ldots, p-1$을 순서만 바꿔 놓은 것이다.

7을 법으로 밑 3을 잡으면 3, 6, 9, 12, 15, 18의 나머지는 3, 6, 2, 5, 1, 4로 정확히 1부터 6까지가 한 번씩 나온다. 이제 양쪽을 전부 곱한다.

$$\prod_{k=1}^{p-1}(ka) \equiv \prod_{k=1}^{p-1} k \pmod p \;\Longrightarrow\; a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p$$

$\prod$는 곱을 뜻하고 $(p-1)!$은 1부터 $p-1$까지의 곱이다. 왼쪽에서 $a$가 $p-1$번 곱해져 $a^{p-1}$이 밖으로 나온다. $(p-1)!$은 $p$보다 작은 수들의 곱이라 $p$와 서로소이므로 양변에서 지울 수 있고, $a^{p-1} \equiv 1 \pmod p$가 남는다. 증명이 끝났다. 이 증명이 알려 주는 핵심은 "소수를 법으로 하면 0이 아닌 수로 곱하는 것은 나머지들을 섞기만 할 뿐 잃어버리지 않는다"는 사실이다.

페르마의 소정리 증명 2 — 이항정리와 수학적 귀납법

둘째 형태 $a^p \equiv a$를 $a$에 대한 귀납법으로 보인다. $a=0$일 때는 양변이 0이라 성립한다. $a$에서 성립한다고 가정하고 $a+1$을 본다.

$$(a+1)^p = \sum_{k=0}^{p}\binom{p}{k}a^{k} \equiv a^{p} + 1 \pmod p, \qquad \binom{p}{k}=\frac{p!}{k!\,(p-k)!}\ (0<k<p)$$

$\binom{p}{k}$는 이항계수다. $0<k<p$일 때 분자 $p!$에는 소수 $p$가 들어 있지만 분모 $k!\,(p-k)!$의 인수는 모두 $p$보다 작아 $p$를 약분할 수 없다. 따라서 양 끝의 두 항을 뺀 나머지 이항계수는 전부 $p$의 배수이고, 법 $p$에서 사라진다. 남는 것은 $a^p+1$이고 귀납 가정에 의해 $a^p \equiv a$이므로 $(a+1)^p \equiv a+1$이 된다. 음의 정수는 $a^p \equiv a$에서 $a$ 대신 $-a$를 넣어 처리한다. 이 증명은 이항계수가 소수로 나누어떨어진다는 성질 하나로 끝나며, 파스칼의 삼각형에서 소수 번째 줄의 양 끝을 뺀 수가 모두 그 소수의 배수라는 관찰과 같은 내용이다.

페르마의 소정리 예제 — 큰 거듭제곱의 나머지와 역원

가장 흔한 활용은 거듭제곱의 나머지 계산이다. $3^{100}$을 7로 나눈 나머지를 구해 보자. 페르마의 소정리에 따라 $3^6 \equiv 1 \pmod 7$이므로 지수를 6으로 나눈다. $100 = 6 \times 16 + 4$이니 $3^{100} = (3^6)^{16}\cdot 3^4 \equiv 3^4 = 81 \equiv 4 \pmod 7$이다. 답은 4다. 같은 방법으로 $2^{2026}$을 13으로 나눈 나머지는 $2^{12} \equiv 1$을 이용해 $2026 = 12 \times 168 + 10$에서 $2^{10} = 1024 \equiv 10 \pmod{13}$이다. 지수가 아무리 커도 $p-1$로 나눈 나머지만 남기면 된다.

둘째 활용은 나눗셈이다. 법 $p$에서 $a$로 나눈다는 것은 $a$와 곱해 1이 되는 역원을 곱하는 일인데, 페르마의 소정리를 $a \cdot a^{p-2} \equiv 1$로 다시 쓰면 $a^{p-2}$가 바로 $a$의 역원이다. 법 7에서 3의 역원은 $3^5 = 243 \equiv 5$이고, 실제로 $3 \times 5 = 15 \equiv 1 \pmod 7$이다. 프로그래밍 대회에서 조합의 수를 큰 소수로 나눈 나머지를 구할 때 쓰는 방법이다.

셋째 활용은 소수 판정이다. $a^{n-1} \equiv 1 \pmod n$이 깨지면 $n$은 확실히 합성수다. 그러나 역은 성립하지 않는다. $561 = 3 \times 11 \times 17$은 합성수인데도 561과 서로소인 모든 $a$에 대해 $a^{560} \equiv 1 \pmod{561}$이다. 이런 카마이클 수가 무한히 많기 때문에 실제 알고리즘은 페르마의 소정리를 보강한 밀러-라빈 판정법을 쓴다. 페르마의 소정리는 소수의 필요조건이지 충분조건이 아니다.

페르마의 소정리와 RSA 암호 — 오일러 정리로 확장

오일러는 법을 소수에서 일반 정수로 넓혔다. $n$과 서로소인 $a$에 대해 $a^{\varphi(n)} \equiv 1 \pmod n$인데, $\varphi(n)$은 $n$ 이하에서 $n$과 서로소인 수의 개수다. $n$이 소수 $p$이면 $\varphi(p)=p-1$이라 페르마의 소정리로 돌아오고, 서로 다른 두 소수의 곱 $n=pq$이면 $\varphi(n)=(p-1)(q-1)$이다. RSA 암호는 바로 이 경우를 쓴다.

RSA는 두 큰 소수 $p$, $q$를 골라 $n=pq$를 공개하고, $\varphi(n)$과 서로소인 공개 지수 $e$를 정한 뒤 $ed \equiv 1 \pmod{\varphi(n)}$이 되는 비밀 지수 $d$를 계산한다. 메시지 $m$은 $c = m^e \bmod n$으로 암호화하고, 받는 쪽은 $c^d \bmod n$으로 복원한다. 복원이 되는 이유가 오일러 정리, 뿌리를 따지면 페르마의 소정리다.

$$m^{ed} = m^{1+k\,\varphi(n)} = m\cdot\left(m^{\varphi(n)}\right)^{k} \equiv m \pmod n$$

$ed \equiv 1 \pmod{\varphi(n)}$이므로 $ed = 1 + k\varphi(n)$인 정수 $k$가 있고, 괄호 안이 1과 합동이 되어 $m$이 그대로 돌아온다. 작은 수로 확인하면 $p=5$, $q=11$, $n=55$, $\varphi(n)=40$, $e=3$, $d=27$이다. 메시지 7을 암호화하면 $7^3 = 343 \equiv 13 \pmod{55}$이고, $13^{27} \bmod 55$를 계산하면 7이 정확히 돌아온다. 공개된 $n$에서 $\varphi(n)$을 알려면 $n$을 소인수분해해야 하는데, 수백 자리 수의 소인수분해가 사실상 불가능하다는 점이 RSA의 안전성이다.

나는 대학 정수론 첫 학기에 페르마의 소정리 증명을 순열 논법으로만 외웠다가, 시험에서 귀납법 증명을 요구받고 이항계수가 왜 소수의 배수인지 그 자리에서 다시 생각해야 했던 기억이 있다. 그때 두 증명이 소수를 법으로 하면 곱셈이 아무것도 잃지 않는다는 같은 성질을 다른 각도에서 본 것임을 알게 됐다.

정리하면 페르마의 소정리는 소수 $p$에 대해 $a^{p-1} \equiv 1 \pmod p$라는 한 줄이고, 순열 논법과 이항정리로 증명되며, 거듭제곱의 나머지·역원·소수 판정에 쓰이고, 오일러 정리로 확장되어 RSA 암호를 떠받친다.

함께 읽으면 좋은 글

유클리드 호제법 원리와 증명, 최소공배수까지 정리 이항정리 공식과 증명 — 일반항·파스칼의 삼각형까지 벤포드 법칙이란? 뜻과 증명, 회계부정 적발 원리

참고 자료

Wikipedia — Fermat's little theorem Wolfram MathWorld — Fermat's Little Theorem Wikipedia — Carmichael number Wikipedia — RSA cryptosystem