1.4 오일러 & 페르마 정리 실전 예제 10선
지수 감소의 마법인 $a^{\phi(m)} \equiv 1 \pmod m$을 활용하여 거대 지수 연산과 모듈러 역원을 구하는 과정을 상세히 풀이합니다.
Ex 1. 페르마 소정리와 지수 감소
문제: $3^{202} \pmod{101}$ 의 값을 구하시오. (단, 101은 소수)
$p=101$은 소수이고 $\gcd(3, 101)=1$이므로 페르마 소정리에 의해:
$3^{100} \equiv 1 \pmod{101}$
$3^{202} = (3^{100})^2 \times 3^2 \equiv 1^2 \times 9 = 9 \pmod{101}$
$\therefore$ 답은 9이다.
Ex 2. 오일러 파이 함수 실전
문제: $\phi(72)$를 구하고, 그 의미를 서술하시오.
$72 = 2^3 \times 3^2$ 이다.
$\phi(72) = 72 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 72 \times \frac{1}{2} \times \frac{2}{3} = 24$
의미: 1부터 72까지의 정수 중 72와 서로소인 정수는 정확히 24개 존재한다.
Ex 3. 오일러 정리 응용
문제: $7^{100} \pmod{48}$ 의 값을 구하시오.
$\gcd(7, 48)=1$ 이다.
$48 = 2^4 \times 3 \implies \phi(48) = 48 \times \frac{1}{2} \times \frac{2}{3} = 16$
오일러 정리에 의해 $7^{16} \equiv 1 \pmod{48}$ 이다.
$100 = 16 \times 6 + 4$ 이므로, $7^{100} \equiv (7^{16})^6 \times 7^4 \equiv 1^6 \times 7^4 \pmod{48}$
$7^2 = 49 \equiv 1 \pmod{48}$ 이므로 $7^4 \equiv 1^2 = 1 \pmod{48}$
$\therefore$ 답은 1이다.
Ex 4. 마지막 두 자리수 (Mod 100)
문제: $3^{1000}$ 의 마지막 두 자릿수를 구하시오.
마지막 두 자리는 법 100에 대한 나머지를 구하는 것과 같다.
$\gcd(3, 100)=1$ 이고 $\phi(100) = 100(1-1/2)(1-1/5) = 40$
오일러 정리에 의해 $3^{40} \equiv 1 \pmod{100}$
$3^{1000} = (3^{40})^{25} \equiv 1^{25} = 1 \pmod{100}$
$\therefore$ 마지막 두 자리는 01이다.
Ex 5. 곱셈군에서의 역원
문제: $5x \equiv 1 \pmod{12}$ 를 만족하는 $x$를 오일러 정리를 이용해 구하시오.
$\gcd(5, 12)=1$ 이고 $\phi(12) = 12(1/2)(2/3) = 4$
오일러 정리에 의해 $5^{\phi(12)} = 5^4 \equiv 1 \pmod{12}$
따라서 $5 \times 5^3 \equiv 1 \pmod{12}$ 이므로 $x \equiv 5^3 \pmod{12}$
$5^3 = 125 = 12 \times 10 + 5 \equiv 5 \pmod{12}$
$\therefore x \equiv 5 \pmod{12}$
Ex 6. 지수 위의 지수 연산
문제: $7^{7^7} \pmod{10}$ 의 값을 구하시오.
$\gcd(7, 10)=1$ 이고 $\phi(10) = 4$ 이다.
따라서 $7^k \pmod{10}$ 을 구할 때 지수 $k$는 법 4에 대해 생각한다.
지수 $7^7 \pmod 4$: $7 \equiv -1 \pmod 4 \implies 7^7 \equiv (-1)^7 = -1 \equiv 3 \pmod 4$
$\therefore 7^{7^7} \equiv 7^3 \pmod{10}$
$7^3 = 343 \equiv 3 \pmod{10}$
$\therefore$ 답은 3이다.
Ex 7. 증명 - $n^{13} - n$ 은 항상 2730의 배수인가?
문제: 모든 정수 $n$에 대해 $13 \mid (n^{13} - n)$ 임을 보이시오.
페르마의 소정리 변형인 $n^p \equiv n \pmod p$를 이용한다.
$p=13$은 소수이므로, 임의의 정수 $n$에 대해 $n^{13} \equiv n \pmod{13}$ 이 성립한다.
따라서 $n^{13} - n$은 항상 13으로 나누어 떨어진다. (2730은 $2 \times 3 \times 5 \times 7 \times 13$ 이므로 각 소수별로 증명하면 전체 증명이 가능함)
Ex 8. 윌슨의 정리와 소수
문제: 소수 $p$에 대해 $(p-1)! \equiv -1 \pmod p$ 임을 이용해 $6! \pmod 7$을 구하시오.
$p=7$은 소수이다. 윌슨의 정리에 의해 $(7-1)! = 6! \equiv -1 \pmod 7$ 이다.
$-1 \equiv 6 \pmod 7$ 이므로 나머지는 6이다.
이는 곱셈군 $\{1, 2, 3, 4, 5, 6\}$ 에서 자기 자신의 역원인 원소($1, 6$)를 제외한 나머지들이 쌍을 이루어 곱이 1이 되기 때문이다.
Ex 9. 오일러 정리의 기하학적 의미
문제: $n > 1$ 일 때, $n$과 서로소인 $n$ 미만 모든 정수의 합은 $\frac{n \phi(n)}{2}$ 임을 보이시오.
$\gcd(a, n)=1$ 이면 $\gcd(n-a, n)=1$ 임을 이용한다.
서로소인 수들을 $x_1, x_2, \dots, x_{\phi(n)}$ 이라 하면, 이들을 거꾸로 나열한 $n-x_i$들도 같은 집합이다.
$2S = (x_1 + (n-x_1)) + (x_2 + (n-x_2)) + \dots = n \times \phi(n)$
$\therefore S = \frac{n \phi(n)}{2}$
Ex 10. 공개키 암호 원리
문제: $p=3, q=11, e=3$ 일 때, $M^e \equiv C \pmod{pq}$ 에서 암호문 $C=8$을 복호화하기 위한 지수 $d$를 구하시오.
$n = 33, \phi(n) = (3-1)(11-1) = 20$
복호화 지수 $d$는 $ed \equiv 1 \pmod{\phi(n)}$ 을 만족해야 한다.
$3d \equiv 1 \pmod{20} \implies 3d = 21 \implies d = 7$
복호화 과정: $M \equiv 8^7 \pmod{33} \dots$ (오일러 정리에 의해 원래 메시지 복원 가능)