페르마의 소정리

1. 서론

페르마의 소정리(Fermat's Little Theorem)는 17세기 프랑스 수학자 피에르 드 페르마(Pierre de Fermat)가 발견한 정수론의 기본 정리입니다. 이 정리는 소수와 거듭제곱 사이의 놀라운 관계를 보여주며, 현대 암호학, 특히 RSA 암호 시스템의 기초가 됩니다.

페르마는 1640년 이 정리를 발견했지만 증명을 남기지 않았고, 약 100년 후 레온하르트 오일러가 이를 일반화하여 오일러 정리를 증명하면서 함께 증명되었습니다.

2. 페르마의 소정리

정리: 페르마의 소정리 (Fermat's Little Theorem)

$p$가 소수이고 정수 $a$가 $p$의 배수가 아니면 (즉, $\gcd(a, p) = 1$이면)

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

동치 형태: 임의의 정수 $a$에 대하여

$$a^p \equiv a \pmod{p}$$

두 형태의 관계:

$\gcd(a, p) = 1$이면: $a^{p-1} \equiv 1 \pmod{p}$에 양변에 $a$를 곱하면 $a^p \equiv a \pmod{p}$
$p | a$이면: $a \equiv 0 \pmod{p}$이므로 $a^p \equiv 0 \equiv a \pmod{p}$

2.1 구체적인 예

예제 1: $p = 5$

$a = 2$일 때 페르마의 소정리를 확인해봅시다.

$$2^{5-1} = 2^4 = 16 = 3 \times 5 + 1 \equiv 1 \pmod{5}$$ ✓

여러 값에 대해 확인:

$a$	$a^4$	$a^4 \bmod 5$
1	1	1
2	16	1
3	81	1
4	256	1

3. 증명

페르마의 소정리는 여러 방법으로 증명할 수 있습니다. 여기서는 세 가지 증명을 소개합니다.

3.1 증명 1: 곱셈 테이블 이용

주어진 조건: $p$는 소수, $\gcd(a, p) = 1$

1단계: 집합 $S = \{1, 2, 3, \ldots, p-1\}$을 생각합니다.

2단계: 각 원소에 $a$를 곱한 집합 $aS = \{a, 2a, 3a, \ldots, (p-1)a\}$를 만듭니다.

3단계: $aS$의 원소들을 $p$로 나눈 나머지도 모두 다르며, $\{1, 2, \ldots, p-1\}$의 순열을 이룹니다.

왜냐하면: 만약 $ia \equiv ja \pmod{p}$ ($1 \leq i < j \leq p-1$)이면, $\gcd(a, p) = 1$이므로 $i \equiv j \pmod{p}$인데 이는 모순입니다.

4단계: 양변의 곱을 비교하면

$$a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$$

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

5단계: $(p-1)!$과 $p$는 서로소이므로 양변을 $(p-1)!$로 나누면

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

3.2 증명 2: 오일러 정리 이용

오일러 정리: $\gcd(a, n) = 1$이면 $a^{\phi(n)} \equiv 1 \pmod{n}$

$p$가 소수이면 $\phi(p) = p - 1$이므로

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

3.3 증명 3: 이항정리 이용 ($a^p \equiv a \pmod{p}$ 형태)

수학적 귀납법을 사용합니다.

기저: $a = 1$일 때, $1^p = 1 \equiv 1 \pmod{p}$ ✓

귀납 가정: $a^p \equiv a \pmod{p}$라고 가정

귀납 단계: $(a+1)^p \equiv a+1 \pmod{p}$를 보이면 됩니다.

이항정리에 의해

$$(a+1)^p = \sum_{k=0}^{p} \binom{p}{k} a^k$$

$0 < k < p$일 때, $\binom{p}{k} = \frac{p!}{k!(p-k)!}$는 $p$의 배수입니다 ($p$는 소수이고 분자에는 $p$가 있지만 분모에는 없음).

따라서

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

4. 응용

4.1 거듭제곱의 나머지 계산

예제 2

$2^{100}$을 7로 나눈 나머지를 구하시오.

풀이:

7은 소수이고 $\gcd(2, 7) = 1$이므로 페르마의 소정리에 의해

$$2^6 \equiv 1 \pmod{7}$$

$100 = 6 \times 16 + 4$이므로

$$\begin{align} 2^{100} &= 2^{6 \times 16 + 4} \\ &= (2^6)^{16} \cdot 2^4 \\ &\equiv 1^{16} \cdot 16 \pmod{7} \\ &\equiv 16 \pmod{7} \\ &\equiv 2 \pmod{7} \end{align}$$

답: 2

4.2 역원 계산

페르마의 소정리를 이용하면 모듈로 소수에서 역원을 쉽게 계산할 수 있습니다.

$$a^{p-1} \equiv 1 \pmod{p} \Rightarrow a \cdot a^{p-2} \equiv 1 \pmod{p}$$

따라서 $a^{-1} \equiv a^{p-2} \pmod{p}$

예제 3

3의 모듈로 11에서의 역원을 구하시오.

풀이:

$$3^{-1} \equiv 3^{11-2} = 3^9 \pmod{11}$$

계산:

$$\begin{align} 3^2 &= 9 \\ 3^4 &= 81 \equiv 4 \pmod{11} \\ 3^8 &\equiv 16 \equiv 5 \pmod{11} \\ 3^9 &= 3^8 \cdot 3 \equiv 5 \cdot 3 = 15 \equiv 4 \pmod{11} \end{align}$$

검증: $3 \times 4 = 12 \equiv 1 \pmod{11}$ ✓

5. 연습문제

문제 1

다음을 계산하시오:

$5^{102} \bmod 103$
$7^{222} \bmod 11$

풀이 1

1) $5^{102} \bmod 103$

103은 소수이고 $\gcd(5, 103) = 1$이므로

$$5^{102} = 5^{103-1} \equiv 1 \pmod{103}$$

답: 1

2) $7^{222} \bmod 11$

11은 소수이고 $\gcd(7, 11) = 1$이므로

$$7^{10} \equiv 1 \pmod{11}$$

$222 = 10 \times 22 + 2$이므로

$$\begin{align} 7^{222} &= (7^{10})^{22} \cdot 7^2 \\ &\equiv 1^{22} \cdot 49 \pmod{11} \\ &\equiv 49 \pmod{11} \\ &\equiv 5 \pmod{11} \end{align}$$

답: 5

문제 2

$n = 2^{2^{100}} - 1$이 13의 배수임을 보이시오.

풀이 2

13은 소수이고 $\gcd(2, 13) = 1$이므로 페르마의 소정리에 의해

$$2^{12} \equiv 1 \pmod{13}$$

$2^{100}$을 12로 나눈 나머지를 구해야 합니다.

$2^{100} = 2^{96+4} = (2^2)^{48} \cdot 2^4 = 4^{48} \cdot 16$

12로 나눈 나머지만 필요하므로:

$$2^{100} = 2^{4 \times 25} \equiv 16^{25} \equiv 4^{25} \pmod{12}$$

더 간단하게, $2^2 = 4$, $2^3 = 8$, $2^4 = 16 \equiv 4 \pmod{12}$

$2^k \equiv 4 \pmod{12}$ (for $k \geq 2$)

따라서 $2^{100} \equiv 4 \pmod{12}$

그러므로

$$\begin{align} 2^{2^{100}} &\equiv 2^4 \pmod{13} \\ &= 16 \\ &\equiv 3 \pmod{13} \end{align}$$

따라서

$$2^{2^{100}} - 1 \equiv 3 - 1 = 2 \pmod{13}$$

이것은 13의 배수가 아닙니다. 문제를 다시 확인하겠습니다.

수정: 실제로 계산하면 13의 배수가 아닙니다. 만약 문제가 $2^{340} - 1$이었다면:

$$340 = 12 \times 28 + 4$$

$$2^{340} = (2^{12})^{28} \cdot 2^4 \equiv 1 \cdot 16 \equiv 3 \pmod{13}$$

페르마의 소정리를 정확히 적용하려면 지수가 $p-1$의 배수여야 합니다.

6. 페르마 소성 판정법

페르마의 소정리를 역으로 사용하여 소수를 판정할 수 있습니다 (완전하지는 않음):

페르마 소성 판정법

$n$이 소수인지 판정하려면:

$a$를 $1 < a < n$인 임의의 수로 선택
$a^{n-1} \bmod n$을 계산
만약 $a^{n-1} \not\equiv 1 \pmod{n}$이면 $n$은 합성수
만약 $a^{n-1} \equiv 1 \pmod{n}$이면 $n$은 아마도 소수

주의: 카마이클 수(Carmichael numbers)는 합성수이지만 모든 $\gcd(a,n)=1$에 대해 $a^{n-1} \equiv 1 \pmod{n}$를 만족합니다. 예: 561 = 3 × 11 × 17

7. 요약

페르마의 소정리: $p$가 소수이고 $\gcd(a, p) = 1$이면 $a^{p-1} \equiv 1 \pmod{p}$
동치 형태: 모든 $a$에 대해 $a^p \equiv a \pmod{p}$
응용: 거듭제곱의 나머지 계산, 역원 계산, 소성 판정
오일러 정리의 특수한 경우 ($\phi(p) = p-1$)
RSA 암호화 등 현대 암호학의 기초