III. 합동 · 7/16

오일러 φ 함수와 정리

φ 함수, 오일러 정리, 페르마의 일반화

읽음 0/0 갱신 2026-06-30

개요 — 동기·문제의식

Fermat 소정리는 $a^{p-1}\equiv1\pmod p$ 라는 깔끔한 결론을 주지만, 법이 소수일 때만 작동한다. 그런데 RSA 같은 실용적 응용에서는 법이 $N=pq$(두 소수의 곱)처럼 명백한 합성수다. 합성수 법에서도 "거듭제곱이 결국 $1$로 돌아오는 주기"가 존재할까? 답은 그렇다 — 다만 그 주기가 $n-1$ 이 아니라, $n$ 과 서로소인 수의 개수라는 새로운 양으로 바뀐다. 이 개수를 세는 함수가 Euler φ 함수이고, 그 주기성을 정당화하는 것이 Euler 정리다.

Euler 정리는 Fermat 소정리를 합성수 법으로 일반화한 것이며, $\varphi(N)=(p-1)(q-1)$ 이라는 단 하나의 숫자가 RSA 암호 전체의 수학적 심장이 된다(모듈러 거듭제곱과 RSA). φ 함수 자체도 소인수분해만 알면 곱셈 공식으로 즉시 계산되는, 정수론에서 가장 자주 등장하는 곱셈적 함수의 대표 선수다.

직관

$\bmod\,p$ ($p$ 소수)에서는 $0$ 을 제외한 모든 잔여류 $1,\dots,p-1$ 가 가역(역원을 가짐)이었다 — 그래서 Fermat의 주기가 깔끔하게 $p-1$ 이다. 그런데 $\bmod\,12$ 를 보면 $1,5,7,11$ 만 가역이고 $2,3,4,6,8,9,10$ 은 $12$ 와 공약수를 가져 가역이 아니다(예: $2x\equiv1\pmod{12}$ 는 해가 없다 — $2x$ 는 항상 짝수). 그래서 "거듭제곱의 순환"이 의미를 가지려면 가역인 잔여류들만 모은 집합 $\mathbb{Z}_n^\times=\{a: 1\le a\le n,\ \gcd(a,n)=1\}$ 위에서 생각해야 한다. 이 집합은 곱셈에 대해 닫혀 있고(가역원끼리 곱해도 가역) 군을 이루며, 그 원소 개수가 $\varphi(n)$ 이다. Euler 정리는 정확히 "이 군 안에서는 거듭제곱이 $\varphi(n)$ 주기로 순환한다"는 뜻이다 — Fermat의 $p-1$ 은 $\varphi(p)=p-1$ 인 특수한 경우일 뿐이다.

정의

Euler φ 함수(오일러 토션트 함수): 양의 정수 $m$ 에 대해¹ $$\varphi(m) = \#\{a : 1\le a\le m,\ \gcd(a,m)=1\} = |\mathbb{Z}_m^\times|$$ ($1,\dots,m$ 중 $m$과 서로소인 것의 개수, 즉 가역 잉여류의 개수).

$m$	$\varphi(m)$	$m$과 서로소인 수
$1$	$1$	$\{1\}$ (관례)
$5$	$4$	$1,2,3,4$
$6$	$2$	$1,5$
$12$	$4$	$1,5,7,11$

기본 공식. - 소수: $\varphi(p)=p-1$ ($1,\dots,p-1$ 전부 $p$ 와 서로소). - 소수거듭제곱: $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$. (왜: $1,\dots,p^k$ 중 $p$의 배수만 $p$ 와 공약수를 가지며 그 개수는 $p^{k-1}$개이므로 빼준다.) - 곱셈적: $\gcd(m,n)=1\ \Rightarrow\ \varphi(mn)=\varphi(m)\varphi(n)$ — 중국인의 나머지 정리의 직접 따름정리.⁴ - 일반 공식: $n=p_1^{e_1}\cdots p_r^{e_r}$ 이면 $$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)=\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$²

주요 정리

정리 (Euler 정리, Euler's Formula).³ $\gcd(a,m)=1$ 이면 $$a^{\varphi(m)}\equiv1\pmod m.$$

증명 보기

증명 스케치 (Fermat과 동일한 재배열 논법). $\mathbb{Z}_m^\times=\{r_1,\dots,r_{\varphi(m)}\}$ 을 $m$ 과 서로소인 잔여류 전체라 하자. $\gcd(a,m)=1$ 이면 사상 $r_i\mapsto ar_i\bmod m$ 은 $\mathbb{Z}_m^\times$ 를 자기 자신으로 보내는 재배열이다(곱 $ar_i$ 도 $m$ 과 서로소이고, $i\ne j\Rightarrow ar_i\not\equiv ar_j$ — Fermat 증명과 같은 소거법칙 논증). 양변의 곱을 비교: $$\prod_i(ar_i)\equiv\prod_i r_i\pmod m\ \Longrightarrow\ a^{\varphi(m)}\prod_i r_i\equiv\prod_i r_i\pmod m.$$ $\prod r_i$ 는 가역원들의 곱이라 $m$과 서로소이므로 소거하면 $a^{\varphi(m)}\equiv1\pmod m$. ∎

왜 가설 $\gcd(a,m)=1$ 이 필요한가. $a$ 가 $m$ 과 공약수를 가지면 $a$ 는 $\mathbb{Z}_m^\times$ 의 원소가 아니므로 재배열 논법 자체가 성립하지 않는다. 실제로 $a$ 가 가역이 아니면 $a^k$ 가 결코 $1$ 이 될 수 없다(가역원의 거듭제곱만 가역이고 $1$은 가역원이므로).

따름정리 (Fermat은 특수 경우). $m=p$ 소수면 $\varphi(p)=p-1$ 이므로 Euler 정리는 정확히 Fermat 소정리로 환원된다.

따름정리 (역원의 닫힌 형태). $\gcd(a,m)=1$ 이면 $a\cdot a^{\varphi(m)-1}\equiv a^{\varphi(m)}\equiv1\pmod m$ 이므로 $$a^{-1}\equiv a^{\varphi(m)-1}\pmod m.$$

따름정리 (φ의 약수 합 항등식). $\displaystyle\sum_{d\mid n}\varphi(d)=n$.⁵ 증명 아이디어. $1,\dots,n$ 을 $\gcd(k,n)=d$ 인 값별로 분류하면, $\gcd(k,n)=d$ 인 $k$ 의 개수는 정확히 $\varphi(n/d)$ 개다($k=d k'$, $\gcd(k',n/d)=1$). $d$ 가 $n$의 약수 전체를 훑으면 좌변이 $n$ 개의 정수 전체를 다 세게 되므로 합이 $n$.

예제

예제 1 (φ 계산, 소인수분해로). $\varphi(360)$: $360=2^3\cdot3^2\cdot5$. $\varphi(360)=\varphi(2^3)\varphi(3^2)\varphi(5)=(2^3-2^2)(3^2-3)(5-1)=4\cdot6\cdot4=96$.

예제 2 (Euler 정리로 큰 거듭제곱). $7^{1000}\bmod30$: $\varphi(30)=\varphi(2)\varphi(3)\varphi(5)=1\cdot2\cdot4=8$. $\gcd(7,30)=1$ → $7^8\equiv1\pmod{30}$. $1000=8\cdot125$ (나머지 $0$) → $7^{1000}=(7^8)^{125}\equiv1^{125}=1\pmod{30}$.

예제 3 (역원을 φ로). $\bmod9$ 에서 $2^{-1}$: $\varphi(9)=6$, 공식 $2^{-1}\equiv2^{5}=32\equiv32-27=5\pmod9$. 검산: $2\cdot5=10\equiv1\pmod9$ ✓.

예제 4 (RSA에 직결되는 계산). $p=11,\ q=13$ → $N=143$, $\varphi(N)=(11-1)(13-1)=10\cdot12=120$. $\gcd(a,143)=1$ 인 모든 $a$ 에 대해 $a^{120}\equiv1\pmod{143}$ — 이 $\varphi(N)=120$ 하나가 모듈러 거듭제곱과 RSA의 키 생성 전체를 떠받친다.

예제 5 (φ의 약수 합 검증). $n=12$: 약수 $1,2,3,4,6,12$, 각각 $\varphi(1)=1,\varphi(2)=1,\varphi(3)=2,\varphi(4)=2,\varphi(6)=2,\varphi(12)=4$. 합 $=1+1+2+2+2+4=12$ ✓.

예제 6 (φ가 곱셈적이지만 완전 곱셈적은 아님을 확인). $\varphi(2\cdot2)=\varphi(4)=2$, 그런데 $\varphi(2)\varphi(2)=1\cdot1=1\ne2$. $\gcd(2,2)=2\ne1$ 이라 곱셈성 공식의 가설(서로소)이 깨졌으므로 적용 불가 — 곱셈적 함수는 "서로소인 인수"에서만 곱으로 분해됨을 보여주는 반례.

흔한 오해와 함정

"φ는 완전 곱셈적이다" (틀림) — $\varphi(mn)=\varphi(m)\varphi(n)$ 은 $\gcd(m,n)=1$ 일 때만 성립한다. 예제 6처럼 공약수가 있으면 공식이 깨진다. 수론적 함수의 곱셈적/완전 곱셈적 구분 참조.
"$\varphi(p^k)=p^k-1$" 로 착각 — 틀림. $\varphi(p^k)=p^k-p^{k-1}$ 이다($p$의 배수만 빼야지, $1$만 빼면 안 된다). $\varphi(4)=4-2=2$ 이지 $3$이 아니다(실제로 $4$와 서로소인 건 $1,3$ 뿐 — 2개 맞음).
합성수 법에 Fermat의 $n-1$ 을 그대로 씀 — $\gcd(a,n)=1$ 이라도 합성수 $n$ 에서는 $a^{n-1}\equiv1$ 이 보장 안 된다(가설이 $\varphi(n)$ 으로 바뀐다). 예: $a=2,n=9$: $\varphi(9)=6$, $2^6=64\equiv1\pmod9$ ✓ 이지만 $2^{n-1}=2^8=256\equiv4\pmod9\ne1$.
$\gcd(a,m)=1$ 확인 누락 — Euler 정리는 $a$와 $m$이 서로소일 때만 성립. $a$가 $m$의 인수를 공유하면 결론이 거짓일 수 있다(가역원이 아니므로 $1$로 돌아올 수 없음).
φ(1)을 빠뜨리거나 잘못 정의 — 관례상 $\varphi(1)=1$ (공집합이 아니라 $\{1\}$ 자신이 자기와 서로소로 취급됨). 약수 합 항등식이 성립하려면 이 관례가 필요하다.

큰 그림 / 연결

Euler 정리는 합동산술의 거듭제곱 순환 현상을 가장 일반적인 형태로 정리한 것이며, 페르마 소정리은 법이 소수인 특수 경우다. φ 함수 자체는 중국인의 나머지 정리의 환 동형 $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ 으로부터 곱셈성을 물려받으며, 수론적 함수에서 다루는 $\tau,\sigma$ 같은 다른 곱셈적 함수들과 같은 "소인수분해 → 소수거듭제곱별 분해 → 곱"의 패턴을 공유한다. 계산 정수론에서 가장 중요한 응용은 모듈러 거듭제곱과 RSA: RSA의 안전성은 공개적으로 $N=pq$ 를 알아도 $\varphi(N)=(p-1)(q-1)$ 을 모르면(즉 $N$을 인수분해하지 못하면) 비밀 지수 $d$를 복원할 수 없다는 사실에 정확히 의존한다. 군론적으로는 $\varphi(n)=|\mathbb{Z}_n^\times|$ 가 그 군의 위수이고, Euler 정리는 유한군에서 원소의 위수가 군의 위수를 나눈다는 Lagrange 정리의 직접적 귀결이다(algebra 위키).

연습문제

$\varphi(100),\ \varphi(p^2),\ \varphi(2^{10})$ 을 구하라.
$3^{1000}\bmod100$ 을 Euler 정리로 구하라.
$\sum_{d\mid n}\varphi(d)=n$ 을 $n=18$ 로 확인하라.
$m>2$ 이면 $\varphi(m)$ 이 항상 짝수임을 보여라.
$\gcd(a,m)=1$ 일 때 $a$ 의 곱셈 역원을 $\varphi$ 로 표현하라.
$\varphi(n)=n/2$ 를 만족하는 $n$ 의 조건을 구하라.
$N=p q$ ($p,q$ 서로 다른 소수)일 때 $\varphi(N)$ 을 $N,p,q$ 로 표현하고, $p=17,q=23$ 일 때 값을 구하라.
$5^{2024}\bmod 24$ 를 Euler 정리로 구하라.

힌트 / 정답

$\varphi(100)=\varphi(4)\varphi(25)=2\cdot20=40$; $\varphi(p^2)=p^2-p=p(p-1)$; $\varphi(2^{10})=2^{10}-2^9=1024-512=512$.
$\varphi(100)=40$, $\gcd(3,100)=1$ → $3^{40}\equiv1\pmod{100}$; $1000=40\cdot25$ (나머지 $0$) → $3^{1000}\equiv1\pmod{100}$.
$18$ 의 약수 $1,2,3,6,9,18$; $\varphi=1,1,2,2,6,6$. 합 $=1+1+2+2+6+6=18$ ✓.
$m>2$ 이면 (a) $m$이 홀수 소인수 $p$를 가지면 $\varphi(p^{e})=p^{e-1}(p-1)$ 에서 $p-1$ 짝수이므로 곱 전체가 짝수; (b) $m=2^k$ ($k\ge2$)이면 $\varphi(2^k)=2^{k-1}$ 이 짝수. 두 경우 모두 짝수 인수를 가짐.
$a^{-1}\equiv a^{\varphi(m)-1}\pmod m$.
$\varphi(n)=n\prod(1-1/p)=n/2$ 가 되려면 $\prod(1-1/p)=1/2$ — $n=2^k$ ($k\ge1$)일 때 $\varphi(2^k)=2^{k-1}=n/2$. (소인수가 $\{2\}$ 하나뿐인 경우가 정확히 이 조건을 만족.)
$\varphi(N)=(p-1)(q-1)$; $p=17,q=23$: $\varphi(391)=16\cdot22=352$.
$\varphi(24)=\varphi(8)\varphi(3)=4\cdot2=8$. $\gcd(5,24)=1$ → $5^8\equiv1\pmod{24}$. $2024=8\cdot253$ (나머지 $0$) → $5^{2024}\equiv1\pmod{24}$.