≅현대대수학
I. 정수의 산술 · 3/16

ℤₙ의 구조

단원, ℤₚ는 체, 페르마·오일러·CRT

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

개요 — 동기·문제의식

$\mathbb{Z}_n$ 은 환이라는 건 알았지만($<a class="wl" href="congruence-and-modular-arithmetic.html">합동과 모듈러 산술</a>$), 그 안에서 나눗셈은 언제 가능한가? 즉 어떤 원소 $[a]$ 가 곱셈에 대해 역원을 가지는가? 이 질문의 답이 정확히 gcd에 있다는 것이 이 페이지의 핵심 통찰이다: $[a]$ 가 가역(단원)일 필요충분조건은 $\gcd(a,n)=1$. 이로부터 즉시 따라오는 것이 "$n=p$ 가 소수이면 $\{1,\dots,p-1\}$ 의 모든 수가 $p$ 와 서로소이므로 $\mathbb{Z}_p$ 의 0 아닌 모든 원소가 가역" — 즉 $\mathbb{Z}_p$ 는 체다. 유한체의 가장 단순한 예가 이렇게 손에 들어오고, 그 곱셈군의 구조를 분석하면 Fermat의 소정리와 Euler 정리가 거의 공짜로 따라 나온다(군론의 Lagrange 정리를 한 번만 적용하면 된다).

직관

"$[a]$ 가 가역"이라는 말은 "$\mathbb{Z}_n$ 에서 $a$ 로 나눌 수 있다"는 뜻이다. 정수 $\mathbb{Z}$ 에서는 $2$ 로 나누는 것이 항상 가능하지 않지만($1/2\notin\mathbb{Z}$), $\mathbb{Z}_n$ 처럼 유한한 "원형 시계" 구조에서는 사정이 다르다 — 시계를 $a$ 칸씩 계속 돌리면 결국 모든 칸을 방문하는지($\gcd(a,n)=1$), 아니면 일부만 순환하며 도는지($\gcd(a,n)>1$)가 가역성을 결정한다. 기하적으로, $\mathbb{Z}_n$ 의 원소를 정$n$각형의 꼭짓점으로 그리고 $a$ 를 곱하는 것을 "한 바퀴를 $a$ 배속으로 돌리는 회전"으로 본다면, $\gcd(a,n)=1$ 일 때만 그 회전이 모든 꼭짓점을 골고루(전단사로) 다시 방문한다 — 그렇지 않으면 일부 꼭짓점만 순환하는 부분궤도가 생긴다.

정의

환 $R$ 에서 $ab=ba=1$ 인 $b$ 가 있으면 $a$ 를 단원(unit, 가역원)이라 한다. $\mathbb{Z}_n$ 의 단원 전체를 $\mathbb{Z}_n^\times$ (또는 $U(n)$)로 쓴다. $\mathbb{Z}_n^\times$ 는 곱셈에 대해 닫혀 있고 군을 이룬다(아래 정리). Euler 피 함수 $\varphi(n)=|\mathbb{Z}_n^\times|$ = $1,\dots,n$ 중 $n$ 과 서로소인 수의 개수.

대상 정의
$\mathbb{Z}_n^\times$ $\mathbb{Z}_n$ 의 단원군, $\{[a]:\gcd(a,n)=1\}$
$\varphi(n)$ $\lvert\mathbb{Z}_n^\times\rvert$, $1\le a\le n$ 중 $\gcd(a,n)=1$ 인 개수
$\varphi(p)$ $p-1$ ($p$ 소수일 때)
$\varphi(p^k)$ $p^k-p^{k-1}$

주요 정리

정리 (단원 판정). $[a]\in\mathbb{Z}_n$ 이 단원 $\iff \gcd(a,n)=1$.1

증명 보기

증명. ($\Leftarrow$) $\gcd(a,n)=1$ 이면 Bezout(divisibility-and-primes)로 $ax+ny=1$ 인 정수 $x,y$ 존재. 법 $n$ 으로 보면 $ax\equiv1\pmod n$, 즉 $[x]=[a]^{-1}$ — $[a]$ 는 단원. ($\Rightarrow$) $[a]$ 가 단원이면 $ab\equiv1\pmod n$ 인 $b$ 가 존재, 즉 $ab-1=ny$ 인 $y$, 즉 $ab-ny=1$ — $a,n$ 의 선형결합이 $1$ 이므로 $\gcd(a,n)$ 은 $1$ 을 나누어야 해 $\gcd(a,n)=1$. ∎

정리 ($\mathbb{Z}_n^\times$ 는 군). $\mathbb{Z}_n^\times$ 는 곱셈에 대해 닫혀 있고(단원과 단원의 곱은 단원: $\gcd(a,n)=\gcd(b,n)=1\Rightarrow\gcd(ab,n)=1$, divisibility-and-primes 연습문제), 항등원 $[1]$ 을 가지며, 정의상 모든 원소가 역원을 가지므로 곱셈군이다.

정리 ($\mathbb{Z}_p$ 는 체). $p$ 가 소수 $\iff \mathbb{Z}_p$ 는 체 $\iff \mathbb{Z}_p$ 는 정역.2

증명 보기

증명. $p$ 소수이면 $1\le a\le p-1$ 인 모든 $a$ 에 대해 $\gcd(a,p)=1$(∵ $p$ 의 약수는 $1,p$ 뿐이고 $a<p$). 단원 판정에 의해 $[a]$ 가 단원, 즉 $\mathbb{Z}_p$ 의 0 아닌 모든 원소가 가역 → 체. 역으로 $n$ 이 합성수($n=ab$, $1<a,b<n$)라면 $[a][b]=[n]=[0]$ 인데 $[a],[b]\ne[0]$ — 영인자 존재 → 정역도 체도 아님. (체 ⇒ 정역은 일반 정리, 환과 체.) ∎

정리 (Fermat 소정리 / Euler 정리). $p$ 소수, $p\nmid a$ 이면 $a^{p-1}\equiv1\pmod p$. 일반화하면, $\gcd(a,n)=1$ 이면 $a^{\varphi(n)}\equiv1\pmod n$.3

증명 보기

증명 스케치. $\mathbb{Z}_n^\times$ 는 위수 $\varphi(n)$ 인 (유한) 군이고 $[a]\in\mathbb{Z}_n^\times$ (∵ $\gcd(a,n)=1$). 군론의 Lagrange 정리에 의해 원소의 위수(군에서 $a^k=1$ 이 되는 최소 $k$)는 군의 위수 $\varphi(n)$ 을 나눈다. 따라서 $a^{\varphi(n)}=([a]$ 의 위수$)^{(\varphi(n)/\text{위수})}=[1]^{(\cdots)}=[1]$. $p$ 가 소수면 $\varphi(p)=p-1$ 이므로 Fermat은 Euler의 특수 경우. ∎

정리 (중국인의 나머지 정리, CRT). $\gcd(m,n)=1$ 이면 사상 $\mathbb{Z}_{mn}\to\mathbb{Z}_m\times\mathbb{Z}_n$, $[a]_{mn}\mapsto([a]_m,[a]_n)$ 은 환 동형이다. 따라서 $\varphi$ 는 곱셈적(서로소인 인수에 대해): $\varphi(mn)=\varphi(m)\varphi(n)$.

증명 보기

증명 스케치. 이 사상이 잘 정의된 환 준동형임은 직접 확인. 단사: $[a]_m=[0]$, $[a]_n=[0]$ 이면 $m\mid a$, $n\mid a$, $\gcd(m,n)=1$ 이므로 $mn\mid a$ (divisibility and primes 연습문제 패턴), 즉 $[a]_{mn}=[0]$ — 핵이 자명. 정의역과 공역의 크기가 같으므로($mn$ 개) 단사이면 전단사. (이는 환 준동형의 제1동형정리로도 재유도된다 — 몫환과 동형정리.)

예제

예제 1 (단원군 직접 계산). $\mathbb{Z}_{10}^\times=\{[1],[3],[7],[9]\}$ ($1,3,7,9$ 가 $10$ 과 서로소), $\varphi(10)=4$. $[3]^{-1}=[7]$ (∵$3\cdot7=21\equiv1\pmod{10}$).

예제 2 ($\mathbb{Z}_5$ 의 역원표). $\mathbb{Z}_5$ 는 체: $[1]^{-1}=[1]$, $[2]^{-1}=[3]$(∵$2\cdot3=6\equiv1$), $[3]^{-1}=[2]$, $[4]^{-1}=[4]$(∵$4\cdot4=16\equiv1$).

예제 3 (Fermat 응용, 큰 거듭제곱). $2^{100}\bmod 13$: $13$ 소수이므로 $2^{12}\equiv1\pmod{13}$. $100=12\cdot8+4$ → $2^{100}=(2^{12})^8\cdot2^4\equiv1\cdot16\equiv3\pmod{13}$.

예제 4 ($\varphi$ 계산, 곱셈성 활용). $\varphi(360)=\varphi(2^3\cdot3^2\cdot5)=\varphi(2^3)\varphi(3^2)\varphi(5)=4\cdot6\cdot4=96$. (공식 $\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$: $\varphi(2^3)=2^2\cdot1=4$, $\varphi(3^2)=3\cdot2=6$, $\varphi(5)=4$.)

예제 5 (위수 직접 관찰). $\mathbb{Z}_7^\times=\{1,2,3,4,5,6\}$, $\varphi(7)=6$. $[3]$ 의 거듭제곱: $3,9\equiv2,6,18\equiv4,12\equiv5,15\equiv1$ — 위수 $6$(군 전체를 생성, $[3]$ 이 원시근). 반면 $[6]=[-1]$ 의 위수는 $2$ ($6^2=36\equiv1$). 둘 다 Lagrange가 보장하는 대로 $6$ 을 나눔($6\mid6$, $2\mid6$).

예제 6 (CRT 구체 적용). $\mathbb{Z}_{15}\cong\mathbb{Z}_3\times\mathbb{Z}_5$ ($\gcd(3,5)=1$). $[8]_{15}\mapsto([8]_3,[8]_5)=([2]_3,[3]_5)$. 역으로 $([2]_3,[3]_5)$ 에서 $[8]_{15}$ 를 복원하려면 $x\equiv2\pmod3,\ x\equiv3\pmod5$ 를 풀면(연립합동) $x=8$.

흔한 오해와 함정

큰 그림 / 연결

이 페이지는 합동산술을 군론·체론과 잇는 다리다. $\mathbb{Z}_n^\times$ 가 군이라는 사실 자체가 이후 군의 첫 비자명한 예 중 하나이고, Lagrange 정리를 가져와 Fermat/Euler를 증명하는 패턴은 "유한군의 위수가 부분군/원소 위수를 통제한다"는 원리의 전형적 응용이다(잉여류와 라그랑주 정리). $\mathbb{Z}_p^\times$ 가 사실은 순환군이라는 (이 페이지에서 증명하지 않은) 더 깊은 정리는 원시근의 존재로 이어지며, 수론(numbertheory 위키)의 이산로그·암호학 응용으로 직결된다. "유한 정역은 체"라는 정리는 euclidean pid ufd에서 유한환의 구조론으로 더 일반화되고, $\mathbb{Z}_p$ 가 체라는 사실 자체가 몫환이 체가 되는 가장 단순한 사례다($\mathbb{Z}/(p)$, $(p)$ 가 극대 아이디얼).

연습문제

  1. $\mathbb{Z}_{12}^\times$ 를 모두 나열하고 $\varphi(12)$ 를 구하라.
  2. $\mathbb{Z}_{11}$ 에서 $[7]^{-1}$ 을 구하라.
  3. $3^{1000}\bmod 7$ 을 구하라.
  4. $\mathbb{Z}_n$ 이 정역이면 체임을 보여라(유한 정역은 체).
  5. $\varphi(100)$ 을 구하라.
  6. $\mathbb{Z}_8^\times$ 의 각 원소의 위수를 구하고, $\mathbb{Z}_8^\times$ 가 순환군이 아님을 보여라.
  7. $a^{13}\equiv a\pmod{13}$ 이 모든 정수 $a$ 에 대해 성립함을 보여라(Fermat의 일반형).
  8. $\mathbb{Z}_{21}^\times\cong\mathbb{Z}_3^\times\times\mathbb{Z}_7^\times$ 임을 (CRT로) 설명하고 양변의 위수를 비교해 $\varphi(21)=\varphi(3)\varphi(7)$ 을 확인하라.
정답·힌트
  1. $\{1,5,7,11\}$, $\varphi(12)=4$.
  2. $7\cdot8=56\equiv1\pmod{11}$ → $[7]^{-1}=[8]$.
  3. $3^6\equiv1\pmod7$, $1000=6\cdot166+4$ → $3^{1000}\equiv3^4=81\equiv4\pmod7$.
  4. 유한 정역 $R$, $a\ne0$: 사상 $x\mapsto ax$ 가 단사(영인자 없음: $ax=ax'\Rightarrow a(x-x')=0\Rightarrow x=x'$)→유한집합에서 단사는 전사→$ax=1$ 인 $x$ 존재. 그러므로 모든 0 아닌 원소 가역 → 체.
  5. $\varphi(100)=\varphi(2^2)\varphi(5^2)=(4-2)(25-5)=2\cdot20=40$.
  6. $\mathbb{Z}_8^\times=\{1,3,5,7\}$. $3^2=9\equiv1$, $5^2=25\equiv1$, $7^2=49\equiv1$ — 모든 원소의 위수가 $1$ 또는 $2$. 위수 $4$($=\varphi(8)$)인 원소가 없으므로 순환군 아님(클라인 4원군과 동형).
  7. $13$ 소수. $13\mid a$ 이면 양변 $\equiv0$. $13\nmid a$ 이면 Fermat 소정리로 $a^{12}\equiv1\pmod{13}$, 양변에 $a$ 를 곱하면 $a^{13}\equiv a$.
  8. CRT(환 동형 $\mathbb{Z}_{21}\cong\mathbb{Z}_3\times\mathbb{Z}_7$)를 단원군으로 제한하면 $\mathbb{Z}_{21}^\times\cong\mathbb{Z}_3^\times\times\mathbb{Z}_7^\times$(환 동형은 단원을 단원으로 보냄). 위수 비교: $\varphi(21)=|\mathbb{Z}_{21}^\times|=|\mathbb{Z}_3^\times||\mathbb{Z}_7^\times|=\varphi(3)\varphi(7)=2\cdot6=12$.

관련 개념

  1. 원전 소개 — Hungerford §2.3 [synthesis] — $[a]$ 가 $\mathbb{Z}_n$ 의 단원 $\iff \gcd(a,n)=1$, Bezout를 이용한 증명. ↩

  2. 원전 소개 — Hungerford §2.3 [synthesis] — $\mathbb{Z}_p$ 는 $p$ 소수일 때 체(=정역); 합성수면 영인자 존재. ↩

  3. 원전 소개 — Hungerford §2.3 / ch.14 [synthesis] — Fermat 소정리, Euler 정리, 중국인의 나머지 정리; 군론(Lagrange)을 이용한 증명. ↩