I. 정수의 산술 · 2/16

합동과 모듈러 산술

합동류, ℤₙ의 연산

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

개요 — 동기·문제의식

"나머지가 같다"는 일상적 관찰을 동치관계로 격상시키면 강력한 일이 벌어진다 — 정수 전체를 유한 개($n$개)의 묶음으로 쪼개고, 그 묶음들 사이에 새로운 덧셈·곱셈을 정의해 완전히 새로운 유한 대수 구조 $\mathbb{Z}_n$ 을 만들 수 있다. 이것이 이 책 전체를 관통하는 "몫으로 새 구조 만들기" 기법의 첫 등장이다 — 정수의 무한한 복잡성을 유한한 대상으로 압축하면서도 덧셈·곱셈의 대수적 성질은 그대로 물려받는다. 이 아이디어는 나중에 임의의 환에서 아이디얼로 몫환을 만드는 일반 이론으로, 군에서는 정규부분군으로 몫군을 만드는 이론으로 정확히 평행하게 일반화된다.

직관

합동을 이해하는 가장 직관적인 그림은 시계 산술이다 — 12시간제 시계에서 $9$ 시에서 $5$ 시간 뒤는 $2$ 시($9+5=14\equiv2\pmod{12}$). "$14$ 시"와 "$2$ 시"는 다른 숫자이지만 시계 위에서는 같은 위치를 가리킨다. 합동 $a\equiv b\pmod n$ 은 정확히 이 관계를 형식화한다: $a$ 와 $b$ 가 $n$ 으로 나눈 나머지가 같다는 것은, 수직선을 길이 $n$ 짜리 원으로 "감아서" 같은 점에 놓인다는 뜻이다.

또 다른 직관: 합동류 $[a]$ 는 "$a$ 와 같은 나머지를 가지는 모든 정수들의 무한 묶음"이다. $\mathbb{Z}$ 라는 무한집합을 정확히 $n$ 개의 서로소인 묶음(동치류)으로 깔끔하게 분할하는 것 — 이것이 동치관계가 항상 하는 일(분할 정리)이며, 합동은 그 가장 기본적이고 가장 유용한 사례다.

정의

정수 $n>0$ 에 대해, $n\mid(a-b)$ 일 때 "$a$ 와 $b$ 는 법 $n$ 에 대해 합동"이라 하고 $$a \equiv b \pmod n$$ 로 쓴다.¹ 이는 동치관계다(아래 정리에서 증명). $a$ 의 합동류 $[a]=\{b\in\mathbb{Z}: b\equiv a\pmod n\}=\{a+kn : k\in\mathbb{Z}\}$. 합동류 전체의 집합을 $\mathbb{Z}_n=\{[0],[1],\dots,[n-1]\}$ 로 쓴다(나눗셈 정리에 의해 정확히 $n$ 개의 서로 다른 합동류가 있다).

연산: $[a]+[b]:=[a+b]$, $[a][b]:=[ab]$. 이 정의가 합동류의 대표원 선택과 무관하게 같은 결과를 주는지 — 즉 잘 정의됨(well-defined) — 이 합동산술 전체에서 가장 먼저 확인해야 할 사실이다.²

표기	의미
$a\equiv b\pmod n$	$n\mid(a-b)$
$[a]$	$a$ 의 합동류 (= $a+n\mathbb{Z}$)
$\mathbb{Z}_n$	합동류 전체, 원소 $n$ 개
$a\bmod n$	$a$ 를 $n$ 으로 나눈 나머지(나눗셈 정리의 $r$, $[a]=[a\bmod n]$)

주요 정리

정리 (합동은 동치관계). $\equiv\pmod n$ 은 반사적($a\equiv a$, $n\mid0$), 대칭적($a\equiv b\Rightarrow n\mid(a-b)\Rightarrow n\mid(b-a)\Rightarrow b\equiv a$), 추이적($a\equiv b,\ b\equiv c\Rightarrow n\mid(a-b),\ n\mid(b-c)\Rightarrow n\mid((a-b)+(b-c))=(a-c)\Rightarrow a\equiv c$)이다.

정리 (합동류와 나머지의 일치). $[a]=[b] \iff a\equiv b\pmod n \iff a,b$ 를 $n$ 으로 나눈 나머지가 같다. 따라서 $\mathbb{Z}_n=\{[0],[1],\dots,[n-1]\}$ 은 정확히 $n$ 개의 서로 다른 류를 가진다(나눗셈 정리의 나머지 $0,\dots,n-1$ 에 대응).

정리 (합동의 보존, 연산이 잘 정의됨). $a\equiv b$, $c\equiv d \pmod n$ 이면 $a+c\equiv b+d$, $ac\equiv bd \pmod n$.²

증명 보기

증명. $n\mid(a-b)$, $n\mid(c-d)$ 라 하자. 덧셈: $(a+c)-(b+d)=(a-b)+(c-d)$ 는 두 $n$-배수의 합이므로 $n$-배수 → $a+c\equiv b+d$. 곱셈: $ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)$ — 두 항 모두 $n$ 의 배수(각각 $a-b$, $c-d$ 의 배수에 정수를 곱한 것)이므로 합도 $n$ 의 배수 → $ac\equiv bd$. ∎ 이 정리가 정확히 "$[a]+[b]:=[a+b]$ 가 대표원 선택과 무관하다"는 잘 정의됨을 보장한다: $[a]=[a']$, $[b]=[b']$ 이면 $a\equiv a'$, $b\equiv b'$ 이므로 $a+b\equiv a'+b'$, 즉 $[a+b]=[a'+b']$.

정리 ($\mathbb{Z}_n$ 은 환). $(\mathbb{Z}_n, +, \cdot)$ 은 항등원 $[1]$, 영원 $[0]$ 을 가진 가환환이다 → 환과 체. (환 공리는 $\mathbb{Z}$ 의 공리에서 합동의 보존성을 통해 그대로 물려받는다 — 예컨대 결합법칙 $([a]+[b])+[c]=[a+b]+[c]=[(a+b)+c]=[a+(b+c)]=[a]+[b+c]=[a]+([b]+[c])$.)

정리 (일차합동식의 해법). $ax\equiv b\pmod n$ 이 해를 가질 필요충분조건은 $\gcd(a,n)\mid b$. 해가 있으면 법 $n$ 에서 정확히 $\gcd(a,n)$ 개의 (서로 다른) 해를 가진다.³

증명 보기

증명 스케치. $d=\gcd(a,n)$. ($\Rightarrow$) 해 $x$ 가 있으면 $ax-b=ny$ 인 $y$ 가 존재, 즉 $b=ax-ny$ 는 $a,n$ 의 선형결합이라 $d\mid b$. ($\Leftarrow$) Bezout로 $d=as+nt$; $d\mid b$ 이므로 $b=d\cdot k$, 양변에 $k$ 를 곱하면 $b=ask\cdot... $, 정리하면 $a(sk)\equiv b\pmod n$ — $x=sk$ 가 한 해. 해의 개수는 $x_0$ 이 한 해일 때 $x_0+\frac{n}{d},x_0+\frac{2n}{d},\dots$ 가 법 $n$ 에서 서로 다른 해이기 때문(전부 $d$ 개).

예제

예제 1 (영인자의 발견). $\mathbb{Z}_6$ 의 곱셈표 일부: $[2][3]=[6]=[0]$. $[2],[3]$ 모두 $[0]$ 이 아닌데 곱이 $[0]$ — 이런 원소쌍을 영인자(zero divisor)라 한다. 그래서 $\mathbb{Z}_6$ 은 정역이 아니다(환과 체).

예제 2 (큰 거듭제곱의 나머지, 반복제곱). $7^{100} \bmod 5$: $7\equiv2\pmod5$, $2^4=16\equiv1\pmod5$, $100=4\cdot25$ → $7^{100}\equiv2^{100}=(2^4)^{25}\equiv1^{25}=1\pmod5$.

예제 3 (일차합동, 비유일). $4x\equiv2\pmod 6$: $\gcd(4,6)=2$ 이고 $2\mid2$ 이므로 해 존재, 정확히 $2$ 개. 검산으로 $x=2$ 시도: $4\cdot2=8\equiv2\pmod6$ ✓. 해: $x\equiv2,5\pmod6$ (간격 $6/2=3$).

예제 4 (9의 배수 판정, 합동의 응용). $10\equiv1\pmod9$ 이므로 $10^k\equiv1\pmod9$ (모든 $k\ge0$). 십진수 $a=\sum d_i10^i$ 는 $a\equiv\sum d_i\pmod 9$ — 자릿수 합이 곧 (법 9에서) 원래 수와 합동. 그래서 "자릿수 합이 9의 배수 ⟺ 원래 수가 9의 배수".

예제 5 (일차합동, 해 없음). $2x\equiv3\pmod4$: $\gcd(2,4)=2$, $2\nmid3$ → 해 없음. (좌변은 항상 짝수, 우변과 법 4에서 같아지려면 우변도 짝수 류여야 하는데 $3$ 은 홀수.)

예제 6 (CRT 맛보기). $x\equiv2\pmod3$, $x\equiv3\pmod5$ 를 동시에 만족하는 $x$: $x=2,5,8,11,14,17,...$(법 3) 중 법 5에서 3인 것 → $x=8$ ($8=3\cdot2+2$ ✓, $8=5\cdot1+3$ ✓). 법 $15$ 에서 유일 — 중국인의 나머지 정리(다음 페이지)의 직접 응용.

흔한 오해와 함정

합동을 "거의 같다"는 느슨한 의미로 오해 — 합동은 정확한 동치관계다. $a\equiv b\pmod n$ 은 $n\mid(a-b)$ 라는 엄밀한 산술 조건.
곱셈의 well-definedness를 당연시함 — $[a][b]:=[ab]$ 가 대표원과 무관함은 증명이 필요한 정리다(위 "합동의 보존"). 일반적인 동치관계+연산 조합에서는 이것이 실패할 수 있다 — 예컨대 "$a\sim b \iff |a|=|b|$" 위에서 $a\sim b$ 일 때 $f(a)=a^2$ 류의 정의가 항상 잘 정의되는 건 아니다(우연히 여기선 되지만 일반적 교훈은 "확인이 필요"라는 것).
$\mathbb{Z}_n$ 에서 소거법칙($ab=ac\Rightarrow b=c$)이 항상 성립한다고 가정 — $\mathbb{Z}_6$ 에서 $2\cdot1=2\cdot4=2$(둘 다 $[2]$)이지만 $1\ne4$. 영인자가 있는 한 일반 소거는 실패; $\gcd(a,n)=1$ 일 때만 안전하게 소거 가능.
법이 다른 합동을 섞어서 계산 — $a\equiv b\pmod m$ 과 $a\equiv b\pmod n$ 을 더하거나 곱할 수 없다. 같은 법끼리만 연산이 보존된다.
일차합동식의 해 개수를 "항상 유일"로 착각 — $\gcd(a,n)=1$ 일 때만 유일(법 $n$ 에서). 일반적으로 $\gcd(a,n)$ 개의 해가 있거나 아예 없다.

큰 그림 / 연결

합동은 나눗셈 정리의 나머지를 동치관계로 격상시킨 것이며, 그 결과물 $\mathbb{Z}_n$ 은 환의 가장 손에 잡히는 예다. 다음 페이지 ℤₙ의 구조에서 $\mathbb{Z}_n$ 의 단원이 정확히 $\gcd(a,n)=1$ 인 원소들임을 보고, $n$ 이 소수일 때 $\mathbb{Z}_n$ 이 체가 됨을 증명한다. "동치류로 새 구조를 만들고 연산이 잘 정의됨을 확인한다"는 패턴은 이 책 전체에서 반복된다 — 임의의 아이디얼 $I\subseteq R$ 에 대한 몫환 $R/I$가 정확히 이 패턴의 일반화이고($\mathbb{Z}/(n)=\mathbb{Z}_n$), 군론에서는 정규부분군에 의한 몫군이 평행한 이야기를 들려준다. 수론(numbertheory 위키)에서 모듈러 산술은 암호학(RSA, Diffie-Hellman)의 토대이기도 하다.

연습문제

$\mathbb{Z}_7$ 에서 $[3]+[5]$, $[3][5]$ 를 구하라.
$3^{200}$ 을 7로 나눈 나머지를 구하라.
$5x\equiv 3\pmod 7$ 을 풀어라.
$2x\equiv3\pmod4$ 가 해가 없음을 보여라.
임의의 정수 $a$ 에 대해 $a^3\equiv a\pmod 6$ 임을 보여라.
합동 $\equiv\pmod n$ 이 동치관계임을 (반사·대칭·추이) 직접 증명하라.
$a\equiv b\pmod n$ 이면 임의의 정수 $k\ge0$ 에 대해 $a^k\equiv b^k\pmod n$ 임을 증명하라.
$\mathbb{Z}_4$ 의 덧셈표와 곱셈표를 작성하고, 영인자를 모두 찾아라.

정답·힌트

$[3]+[5]=[8]=[1]$; $[3][5]=[15]=[1]$.
$3^6\equiv1\pmod7$ (Fermat, 다음 페이지). $200=6\cdot33+2$ → $3^{200}\equiv3^2=9\equiv2$.
$5^{-1}\equiv3\pmod7$ (∵$5\cdot3=15\equiv1$) → $x\equiv3\cdot3=9\equiv2\pmod7$.
$\gcd(2,4)=2\nmid3$ → 해 없음.
$a^3-a=(a-1)a(a+1)$ 은 연속 세 정수의 곱 → 연속 두 수 중 하나는 짝수(2의 배수), 연속 세 수 중 하나는 3의 배수 → 전체가 $2\cdot3=6$ 으로 나뉨.
반사: $n\mid(a-a)=0$ 항상 참. 대칭: $n\mid(a-b)\Rightarrow n\mid-(a-b)=(b-a)$. 추이: $n\mid(a-b)$, $n\mid(b-c)$ 이면 $n\mid((a-b)+(b-c))=(a-c)$.
$k$ 에 대한 귀납법. $k=0$: $a^0=b^0=1$ 자명. $k\to k+1$: $a^k\equiv b^k$ 이고 $a\equiv b$ 이므로 곱셈 보존(정리)에 의해 $a^k\cdot a\equiv b^k\cdot b$, 즉 $a^{k+1}\equiv b^{k+1}$.
덧셈표는 보통의 $\bmod4$ 순환표. 곱셈표에서 $[2][2]=[0]$ — $[2]$ 가 자기 자신과 곱해 영인자(유일한 0 아닌 영인자, $\mathbb{Z}_4$ 에서).