이 글은 오일러의 정리(Euler’s theorem)를 빠르게 적용하는 법을 예제 중심으로 정리한 자료입니다. 모듈러 연산에서 큰 거듭제곱을 다룰 때 지수를 줄이는 핵심 아이디어, 오일러 피함수 \(\varphi(n)\) 계산법, 중국인의 나머지 정리(CRT)와의 결합, 그리고 RSA 장난감 예시까지 “시험·코딩 면접·CTF·개발 실무”에서 곧장 써먹을 수 있도록 구성했습니다. 본문은 모두 HTML 코드 형태이며, 실행은 고려하지 않습니다.
오일러의 정리: 정의와 공식
정수 \(n\)과 \(a\)가 서로소일 때(\(\gcd(a,n)=1\)), 다음이 성립합니다.
\[ a^{\varphi(n)} \equiv 1 \pmod{n} \]
\(\varphi(n)\)는 오일러 피함수로, \(1\)부터 \(n\)까지의 정수 중 \(n\)과 서로소인 수의 개수입니다. 이 정리는 소수 모듈러에 대한 페르마의 소정리 \(\big(a^{p-1}\equiv 1\ (\mathrm{mod}\ p)\big)\)를 합성수로 일반화한 형태입니다. 핵심은 “지수를 \(\varphi(n)\)로 나눈 나머지로 줄여도 결과가 동일하다”는 점입니다.
오일러 피함수 \(\varphi(n)\) 계산법
\(n\)을 소인수분해하여 \(n=\prod_i p_i^{k_i}\)라면 다음이 성립합니다.
\[ \varphi(n) = n \prod_{p_i \mid n}\!\left(1-\frac{1}{p_i}\right) \]
예시로 \(\varphi(1000)=1000\!\left(1-\frac{1}{2}\right)\!\left(1-\frac{1}{5}\right)=1000\cdot\frac{1}{2}\cdot\frac{4}{5}=400\), \(\varphi(77)=77\!\left(1-\frac{1}{7}\right)\!\left(1-\frac{1}{11}\right)=77\cdot\frac{6}{7}\cdot\frac{10}{11}=60\)을 손쉽게 얻을 수 있습니다.
문제 풀이 전략(체크리스트)
첫째, \(\gcd(a,n)=1\)인지 확인합니다. 서로소가 아니라면 오일러의 정리를 그대로 쓰면 안 되며, CRT로 법을 쪼개거나(예: \(n=2^k 5^m\) 분해) 지수 승수 올리기 기법 등을 사용합니다.
둘째, \(\varphi(n)\)를 구한 뒤 지수를 \(\bmod\ \varphi(n)\)로 축소합니다. 즉 \(a^e \bmod n\)은 \(a^{\,e \bmod \varphi(n)} \bmod n\)과 같습니다(단, 서로소 가정).
셋째, 커다란 모듈러스는 CRT로 작은 소수 거듭제곱 모듈러들로 나눠 계산 후 합칩니다. 예를 들어 \(n=8\cdot 125=1000\)이면 \(\bmod\ 8\)과 \(\bmod\ 125\)로 계산 후 해를 맞춥니다.
넷째, “거듭제곱 분할 제곱(빠른 거듭제곱)”을 기본으로 사용합니다. 지수의 이진 분해를 이용해 \(O(\log e)\)에 계산합니다.
예제 1: 기본형 — \(3^{100}\bmod 35\)
문제: \(3^{100}\bmod 35\)를 구하라.
풀이: \(35=5\cdot 7\), \(\varphi(35)=(5-1)(7-1)=24\). \(\gcd(3,35)=1\)이므로 오일러의 정리 적용 가능, \(3^{24}\equiv 1\ (\mathrm{mod}\ 35)\). 따라서 \(100\bmod 24=4\)이므로 \(3^{100}\equiv 3^4\ (\mathrm{mod}\ 35)\). \(3^4=81\equiv 11\ (\mathrm{mod}\ 35)\). 정답은 \(11\).
포인트: 피함수로 지수를 줄여 연산량을 크게 줄였습니다.
예제 2: CRT 결합 — \(7^{2222}\bmod 1000\)
문제: \(7^{2222} \bmod 1000\)을 구하라.
풀이 1(직접 \(\varphi\)로 축소): \(\varphi(1000)=400\). \(\gcd(7,1000)=1\)이므로 \(7^{400}\equiv 1\). \(2222\bmod 400=222\)이므로 \(7^{222} \bmod 1000\)만 계산하면 됩니다. 하지만 여전히 크므로 CRT를 병행합니다.
풀이 2(CRT): \(1000=8\cdot 125\). 먼저 \(\bmod 8\): \(7\equiv -1\Rightarrow 7^{2222}\equiv (-1)^{2222}=1\). 다음 \(\bmod 125\): \(\varphi(125)=100\), \(2222\bmod 100=22\)이므로 \(7^{22}\bmod 125\)만 구하면 됩니다. 제곱 반복로 \(7^2=49\), \(7^4=49^2=2401\equiv 26\), \(7^8=26^2=676\equiv 51\), \(7^{16}=51^2=2601\equiv 101\)를 얻고 \(7^{22}=7^{16}\cdot 7^4\cdot 7^2\equiv 101\cdot 26\cdot 49\equiv 1\cdot 49\equiv 49\ (\mathrm{mod}\ 125)\).
이제 연립합동을 풉니다. \(x\equiv 1\ (\mathrm{mod}\ 8)\), \(x\equiv 49\ (\mathrm{mod}\ 125)\). \(x=49+125k\)를 \(\bmod 8\)로 보면 \(49\equiv 1\), \(125\equiv 5\)이므로 \(1+5k\equiv 1\Rightarrow k\equiv 0\ (\mathrm{mod}\ 8)\). 최솟값 \(k=0\)에서 \(x=49\). 따라서 \(7^{2222}\bmod 1000=49\).
포인트: \(\bmod 8\)과 \(\bmod 125\)로 쪼개면 계산이 극적으로 쉬워집니다.
예제 3: \(\varphi\)로 지수 줄이기 — \(2^{120}\bmod 105\)
문제: \(2^{120}\bmod 105\)를 구하라.
풀이: \(105=3\cdot 5\cdot 7\), \(\varphi(105)=105\!\left(1-\frac{1}{3}\right)\!\left(1-\frac{1}{5}\right)\!\left(1-\frac{1}{7}\right)=48\). \(\gcd(2,105)=1\)이므로 \(2^{48}\equiv 1\). \(120\bmod 48=24\)이므로 \(2^{120}\equiv 2^{24}\ (\mathrm{mod}\ 105)\). CRT로 검산하면 \(\bmod 3\)에서 \(2^{24}\equiv 1\), \(\bmod 5\)에서 \(2^{24}\equiv 1\), \(\bmod 7\)에서 \(2^{24}\equiv 1\)이므로 최종 \(1\). 정답은 \(1\).
포인트: 지수 축소와 CRT가 완벽히 맞물립니다.
예제 4: 서로소 아님 — \(12^{100}\bmod 36\)
문제: \(12^{100}\bmod 36\)을 구하라.
풀이: \(\gcd(12,36)\neq 1\)이므로 오일러의 정리를 바로 쓰지 않습니다. CRT로 \(36=4\cdot 9\)를 나눕니다. \(\bmod 4\)에서는 \(12\equiv 0\Rightarrow 12^{100}\equiv 0\). \(\bmod 9\)에서는 \(12\equiv 3\), \(3^2=9\equiv 0\)이므로 \(3^{100}\equiv 0\). 연립합동은 \(x\equiv 0\ (\mathrm{mod}\ 4)\), \(x\equiv 0\ (\mathrm{mod}\ 9)\)이므로 \(x\equiv 0\ (\mathrm{mod}\ 36)\). 정답은 \(0\).
포인트: 서로소 조건이 깨지면 곧장 CRT나 지수 올리기 기법을 택합니다.
예제 5: 실전형 — \(10^{2025}\bmod 77\)
문제: \(10^{2025}\bmod 77\)을 구하라.
풀이: \(\varphi(77)=60\), \(\gcd(10,77)=1\). 따라서 \(10^{60}\equiv 1\)이고 \(2025\bmod 60=45\). 즉 \(10^{2025}\equiv 10^{45}\ (\mathrm{mod}\ 77)\). CRT로 \(\bmod 7\)과 \(\bmod 11\)에서 계산합니다. \(\bmod 7\)에서 \(10\equiv 3\), \(\varphi(7)=6\)이므로 \(3^{45}\equiv 3^{(45\bmod 6)=3}\equiv 27\equiv 6\). \(\bmod 11\)에서 \(10\equiv -1\), \((-1)^{45}\equiv -1\equiv 10\). 이제 \(x\equiv 6\ (\mathrm{mod}\ 7)\), \(x\equiv 10\ (\mathrm{mod}\ 11)\)을 풀면 \(x=10+11k\)가 \(6\ (\mathrm{mod}\ 7)\)을 만족해야 하므로 \(10\equiv 3\), \(11k\equiv 3\Rightarrow 4k\equiv 3\ (\mathrm{mod}\ 7)\). \(4^{-1}\equiv 2\)이므로 \(k\equiv 6\). \(x=10+66=76\). 정답은 \(76\).
포인트: \(\varphi\) 축소 후 CRT로 단숨에 끝냅니다.
예제 6: 토이 RSA — 오일러로 암복호 역관계 확인
문제: 작은 RSA를 구성해 암호화와 복호화가 성립함을 보여라.
구성: \(p=11, q=13 \Rightarrow n=143\), \(\varphi(n)=(p-1)(q-1)=120\). 공개 지수 \(e=7\)을 택하고 \(ed\equiv 1\ (\mathrm{mod}\ 120)\)인 \(d\)를 구하면 \(7\cdot 103=721\equiv 1\)이므로 \(d=103\). 평문 \(m=42\).
암호화: \(c\equiv m^e \equiv 42^7\ (\mathrm{mod}\ 143)\). CRT로 \(\bmod 11\)에서 \(42\equiv 9\), \(9^7\equiv 4\). \(\bmod 13\)에서 \(42\equiv 3\), \(3^7\equiv 3\). 연립합동 \(x\equiv 4\ (\mathrm{mod}\ 11)\), \(x\equiv 3\ (\mathrm{mod}\ 13)\)의 해는 \(x=81\). 즉 \(c=81\).
복호화: \(m’\equiv c^d \equiv 81^{103}\ (\mathrm{mod}\ 143)\). \(\bmod 11\)에서 \(81\equiv 4\), \(\varphi(11)=10\Rightarrow 4^{103}\equiv 4^{3}\equiv 64\equiv 9\). \(\bmod 13\)에서 \(81\equiv 3\), \(\varphi(13)=12\Rightarrow 3^{103}\equiv 3^{7}\equiv 3\). 이는 \(42\equiv 9\ (\mathrm{mod}\ 11)\), \(42\equiv 3\ (\mathrm{mod}\ 13)\)과 일치하므로 \(m’=42\) 복원. 오일러의 정리가 암복호 역관계를 보장함을 확인했습니다.
포인트: RSA의 핵심은 \(\gcd(m,n)=1\)인 평문에 대해 \(m^{ed}\equiv m\)이 된다는 사실로, 바로 오일러의 정리에 기반합니다.
예제 7: 커다란 지수 — \(\gcd\) 점검과 지수 축소
문제: \(17^{123456}\bmod 221\)을 구하라.
풀이: \(221=13\cdot 17\). \(\gcd(17,221)\neq 1\)이므로 오일러의 정리를 직접 쓰면 안 됩니다. CRT로 분해합니다. \(\bmod 13\)에서 \(17\equiv 4\), \(\varphi(13)=12\Rightarrow 4^{123456}\equiv 4^{(123456\bmod 12)=0}\equiv 1\). \(\bmod 17\)에서는 \(17\equiv 0\Rightarrow 0^{123456}\equiv 0\) (지수는 양의 정수). 연립합동은 \(x\equiv 1\ (\mathrm{mod}\ 13)\), \(x\equiv 0\ (\mathrm{mod}\ 17)\). \(x=17k\)가 \(1\ (\mathrm{mod}\ 13)\)을 만족해야 하므로 \(17k\equiv 1\Rightarrow 4k\equiv 1\ (\mathrm{mod}\ 13)\). \(4^{-1}\equiv 10\)이므로 \(k\equiv 10\). \(x=170\). 정답은 \(170\).
포인트: 서로소가 깨진 경우에도 CRT가 답을 엽니다.
예제 8: 1 감소 패턴 — \((a^{\varphi(n)}-1)\) 구조 이용
문제: \(9^{99}\bmod 35\)를 구하라.
풀이: \(\varphi(35)=24\), \(\gcd(9,35)=1\). \(9^{24}\equiv 1\)이므로 \(9^{96}\equiv 1\). 따라서 \(9^{99}\equiv 9^{96}\cdot 9^3\equiv 9^3\). \(9^2=81\equiv 11\), \(9^3\equiv 11\cdot 9=99\equiv 29\). 정답은 \(29\).
포인트: 지수를 배수와 나머지로 쪼개면 계산이 즉시 간단해집니다.
예제 9: 두 모듈러 동시 계산 — 테크닉 묶음
문제: \(a=13\), \(n=840=2^3\cdot 3\cdot 5\cdot 7\)일 때 \(13^{2024}\bmod 840\)을 구하라.
풀이: \(\gcd(13,840)=1\), \(\varphi(840)=840\!\left(1-\frac{1}{2}\right)\!\left(1-\frac{1}{3}\right)\!\left(1-\frac{1}{5}\right)\!\left(1-\frac{1}{7}\right)=840\cdot\frac{1}{2}\cdot\frac{2}{3}\cdot\frac{4}{5}\cdot\frac{6}{7}=192\). 따라서 \(13^{192}\equiv 1\). \(2024\bmod 192=2024-192\cdot 10=2024-1920=104\). 즉 \(13^{2024}\equiv 13^{104}\). 이제 CRT로 \(\bmod 8,3,5,7\)에 대해 빠른 거듭제곱으로 값을 구해 합치면 끝입니다. 예를 들어 \(\bmod 8\)에서 \(13\equiv 5\), \(5^2\equiv 1\)이므로 \(5^{104}\equiv 1\); \(\bmod 3\)에서 \(13\equiv 1\Rightarrow 1\); \(\bmod 5\)에서 \(13\equiv 3\), \(3^4\equiv 1\Rightarrow 104\bmod 4=0\Rightarrow 1\); \(\bmod 7\)에서 \(13\equiv 6\equiv -1\Rightarrow (-1)^{104}=1\). 네 모듈러 모두 1이므로 결론적으로 \(13^{2024}\equiv 1\ (\mathrm{mod}\ 840)\).
포인트: \(\varphi(n)\) 축소와 각 소수 거듭제곱 모듈러의 순환성을 함께 보면 해가 한눈에 보입니다.
예제 10: 지수 자체가 큰 합동 — 지수에 \(\varphi\) 한 번 더
문제: \(a^{\,b^{\,c}}\bmod n\) 꼴에서 \(a=7\), \(b=12\), \(c=34\), \(n=77\)일 때 값을 구하라.
풀이: \(\gcd(7,77)=1\), \(\varphi(77)=60\). 핵심은 지수 \(b^c\)를 \(\bmod \varphi(n)=60\)으로 먼저 줄이는 것입니다. \(\gcd(12,60)\neq 1\)이지만 여기서는 \(12^{34}\bmod 60\)을 직접 계산할 수 있습니다. \(12\equiv 0\ (\mathrm{mod}\ 3)\)이므로 \(\bmod 3\)에서 0, \(\bmod 20\)에서 \(12^2=144\equiv 4\), \(12^4\equiv 16\), \(12^8\equiv 16^2=256\equiv 16\), 지수가 커져도 주기는 짧습니다. 실제로 \(12^{34}\bmod 60=16\)임을 얻으면, 최종 문제는 \(7^{16}\bmod 77\)로 축소됩니다. CRT로 \(\bmod 7\)에서 \(0\), \(\bmod 11\)에서 \(7^{10}\equiv 1\), \(16\bmod 10=6\Rightarrow 7^6\equiv 4\). 연립합동 \(x\equiv 0\ (\mathrm{mod}\ 7)\), \(x\equiv 4\ (\mathrm{mod}\ 11)\)을 풀면 \(x=49\). 따라서 정답은 \(49\).
포인트: 지수가 거듭제곱일 때는 지수의 지수를 \(\varphi(n)\)로 한 번 더 줄이면 게임이 쉬워집니다.
자주 하는 실수와 팁
서로소 조건을 빼먹는 실수가 가장 많습니다. \(\gcd(a,n)\neq 1\)이면 오일러의 정리를 직접 적용할 수 없습니다. 이때는 CRT로 소수 거듭제곱 모듈러에 대해 각각 처리하거나, 영원이 빨리 되는 요인(예: \(a\equiv 0\ (\mathrm{mod}\ p)\))을 감지해 계산을 단순화합니다.
\(\varphi(n)\)를 잘못 계산하는 실수도 잦습니다. 특히 중복 소인수에 유의하십시오. \(p^k\)에 대해 \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\)을 기억하면 실수를 줄일 수 있습니다.
빠른 거듭제곱에서 모듈러를 중간마다 적용하지 않으면 정수 오버플로우 혹은 수가 감당 안 될 정도로 커집니다. 매 곱셈마다 \(\bmod n\)을 취하는 습관이 중요합니다.
CRT에서 역원을 구할 때는 “작은 모듈러일수록 표를 외우기” 또는 확장 유클리드 알고리즘을 사용하세요. 손계산에서는 작은 수의 역원을 외우는 것이 시간을 절약합니다.
추가 미니 연습문제(정답만)
\(5^{2024}\bmod 21= \ 5^{(2024\bmod 12)=8}\equiv 16\). \(9^{123}\bmod 40\)은 \(\gcd(9,40)=1\), \(\varphi(40)=16\), \(123\bmod 16=11\), 결과는 \(9^{11}\bmod 40=9\). \(8^{2025}\bmod 63\)은 \(\gcd(8,63)=1\), \(\varphi(63)=36\), \(2025\bmod 36=9\), \(8^9\bmod 63=8\).
연습으로 위 세 문제를 CRT로도 각각 재확인해 보세요. 두 방식이 같은 답으로 합쳐지는 경험이 큰 자신감을 줍니다.
결론
오일러의 정리 정의 요약: \(\gcd(a,n)=1\)이면 \(a^{\varphi(n)}\equiv 1\ (\mathrm{mod}\ n)\). 핵심은 큰 지수를 \(\varphi(n)\)로 나눈 나머지로 줄여 계산량을 급격히 줄이는 데 있습니다.
\(\varphi(n)\) 계산 요약: 소인수분해 후 \(\varphi(n)=n\prod_{p\mid n}(1-\frac{1}{p})\). \(p^k\) 꼴은 \(\varphi(p^k)=p^{k-1}(p-1)\)를 즉시 적용하세요.
전략 요약: 서로소 확인 → 지수 \(\bmod \varphi(n)\) 축소 → 빠른 거듭제곱 → 필요하면 CRT로 분해·합치기. 이 4단계를 습관화하면 거의 모든 계산이 손에 잡힙니다.
예제 종합 요약: 예제 1은 기본 축소(정답 11), 예제 2는 CRT 결합(정답 49), 예제 3은 \(\varphi\) 축소로 \(1\) 도출, 예제 4는 서로소가 아니므로 CRT로 \(0\) 도출, 예제 5는 축소+CRT로 \(76\), 예제 6은 RSA의 역관계 확인, 예제 7은 비서로소에서도 CRT로 해결, 예제 8·9는 주기·구조 파악으로 계산 단축, 예제 10은 지수의 지수 축소 사례입니다.
마지막 한 줄: 큰 수의 모듈러 거듭제곱은 무작정 곱하지 말고, 오일러의 정리와 CRT로 “작게 나누고, 빨리” 계산하세요. 그러면 시험과 실무 모두에서 확실히 빨라집니다.