합동식

개요 — 동기·문제의식

$2^{100}$ 의 마지막 자리 숫자는 무엇인가? 직접 계산하면 $30$ 자리가 넘는 수가 나오지만, 사실 답을 구하는 데 그 모든 자릿수가 필요한 건 아니다 — 우리가 정말 알고 싶은 건 "$10$으로 나눈 나머지"뿐이다. 합동(congruence) 은 이렇게 "전체 값은 잊고 나머지만 추적한다"는 발상을 엄밀한 산술 체계로 만든다. Gauss가 Disquisitiones Arithmeticae(1801)에서 도입한 이 표기법 $a\equiv b\pmod m$ 은 단순한 약속이 아니라, 나머지끼리도 보통의 수처럼 더하고 곱할 수 있다는 — 즉 등식처럼 다뤄도 안전하다는 — 강력한 사실을 압축한다. 이 한 가지 도구 위에 Fermat·Euler의 정리(페르마 소정리, 오일러 φ 함수와 정리), 이차상호법칙, RSA 암호(모듈러 거듭제곱과 RSA)까지 정수론의 거의 모든 결과가 세워진다. 합동은 말 그대로 정수론의 공용어다.

직관 — 시계 산술

합동을 이해하는 가장 좋은 그림은 시계다. $12$시간 시계에서 $9$시에서 $5$시간이 지나면 $2$시가 된다 — $9+5=14$ 인데 시계는 $14$를 $2$로 "읽는다"($14-12=2$). 이것이 정확히 $14\equiv2\pmod{12}$ 다. 일반적으로 $\bmod\,m$ 산술은 수직선을 길이 $m$ 짜리 고리로 둘둘 말아 감은 것과 같다 — $0,1,\dots,m-1$ 이 고리 위의 $m$개 점이고, 모든 정수는 이 고리 위 어딘가에 떨어진다(여러 바퀴를 돌고서). 두 수가 합동이라는 것은 "고리를 감은 뒤 같은 점에 떨어진다"는 뜻이다. 이 그림이 강력한 이유는, 고리를 감기 전에 더하고 곱한 뒤 감거나, 감은 후에 더하고 곱하거나 결과가 똑같다는 데 있다 — 그래서 큰 수를 직접 다루지 않고 작은 나머지로 바꿔치기해서 계산해도 안전하다.

정의

합동(congruence).¹ 양의 정수 $m$ (법, modulus)에 대해 $$a\equiv b\pmod m \quad\overset{\text{def}}{\Longleftrightarrow}\quad m\mid(a-b) \quad\overset{\text{def}}{\Longleftrightarrow}\quad a,b\text{ 를 }m\text{으로 나눈 나머지가 같다.}$$

동치관계로서의 합동. $\equiv\pmod m$ 은 반사적($a\equiv a$), 대칭적($a\equiv b\Rightarrow b\equiv a$), 추이적($a\equiv b,\,b\equiv c\Rightarrow a\equiv c$)이다 — 즉 진짜 동치관계이며, 이것이 정수 전체를 $m$개의 서로소인 잉여류로 깔끔하게 분할한다.

주요 정리

정리 (합동의 산술 — 등식처럼 다루는 근거).¹ $a\equiv b\pmod m$, $c\equiv d\pmod m$ 이면 $$a+c\equiv b+d,\qquad a-c\equiv b-d,\qquad ac\equiv bd\pmod m.$$

정리 (소거법칙).¹ $ac\equiv bc\pmod m$ 이고 $\gcd(c,m)=1$ 이면 $a\equiv b\pmod m$.

정리 (일차합동식의 해).² $ax\equiv c\pmod m$ 이 해를 가질 필요충분조건은 $d=\gcd(a,m)$ 이 $c$ 를 나누는 것이다. 해가 존재하면 법 $m$ 을 기준으로 정확히 $d$ 개의 서로 다른 해를 갖는다.

정리 (곱셈 역원의 존재). $\gcd(a,m)=1$ $\iff$ $a$ 가 $\bmod\,m$ 곱셈 역원 $a^{-1}$($aa^{-1}\equiv1\pmod m$)을 가진다.

정리 (나눗셈 판정법, 합동의 응용).¹ $10\equiv1\pmod9$ 이므로 $10^k\equiv1\pmod9$ (모든 $k\ge0$) → 어떤 수든 각 자릿수의 합이 $9$의 배수이면 그 수 자체도 $9$의 배수(자릿수 합 판정법). 마찬가지로 $10\equiv-1\pmod{11}$ 이므로 $10^k\equiv(-1)^k\pmod{11}$ → 자릿수의 교대합으로 $11$의 배수 여부를 판정한다.

예제

예제 1 (큰 거듭제곱, 거듭제곱 보존 활용). $7^{100}\bmod5$: $7\equiv2\pmod5$ 이므로 $7^{100}\equiv2^{100}\pmod5$. $2^4=16\equiv1\pmod5$ 이고 $100=4\cdot25$ 이므로 $2^{100}=(2^4)^{25}\equiv1^{25}=1\pmod5$.

예제 2 (곱셈 역원, 확장 Euclid). $\bmod26$ 에서 $5^{-1}$: $26=5\cdot5+1$ → $1=26-5\cdot5$ → $5\cdot(-5)\equiv1\pmod{26}$ → $5^{-1}\equiv-5\equiv21\pmod{26}$. 검산: $5\cdot21=105=4\cdot26+1$ ✓.

예제 3 (일차합동식, 해가 여러 개). $6x\equiv4\pmod{10}$: $\gcd(6,10)=2$, $2\mid4$ → 해 존재, 정확히 $2$개. 양변·법을 $2$로 나눠 $3x\equiv2\pmod5$. $3^{-1}\equiv2\pmod5$ ($3\cdot2=6\equiv1$) → $x\equiv2\cdot2=4\pmod5$ → 원래 법 $10$에서는 $x\equiv4\pmod{10}$ 과 $x\equiv9\pmod{10}$ 두 해. 검산: $6\cdot4=24\equiv4\pmod{10}$ ✓, $6\cdot9=54\equiv4\pmod{10}$ ✓.

예제 4 (해가 없는 경우). $4x\equiv3\pmod6$: $\gcd(4,6)=2$, $2\nmid3$ → 해 없음. (직접 확인: $4x\bmod6$ 은 $x=0,\dots,5$ 에서 $0,4,2,0,4,2$ — $3$은 결코 나오지 않는다.)

예제 5 (나눗셈 판정법 응용). $n=4827193$ 이 $9$의 배수인지: 자릿수 합 $4+8+2+7+1+9+3=34$, $3+4=7$ — $9$의 배수 아님. $11$의 배수인지: 교대합(오른쪽부터) $3-9+1-7+2-8+4=-14$ — $11$로 나뉘지 않으므로 $11$의 배수 아님.

예제 6 (연속한 거듭제곱의 마지막 자리, 주기 찾기). $7^n\bmod10$ 의 패턴: $7^1\equiv7,\ 7^2\equiv9,\ 7^3\equiv3,\ 7^4\equiv1,\ 7^5\equiv7,\dots$ — 주기 $4$. $7^{2024}\bmod10$: $2024=4\cdot506$ → $7^{2024}\equiv7^4\equiv1\pmod{10}$, 즉 마지막 자리는 $1$.

예제 7 (합동식의 산술로 큰 수의 나머지). $123456789\bmod7$: $123456789=7\cdot17636684+1$ 을 직접 나누는 대신, $123456789=123\cdot10^6+456\cdot10^3+789$ 로 쪼개고 $10^6\equiv10^3\equiv\cdots$ 의 $\bmod7$ 패턴을 이용하거나, 단순히 단계적으로 나눠 나머지 $1$을 얻는다(직접 나눗셈으로 검증: $7\times17636684=123456788$, 나머지 $1$).

예제 8 (역원이 존재하지 않는 경우). $\bmod 12$ 에서 $4^{-1}$ 이 존재하는가? $\gcd(4,12)=4\ne1$ → 역원이 존재하지 않는다. 실제로 $4x\equiv1\pmod{12}$ 을 만족하는 $x$ 는 없다($4x\bmod12\in\{0,4,8\}$ 뿐, $1$이 될 수 없음).

흔한 오해와 함정

• "합동식도 양변을 아무 수로나 나눌 수 있다" — 틀림. 소거법칙은 $\gcd(c,m)=1$ 일 때만 안전하다. $\gcd(c,m)=d>1$ 이면 나눈 뒤 법도 $m/d$ 로 함께 줄여야 한다(예제 3처럼).
• "$a\equiv b\pmod m$ 이면 $a=b$" — 전혀 다른 이야기다. 합동은 "나머지가 같다"이지 "값이 같다"가 아니다. $14\equiv2\pmod{12}$ 이지만 $14\ne2$.
• 모든 수가 역원을 갖는다고 가정 — $\gcd(a,m)\ne1$ 이면 역원이 존재하지 않는다(예제 8). $\mathbb{Z}_m$ 에서 역원을 갖는 원소는 정확히 기약잉여계(서로소인 것들)뿐이다.
• 일차합동식 $ax\equiv c\pmod m$ 의 해 개수를 항상 "유일"로 착각 — $\gcd(a,m)=d>1$ 이고 $d\mid c$ 이면 해는 $d$개(법 $m$에서). $d=1$일 때만 유일하다.
• 나눗셈 판정법을 $10$ 이외의 진법에서도 그대로 쓰려는 시도 — $9,11$의 판정법은 $10\equiv1\pmod9$, $10\equiv-1\pmod{11}$ 이라는 십진법 고유의 사실에 의존한다. 다른 진법에서는 다른 수에 대해 비슷한 판정법이 성립한다.
• 음수의 합동을 다룰 때 나머지의 범위를 헷갈림 — $-2\equiv?\pmod5$ 는 $-2+5=3$ 이므로 $3$. 음수 나머지를 그냥 두면(예: $-2$) 표준 범위 $\{0,\dots,m-1\}$ 을 벗어나 후속 계산에서 실수를 유발한다.

큰 그림 / 연결

합동은 정수론의 거의 모든 후속 페이지가 쓰는 공용어다. 곱셈 보존성과 소거법칙은 페르마 소정리·오일러 φ 함수와 정리의 재배열 논법에서 핵심 도구로 재사용되고, 일차합동식의 해 이론은 중국인의 나머지 정리에서 여러 법을 동시에 만족하는 해를 구성하는 데 직접 쓰인다. 거듭제곱 보존 성질(예제 1, 6)은 모듈러 거듭제곱과 RSA의 연속 제곱법과 RSA 암호화·복호화 전체의 계산적 기반이며, 역원의 존재와 계산은 RSA의 비밀 지수를 구하는 단계 그 자체다. 더 추상적으로, 잉여류 $\mathbb{Z}_m$ 에 덧셈·곱셈을 얹은 구조는 algebra 위키에서 환(ring)의 가장 구체적인 예시로 다뤄진다 — congruence-and-modular-arithmetic, structure-of-zn 항목은 이 페이지와 같은 대상을 군론·환론의 언어로 다시 서술한 것이다(온톨로지 same-concept). 합동이라는 "유한한 세계로 축소해서 생각한다"는 발상 자체는 이차잉여의 제곱 패턴, 원시근의 곱셈 구조 분석으로 계속 확장된다.

연습문제

1. $3^{1000}\bmod7$ 을 구하라.
2. $\bmod17$ 에서 $7^{-1}$ 을 확장 Euclid로 구하라.
3. $8x\equiv6\pmod{14}$ 의 해를 모두 구하라.
4. $2^{1000}$ 의 마지막 자리(십진 일의 자리)를 구하라.
5. $a\equiv b\pmod m$ 이고 $d\mid m$ 이면 $a\equiv b\pmod d$ 임을 보여라.
6. $n=87654321$ 이 $9$의 배수인지, $11$의 배수인지 판정하라.
7. $\bmod 15$ 에서 어떤 원소가 역원을 갖는지 모두 나열하라.
8. $x^2\equiv1\pmod8$ 의 해를 $\{0,1,\dots,7\}$ 에서 모두 구하고, 해가 둘보다 많다는 사실이 왜 "법이 소수가 아니면 이차방정식의 해가 둘을 넘을 수 있다"는 현상의 예인지 설명하라.

관련 개념

• 나눗셈과 최대공약수 — 역원·일차합동의 도구(확장 Euclid, Bezout)
• 산술의 기본정리 — 소인수분해와 합동의 상호작용
• 페르마 소정리 — $a^{p-1}\equiv1\pmod p$
• 오일러 φ 함수와 정리 — $a^{\varphi(m)}\equiv1\pmod m$, 합성수 법으로 일반화
• 중국인의 나머지 정리 — 여러 법의 연립 합동
• 모듈러 거듭제곱과 RSA — 합동 산술의 가장 유명한 응용
• algebra 위키 congruence-and-modular-arithmetic, structure-of-zn — 동일 개념(온톨로지 same-concept)