페르마 소정리

개요 — 동기·문제의식

$2^{10}\bmod11$, $2^{100}\bmod11$, $2^{1000000}\bmod11$ — 지수가 아무리 커져도 이 값들을 계산하는 데 진짜로 큰 수의 곱셈이 필요할까? 직접 곱하면 $2^{1000000}$ 은 우주의 원자 수보다 많은 자릿수를 가진 수다. 그런데 답은 놀랍도록 간단하다: 소수 $p$ 를 법으로 한 거듭제곱은 지수가 주기 $p-1$ 로 반복된다. 이 반복의 정확한 형태가 Fermat 소정리다.

이 정리는 정수론에서 가장 자주 쓰이는 도구 중 하나다. 지수를 줄여 거대한 거듭제곱을 즉시 계산하게 해주고(모듈러 거듭제곱과 RSA), 어떤 수가 합성수임을 인수분해 없이 알아내는 소수판정의 출발점이 되며(primality testing), Euler 정리로 합성수 법까지 일반화되어 RSA 암호의 수학적 근거가 된다. 군론적으로 보면 $\mathbb{Z}_p^\times$ 가 위수 $p-1$ 인 군이라는 사실의 직접적인 귀결이며(Lagrange 정리), 이 페이지에서 다루는 "재배열 논법"은 군론을 몰라도 초등적으로 같은 결론에 도달하는 길이다.

직관

$p=7$, $a=3$ 이라 하고 $1,2,3,4,5,6$ 에 $3$ 을 곱해 $\bmod7$ 로 본다: $3,6,2,5,1,4$. 순서는 뒤섞였지만 나온 값들의 집합은 정확히 $\{1,2,3,4,5,6\}$ 그대로다 — 곱셈 "$\times3 \bmod 7$" 이 잉여류 집합 $\{1,\dots,6\}$ 을 자기 자신으로 보내는 재배열(순열)이기 때문이다. 이게 가능한 이유는 $\gcd(3,7)=1$ 이라 "$3$ 을 곱한다"가 가역 연산이어서 서로 다른 입력이 서로 다른 출력으로 가기 때문이다(소거법칙). 이제 양쪽을 다 곱해보면, 순서만 다를 뿐 같은 숫자들의 곱이므로 $$(1\cdot3)(2\cdot3)(3\cdot3)(4\cdot3)(5\cdot3)(6\cdot3)\ \equiv\ 1\cdot2\cdot3\cdot4\cdot5\cdot6\pmod7$$ 좌변은 $6!\cdot3^6$, 우변은 $6!$. $6!$ 이 $7$과 서로소이니 약분하면 $3^6\equiv1\pmod7$ 이 떨어진다 — 이것이 Fermat 소정리의 알맹이다: "법과 서로소인 수를 곱하는 연산은 잉여류 전체를 뒤섞을 뿐 보존하므로, 그 곱들의 곱은 원래 곱과 같고, 거기서 거듭제곱이 정확히 $1$로 떨어진다."

정의

(Fermat 소정리) $p$ 가 소수이고 $a\not\equiv0\pmod p$ 이면¹ $$a^{p-1}\equiv1\pmod p.$$

왜 가설 $p\nmid a$ 가 필요한가. $a\equiv0\pmod p$ 이면 $a^{p-1}\equiv0\pmod p$ 이지 $1$ 이 아니다 — 표준형은 거짓이 된다. 동치형 $a^p\equiv a$ 는 이 예외적인 경우도 양변이 똑같이 $0$ 이 되어 자동으로 흡수하므로 "모든 $a$" 에 대해 성립하는 형태로 다시 쓸 수 있는 것이다.

왜 $p$ 가 소수여야 하는가. 증명의 핵심은 "$1,\dots,p-1$ 전부가 $p$ 와 서로소"라는 사실인데, 이는 $p$ 가 소수일 때만 자동으로 참이다. $p$ 가 합성수면 $1,\dots,p-1$ 중 일부가 $p$ 와 공약수를 가져 재배열 논법이 깨진다(아래 "흔한 오해" 참조 — Euler 정리가 이 경우를 일반화한다).

주요 정리

정리 (Fermat 소정리).¹ 위 진술대로.

따라서 $p-1$ 개의 값 $1a,\dots,(p-1)a \pmod p$ 는 전부 $\{1,\dots,p-1\}$ 안에 있고 서로 다르므로, 정확히 $\{1,\dots,p-1\}$ 의 재배열이다. 양변의 곱을 취하면 $$\prod_{i=1}^{p-1}(ia)\ \equiv\ \prod_{i=1}^{p-1}i \pmod p\quad\Longrightarrow\quad (p-1)!\,a^{p-1}\equiv(p-1)!\pmod p.$$ $(p-1)!$ 은 $p$와 서로소($1,\dots,p-1$ 모두 $p$와 서로소이므로)이니 양변에서 소거 가능 → $a^{p-1}\equiv1\pmod p$. ∎

따름정리 (지수 축소). $\gcd(a,p)=1$ 일 때 $a^N\bmod p$ 는 지수를 $N\bmod(p-1)$ 로 줄여 계산해도 된다: $N=(p-1)q+r$ 이면 $a^N=(a^{p-1})^qa^r\equiv1^q\cdot a^r=a^r\pmod p$.

따름정리 (모듈러 역원의 닫힌 형태). $\gcd(a,p)=1$ 이면 $a\cdot a^{p-2}\equiv a^{p-1}\equiv1\pmod p$ 이므로 $$a^{-1}\equiv a^{p-2}\pmod p.$$ 나눗셈 없이 거듭제곱만으로 역원을 구하는 공식 — 모듈러 거듭제곱과 RSA의 연속 제곱과 결합하면 매우 빠르다.

예제

예제 1 (기본 검증). $2^{10}\bmod11$: Fermat에 의해 $p=11$, $a=2$, $\gcd(2,11)=1$ → $2^{10}\equiv1\pmod{11}$. 직접 확인: $2^{10}=1024=93\cdot11+1$ ✓.

예제 2 (지수 축소). $3^{100}\bmod7$: $p-1=6$. $100=6\cdot16+4$ → $3^{100}\equiv3^4\pmod7$. $3^2=9\equiv2$, $3^4=(3^2)^2\equiv2^2=4\pmod7$. 답: $4$.

예제 3 (역원을 거듭제곱으로). $\bmod13$ 에서 $5^{-1}$: 공식으로 $5^{-1}\equiv5^{11}\pmod{13}$. 직접 검산이 더 빠르다: $5\cdot8=40=3\cdot13+1\equiv1$ → $5^{-1}\equiv8$. (공식이 맞는지 확인: $5^{11}\bmod13$ 을 연속제곱으로 $5^2=25\equiv-1,\ 5^4\equiv1,\ 5^8\equiv1,\ 5^{11}=5^8\cdot5^2\cdot5\equiv1\cdot(-1)\cdot5=-5\equiv8$ ✓ 일치.)

예제 4 (Fermat으로 합성수 판정 — 첫 발판). $n=15$ 가 소수라면 $2^{14}\equiv1\pmod{15}$ 이어야 한다. 실제로 $2^4=16\equiv1\pmod{15}$ 이므로 $2^{14}=2^{12}\cdot2^2\equiv1\cdot4=4\not\equiv1\pmod{15}$ → $15$는 합성수(증인 $a=2$가 합성수임을 폭로). primality testing의 출발점.

예제 5 (큰 지수의 빠른 계산). $2^{1000000}\bmod13$: $p-1=12$. $1000000=12\cdot83333+4$ → $2^{1000000}\equiv2^4=16\equiv3\pmod{13}$. (이렇게 거대한 지수를 종이 위에서 즉시 처리한다.)

예제 6 (Fermat의 한계 — 합성수 법에서는 적용 불가). $a^{n-1}\bmod n$ 을 $n=9$(합성수), $a=2$ 로 시도: $2^8=256=28\cdot9+4\equiv4\pmod9\ne1$ — Fermat의 결론이 안 나온다(가설이 $p$ 소수인데 $9$는 합성수이므로 당연하다). 합성수 법의 올바른 일반화는 Euler 정리 $a^{\varphi(n)}\equiv1\pmod n$ ($\gcd(a,n)=1$ 일 때).

흔한 오해와 함정

• "역도 성립한다" (Fermat의 거짓 역) — 틀림. $a^{n-1}\equiv1\pmod n$ 이 어떤 $a$ 에 대해 성립한다고 해서 $n$이 반드시 소수는 아니다. Carmichael 수가 반례: $n=561=3\cdot11\cdot17$ 은 합성수인데도 $\gcd(a,561)=1$ 인 모든 $a$ 에 대해 $a^{560}\equiv1\pmod{561}$ 이 성립한다.² 이런 수는 Fermat 판정을 완전히 속이므로, Fermat 소정리는 "합성수임을 증명"하는 데는 100% 확실하지만(예제 4처럼 $a^{n-1}\not\equiv1$ 을 찾으면 끝) "소수임을 증명"하는 데는 절대 충분하지 않다.
• 법이 합성수인데 그대로 $p-1$ 자리에 $n-1$ 을 넣음 — $n$이 합성수면 지수를 $n-1$ 로 줄이는 정당성 자체가 없다(증명이 소수성에 의존). 합성수 법에서는 $\varphi(n)$ 을 써야 한다.
• $p\mid a$ 인 경우를 빠뜨림 — $a\equiv0\pmod p$ 이면 $a^{p-1}\equiv0$, 표준형이 성립하지 않는다. 표준형을 쓰기 전에 항상 $p\nmid a$ 를 확인해야 하며, 모든 $a$ 에 적용하려면 동치형 $a^p\equiv a$ 를 쓴다.
• 재배열 논법을 "그냥 같은 수들이니까 곱이 같다"로 오해 — 핵심은 곱이 같다는 사실 자체가 아니라, 소거 가능한 인수 $(p-1)!$ 로 나눠 떨어진다는 점이다. $p$가 소수가 아니면 $(p-1)!$ 이 $n$과 서로소라는 보장이 없어 소거가 막힌다.
• "증인 하나만 확인하면 충분"이라는 과신 — 합성수 판정에는 증인 하나로 충분하지만(반례 하나로 끝), Carmichael 수처럼 거의 모든 증인이 통과해버리는 수가 존재하므로 실전 소수판정 알고리즘은 Miller–Rabin처럼 더 정교한 도구를 쓴다(primality testing).

큰 그림 / 연결

Fermat 소정리는 합동산술의 "거듭제곱은 결국 순환한다"는 사실을 가장 먼저, 가장 깨끗하게 보여주는 정리다. 직접적인 일반화는 합성수 법으로 확장한 Euler 정리이고, 같은 재배열 논법이 원시근에서 $\mathbb{Z}_p^\times$ 의 순환군 구조를 분석할 때 다시 쓰인다. 계산적으로는 모듈러 거듭제곱과 RSA에서 지수 축소와 연속 제곱법을 결합해 거대한 거듭제곱을 즉시 계산하는 데 직접 쓰이고, 그 RSA 복호화의 정당성 자체가 Euler 정리(따라서 Fermat의 일반화)에 의존한다. 소수판정 알고리즘(primality testing)은 정확히 이 정리의 대우(對偶) — "거듭제곱이 $1$이 안 나오면 합성수"를 — 실용적 도구로 바꾼 것이다. 대수적으로는, $\mathbb{Z}_p^\times$ 가 위수 $p-1$ 인 유한군이라는 사실에서 Lagrange 정리로 즉시 Fermat을 얻는 길도 있다(군론적 시야는 algebra 위키 structure-of-zn, cyclic-groups에서).

연습문제

1. $7^{222}\bmod11$ 을 구하라.
2. Fermat 소정리로부터 $a^{-1}\pmod p$ 를 거듭제곱 형태로 표현하라.
3. $n=15$ 가 $2^{14}\not\equiv1\pmod{15}$ 으로 합성수임을 보여라.
4. 모든 정수 $a$ 에 대해 $a^{13}\equiv a\pmod{13}$ 임을 보여라.
5. $p$ 가 홀소수일 때 $1^{p-1}+2^{p-1}+\cdots+(p-1)^{p-1}\equiv-1\pmod p$ 임을 보여라.
6. $561=3\cdot11\cdot17$ 이 $a=2$ 에 대해 $2^{560}\equiv1\pmod{561}$ 을 만족함을 (CRT로 $3,11,17$ 각각에서) 확인하라.
7. $5^{2024}\bmod7$ 을 지수 축소로 구하라.
8. $\bmod17$ 에서 $a^{16}\equiv1$ 이 어떤 $a=1,\dots,16$ 에 대해서도 성립함을, 직접 몇 개 계산해 확인하라($a=2,3$).

관련 개념

• 합동식 — 합동 산술의 기본 규칙
• 나눗셈과 최대공약수 — 서로소·소거법칙의 근거
• 오일러 φ 함수와 정리 — 합성수 법으로의 일반화(Euler 정리)
• 원시근 — $\mathbb{Z}_p^\times$ 의 위수·생성원과 Lagrange 정리
• primality testing — Fermat 판정과 Carmichael 수
• 모듈러 거듭제곱과 RSA — 지수 축소·연속 제곱·RSA 복호화의 정당성
• algebra 위키 structure-of-zn (Lagrange를 통한 Fermat), cyclic-groups — 군론적 근거(온톨로지 교차)