ℤ정수론
II. 나눗셈과 소수 · 2/16

나눗셈과 최대공약수

나눗셈 정리, 유클리드 호제법, 베주 항등식

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

개요 — 동기·문제의식

정수론의 모든 것은 결국 "나눈다"는 한 가지 동작에서 자라난다. $a$ 가 $b$ 를 나누는가? 두 수가 공유하는 가장 큰 약수는 무엇인가? 이 단순한 질문들이 유일인수분해·합동·RSA까지 정수론 전체가 서는 토대다. 이 페이지가 다루는 사슬은 나눗셈 정리 → Euclid 호제법(gcd 계산) → Bezout 항등식($\gcd=ax+by$) 으로 이어지며, 이 세 단계는 각각 "나머지를 만든다 → 나머지로 gcd를 줄인다 → gcd를 두 수의 정수 결합으로 거꾸로 복원한다"는 하나의 이야기를 이룬다. 놀라운 점은 이 절차가 $a,b$ 가 아무리 커도(수천 자리 RSA 소수라도) 빠르게 끝난다는 것이다 — 정수론이 단지 이론이 아니라 실용적 알고리즘의 학문이기도 한 첫 증거가 여기서 나온다.

대수학(algebra) 위키에서도 같은 구조를 정수환(혹은 임의의 유클리드 정역)의 일반론으로 다루지만, 이 위키에서는 구체적인 수로 직접 계산하는 데 무게를 둔다.

직관 — 왜 호제법이 통하는가

$\gcd(1180,482)$ 를 구한다고 하자. 약수를 일일이 나열해 비교하는 건 큰 수에서는 절망적이다. 핵심 관찰은 이것이다: $a=bq+r$ 로 나누면, $a,b$ 의 공약수 집합은 $b,r$ 의 공약수 집합과 정확히 같다. 왜냐하면 $d\mid a$ 이고 $d\mid b$ 이면 $r=a-bq$ 도 $d$ 로 나뉘고, 거꾸로 $d\mid b$, $d\mid r$ 이면 $a=bq+r$ 도 $d$ 로 나뉘기 때문이다 — 나눗셈은 공약수를 보존하면서 숫자만 작게 줄이는 변환이다. 그래서 $\gcd(1180,482)=\gcd(482,216)=\gcd(216,50)=\cdots$ 처럼 두 수가 빠르게 작아지다가, 결국 한쪽이 다른 쪽을 나누어떨어뜨리는 순간(나머지 $0$) gcd가 그대로 드러난다. 마치 두 막대기의 길이를 재서 짧은 쪽으로 긴 쪽을 계속 측정해 나가는 유클리드의 원래 기하학적 그림 그대로다.

Bezout 항등식은 이 과정을 거꾸로 되짚는다 — 마지막 줄(나머지가 gcd인 줄)에서 시작해 한 단계씩 위로 올라가며 매번 "이 나머지는 이전 두 수의 정수 결합"이라는 사실을 대입해 나가면, 결국 gcd가 처음 두 수 $a,b$ 만의 정수 결합 $ax+by$ 로 표현된다.

정의

기호/용어 정의
$a\mid b$ ($a$ 가 $b$ 를 나눔) $b=ac$ 인 정수 $c$ 가 존재
$a\nmid b$ 그런 $c$ 가 없음
최대공약수 $\gcd(a,b)$ $a,b$ 를 모두 나누는 양의 정수 중 가장 큰 것 (둘 다 $0$이 아닐 때 잘 정의됨)
서로소(coprime) $\gcd(a,b)=1$
최소공배수 $\operatorname{lcm}(a,b)$ $a,b$ 의 양의 공배수 중 가장 작은 것

나눗셈 정리(Division Algorithm).1 임의의 정수 $a$ 와 양의 정수 $b$ 에 대해 $$a=bq+r,\qquad 0\le r<b$$ 인 정수 $q$(몫), $r$(나머지)이 유일하게 존재한다.

비고. $\gcd$ 의 정의를 $\gcd(a,0)=|a|$ 로 약속하면(어떤 수든 $0$을 나누므로) 호제법의 종료 조건과 자연스럽게 맞아떨어진다. $\gcd$ 는 항상 양수로 잡는 관례를 따른다($a,b$ 의 부호와 무관).

주요 정리

정리 (나눗셈 정리의 증명 스케치). 존재성: $a-bq\ge0$ 을 만족하는 가장 큰 $q$ 를 잡으면(정수 집합의 정렬성, $a\ge0$ 인 경우 $q=0,1,2,\dots$ 를 시도) $r=a-bq$ 는 $0\le r<b$ 를 만족한다($r\ge b$ 이면 $q+1$ 도 후보가 되어 $q$ 의 최대성에 모순). 유일성: $a=bq_1+r_1=bq_2+r_2$ ($0\le r_1,r_2<b$)이면 $b(q_1-q_2)=r_2-r_1$, 우변의 절댓값은 $b$ 미만인데 좌변은 $b$ 의 배수이므로 양쪽 모두 $0$ — $q_1=q_2$, $r_1=r_2$.

정리 (Euclid 호제법).1 $a=bq+r$ ($0\le r<b$) 이면 $\gcd(a,b)=\gcd(b,r)$. 이를 나머지가 $0$ 이 될 때까지 반복하면 마지막 $0$ 이 아닌 나머지가 $\gcd(a,b)$ 다.

증명 보기

증명. $d$ 가 $a,b$ 의 공약수 $\iff$ $d\mid a$, $d\mid b$ $\iff$ $d\mid b$, $d\mid(a-bq)=r$ $\iff$ $d$ 가 $b,r$ 의 공약수. 두 쌍의 공약수 집합이 완전히 같으므로 그 집합의 최댓값(gcd)도 같다. 호제법이 종료하는 이유는 나머지가 $r_1>r_2>\cdots\ge0$ 으로 매번 엄격히 줄어드는 음 아닌 정수열이라 유한 단계 안에 $0$ 에 도달할 수밖에 없기 때문이다.

정리 (Bezout 항등식 / 선형방정식).2 $\gcd(a,b)=d$ 이면 $ax+by=d$ 를 만족하는 정수 $x,y$ 가 존재한다(확장 Euclid 호제법으로 계산). 더 일반적으로, $ax+by=c$ 가 정수해를 가질 필요충분조건은 $d\mid c$ 이다.

증명 보기

증명 스케치 (존재). 호제법의 각 줄 $r_{k-1}=r_kq_{k+1}+r_{k+1}$ 을 $r_{k+1}=r_{k-1}-r_kq_{k+1}$ 로 뒤집어, 마지막 줄(나머지가 $d$)부터 거꾸로 대입해 올라가면 $d$ 가 매 단계 직전 두 나머지의 정수 결합으로, 결국 $a,b$ 의 정수 결합으로 표현된다(아래 예제 2가 이 과정을 보여준다). 필요충분조건의 증명. ($\Rightarrow$) $d\mid a,d\mid b$ 이므로 $d\mid(ax+by)=c$. ($\Leftarrow$) $d\mid c$ 이면 $c=dk$ 라 쓰고, Bezout으로 얻은 $ax_0+by_0=d$ 의 양변에 $k$ 를 곱하면 $a(kx_0)+b(ky_0)=dk=c$.

따름정리 (해의 일반형). $ax+by=c$ 가 해를 가지면($d\mid c$), 특수해 $(x_0,y_0)$ 로부터 모든 정수해는 $$x=x_0+\frac{b}{d}t,\qquad y=y_0-\frac{a}{d}t\qquad(t\in\mathbb{Z})$$ 로 주어진다. 왜 $b/d, a/d$ 인가. 두 해의 차 $(x-x_0,y-y_0)$ 는 $a(x-x_0)=-b(y-y_0)$ 를 만족해야 하는데, $a/d$ 와 $b/d$ 가 서로소이므로 $b/d\mid(x-x_0)$ 이어야 한다(이것이 바로 다음 정리).

정리 (서로소의 핵심 성질, Euclid 보조정리의 토대). $\gcd(a,b)=1$ 이고 $a\mid bc$ 이면 $a\mid c$.

증명 보기

증명. Bezout으로 $1=ax+by$. 양변에 $c$ 를 곱하면 $c=acx+bcy$. $a\mid bc$ 이므로 우변의 두 항 모두 $a$ 의 배수 → $a\mid c$. (이 사실이 다음 페이지 산술의 기본정리의 Euclid 보조정리를 그대로 증명한다 — $a=p$ 가 소수이면 $\gcd(p,b)$ 는 $1$ 또는 $p$ 뿐이므로.)

예제

예제 1 (나눗셈 정리). $a=-17$, $b=5$: $-17=5\cdot(-4)+3$ ($q=-4$, $r=3$). 음수를 나눌 때 $r$ 은 항상 $0\le r<b$ 범위를 지킨다 — $-17=5\cdot(-3)+(-2)$ 는 $r=-2<0$ 이라 나눗셈 정리의 표준형이 아니다.

예제 2 (Euclid 호제법). $\gcd(1180,482)$: $$1180=482\cdot2+216,\quad 482=216\cdot2+50,\quad 216=50\cdot4+16,\quad 50=16\cdot3+2,\quad 16=2\cdot8+0.$$ 마지막 $0$ 이 아닌 나머지 $\gcd=2$.

예제 3 (Bezout, 확장 Euclid — 역대입). 같은 두 수 $17,5$ 로 $\gcd(17,5)=1$ 을 $17x+5y=1$ 로: $17=5\cdot3+2$, $5=2\cdot2+1$, $2=1\cdot2+0$. 역대입: $1=5-2\cdot2$. $2=17-5\cdot3$ 을 대입: $1=5-(17-5\cdot3)\cdot2=5\cdot7-17\cdot2$. 따라서 $x=-2,\ y=7$. 검산: $17\cdot(-2)+5\cdot7=-34+35=1$ ✓.

예제 4 (Bezout, 더 큰 수). $\gcd(35,64)$ 를 $35x+64y=1$ 로. $64=35+29$, $35=29+6$, $29=6\cdot4+5$, $6=5+1$, $5=1\cdot5+0$ → $\gcd=1$. 역대입: $1=6-5$. $5=29-6\cdot4$ 대입: $1=6-(29-6\cdot4)=6\cdot5-29$. $6=35-29$ 대입: $1=(35-29)\cdot5-29=35\cdot5-29\cdot6$. $29=64-35$ 대입: $1=35\cdot5-(64-35)\cdot6=35\cdot11-64\cdot6$. 따라서 $x=11,\ y=-6$. 검산: $35\cdot11+64\cdot(-6)=385-384=1$ ✓.

예제 5 (선형 디오판토스 방정식, 해 존재 판정). $6x+9y=21$: $\gcd(6,9)=3$, $3\mid21$ → 해 존재. 양변을 $3$ 으로 나누면 $2x+3y=7$. 시행으로 특수해 $(x_0,y_0)=(2,1)$ ($4+3=7$ ✓). 일반해: $x=2+3t,\ y=1-2t$ ($t\in\mathbb{Z}$).

예제 6 (해가 없는 경우). $6x+9y=20$: $\gcd(6,9)=3$ 이고 $3\nmid20$ → 정수해 없음. ($20/3$ 이 정수가 아니므로 직관적으로도 당연 — $6x+9y$ 는 항상 $3$ 의 배수이기 때문이다.)

예제 7 (최소공배수 계산). $\operatorname{lcm}(1180,482)$: 예제 2에서 $\gcd=2$, 항등식 $\gcd\cdot\operatorname{lcm}=ab$ 로 $\operatorname{lcm}=\dfrac{1180\cdot482}{2}=\dfrac{568760}{2}=284380$.

예제 8 (서로소 응용, RSA 맛보기). $\gcd(7,40)=1$ 이므로 $7x\equiv1\pmod{40}$ 은 해를 가진다. 확장 Euclid: $40=7\cdot5+5$, $7=5+2$, $5=2\cdot2+1$ → 역대입 $1=5-2\cdot2=5-(7-5)\cdot2=5\cdot3-7\cdot2=(40-7\cdot5)\cdot3-7\cdot2=40\cdot3-7\cdot17$. 따라서 $7\cdot(-17)\equiv1\pmod{40}$, 즉 $7^{-1}\equiv-17\equiv23\pmod{40}$. 검산: $7\cdot23=161=4\cdot40+1$ ✓. 이런 역원 계산이 모듈러 거듭제곱과 RSA에서 비밀 지수 $d$ 를 구하는 바로 그 절차다.

흔한 오해와 함정

큰 그림 / 연결

이 페이지의 세 도구(나눗셈 정리·호제법·Bezout)는 정수론 전체에서 반복되는 패턴의 원형이다. Bezout의 "서로소이면 $1=ax+by$" 는 산술의 기본정리의 Euclid 보조정리를 직접 증명하고, 그것이 다시 유일인수분해 정리 전체를 떠받친다. 합동식의 일차합동식 $ax\equiv c\pmod m$ 의 해 존재 조건은 정확히 이 페이지의 선형 디오판토스 방정식과 동일한 문제이고, 합동식의 곱셈 역원도 Bezout으로 구한다(예제 8). 중국인의 나머지 정리은 여러 서로소 법에 대해 이 역원 계산을 반복 적용하는 구조이며, 모듈러 거듭제곱과 RSA에서 비밀 지수를 구하는 단계는 글자 그대로 확장 Euclid 호제법이다. 더 추상적으로는 algebra 위키의 integers-and-division-algorithm·euclidean-pid-ufd가 이 모든 절차를 임의의 유클리드 정역으로 일반화한다 — 정수에서 일어나는 일이 다항식환·가우스 정수(가우스 정수)에서도 글자 그대로 반복된다.

연습문제

  1. $\gcd(2024, 748)$ 을 Euclid 호제법으로 구하라.
  2. $17=5\cdot3+2$, $5=2\cdot2+1$ 의 역대입으로 $35x+64y=1$ 이 아니라 $35\cdot11+64\cdot(-6)=1$ 임을 처음부터 직접 다시 유도해 확인하라(예제 4 보지 않고).
  3. $14x+35y=7$ 의 정수해를 모두 구하라.
  4. $\gcd(a,b)=1$ 이고 $a\mid c$, $b\mid c$ 이면 $ab\mid c$ 임을 보여라.
  5. $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab$ 임을 증명하라.
  6. $9x+12y=2$ 가 정수해를 갖지 않음을 보이고 이유를 설명하라.
  7. $\gcd(F_{n+1},F_n)=1$ (연속한 피보나치 수는 서로소)임을 호제법의 구조로 설명하라. ($F_1=1,F_2=1,F_3=2,\dots$)
  8. $\bmod 91$ 에서 $11^{-1}$ 을 확장 Euclid 호제법으로 구하라.
힌트 / 정답
  1. $2024=748\cdot2+528$, $748=528\cdot1+220$, $528=220\cdot2+88$, $220=88\cdot2+44$, $88=44\cdot2+0$ → $\gcd=44$.
  2. $64=35\cdot1+29$, $35=29+6$, $29=6\cdot4+5$, $6=5+1$, $5=5\cdot1+0$. 역대입: $1=6-5$, $5=29-6\cdot4 \Rightarrow 1=6-(29-24)=5\cdot6-29$, $6=35-29 \Rightarrow 1=5(35-29)-29=5\cdot35-6\cdot29$, $29=64-35 \Rightarrow 1=5\cdot35-6(64-35)=11\cdot35-6\cdot64$ → $x=11,y=-6$, 즉 $35\cdot11+64\cdot(-6)=1$, 예제 4와 일치.
  3. $\gcd(14,35)=7\mid7$ → 해 존재. $2x+5y=1$ 로 약분, 특수해 $(x_0,y_0)=(-2,1)$ ($-4+5=1$) → 원래 식의 해는 $x=-2+5t,\ y=1-2t$.
  4. Bezout $1=ax+by$ → 양변에 $c$ 곱: $c=acx+bcy$. $b\mid c$ 이므로 $c=bm$, 첫 항 $acx$; $a\mid c$ 이므로 $c=an$, 둘째 항 $bcy=ab(ny)/$ ... 더 직접적으로: $a\mid c\Rightarrow c=ak$; $b\mid c=ak$ 이고 $\gcd(a,b)=1$ 이므로 (서로소 성질로) $b\mid k$, $k=bm$ → $c=abm$ → $ab\mid c$.
  5. $d=\gcd(a,b)$, $a=da'$, $b=db'$ ($\gcd(a',b')=1$). $\operatorname{lcm}(a,b)=da'b'$ 이 $a,b$ 의 공배수 중 최소임을 보이면(공배수는 반드시 $da'b'$ 의 배수) $d\cdot\operatorname{lcm}=d\cdot da'b'=(da')(db')=ab$.
  6. $\gcd(9,12)=3$, $3\nmid2$ → 정수해 없음(좌변은 항상 $3$의 배수인데 우변 $2$는 아님).
  7. 호제법으로 $\gcd(F_{n+1},F_n)$ 을 계산하면 $F_{n+1}=1\cdot F_n+F_{n-1}$ (피보나치 정의 자체가 나눗셈 정리 형태) → $\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1})=\cdots=\gcd(F_2,F_1)=\gcd(1,1)=1$.
  8. $91=11\cdot8+3$, $11=3\cdot3+2$, $3=2+1$, $2=1\cdot2+0$. 역대입: $1=3-2=3-(11-3\cdot3)=3\cdot4-11=(91-11\cdot8)\cdot4-11=91\cdot4-11\cdot33$. 따라서 $11\cdot(-33)\equiv1\pmod{91}$, $11^{-1}\equiv-33\equiv58\pmod{91}$. 검산: $11\cdot58=638=7\cdot91+1$ ✓.

관련 개념

  1. 원전 소개 — Silverman ch.5 [synthesis] — 나눗셈 정리(존재성·유일성)와 Euclid 호제법의 절차·정당성(공약수 집합의 보존). ↩↩

  2. 원전 소개 — Silverman ch.6 [synthesis] — 선형방정식 $ax+by=\gcd(a,b)$ (Bezout 항등식), 확장 Euclid 호제법으로 계수 $x,y$ 계산, 해의 존재 조건과 일반해의 형태. ↩