I. 정수의 산술 · 1/16

정수와 나눗셈 정리

나눗셈 정리, gcd, 유클리드 호제법

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

개요 — 동기·문제의식

추상대수 전체는 $\mathbb{Z}$ 의 산술을 추상화하는 이야기다. Hungerford의 구성이 환을 군보다 먼저 다루는 이유도 여기 있다 — 우리가 평생 다뤄온 가장 친숙한 대수 구조가 정수환 $\mathbb{Z}$ 이고, 그 안의 거의 모든 정리가 단 하나의 사실에서 흘러나오기 때문이다: 나머지 있는 나눗셈은 항상 가능하고, 그 몫과 나머지는 유일하다. 이것이 나눗셈 정리(Division Algorithm)다. 이 한 정리에서 gcd의 존재, Bezout 항등식, 소인수분해의 유일성, 합동산술, 그리고 한참 뒤 다항식환 $F[x]$ 의 평행한 이론(다항식환)까지 전부 같은 논증 패턴으로 따라 나온다. 이 페이지의 목표는 단순히 "나눗셈"이 아니라, 정렬성 원리(well-ordering principle) 라는 정수 고유의 공리적 사실이 어떻게 모든 산술적 구조를 만들어내는 엔진인지 보는 것이다.

직관

나눗셈 정리는 직관적으로 자명해 보이지만(초등학교 나눗셈), 그 존재성과 유일성을 증명 없이 받아들이면 추상대수 전체가 모래 위에 서게 된다. 핵심 도구는 정렬성 원리: 음 아닌 정수의 공집합이 아닌 부분집합은 항상 최소원을 가진다. 이는 $\mathbb{Z}$ 가 $\mathbb{Q}$ 나 $\mathbb{R}$ 과 본질적으로 다른 지점이다 — $\mathbb{Q}_{>0}$ 에는 최소원이 없지만(아무리 작은 양의 유리수도 그보다 작은 양의 유리수가 존재), $\mathbb{Z}_{\ge0}$ 에는 항상 있다. 나눗셈 정리의 증명은 이 사실을 정확히 한 번 사용한다: "$a$ 에서 $b$ 의 배수를 최대한 많이 뺀 나머지들" 중 음이 아닌 것 중 가장 작은 것을 골라낸다 — 더 뺄 수 있다면 더 작은 음 아닌 나머지가 생기므로 모순이 되는 지점에서 멈춘다는 것이 곧 "나머지가 $b$ 보다 작다"는 뜻이다.

기하적으로는, 수직선 위에서 $b, 2b, 3b,\dots$ 의 눈금을 긋고 $a$ 가 어느 칸에 떨어지는지 보는 것과 같다 — $a$ 는 $qb$ 와 $(q+1)b$ 사이(또는 정확히 $qb$ 위)에 있고, 그 거리 $r=a-qb$ 가 나머지다.

정의

정수 $a, b$ 에 대해 $b = ac$ 인 정수 $c$ 가 존재하면 "$a$ 가 $b$ 를 나눈다(divides)"고 하고 $a \mid b$ 로 쓴다. 이때 $a$ 는 $b$ 의 약수, $b$ 는 $a$ 의 배수. $a\nmid b$ 는 나누지 않음을 뜻한다.

기본 성질 (정의에서 즉시 따라옴): $a\mid b$ 이고 $b\mid c$ 이면 $a\mid c$ (추이성). $a\mid b$ 이고 $a\mid c$ 이면 임의의 정수 $x,y$ 에 대해 $a\mid (bx+cy)$ (선형결합으로 닫힘). 모든 정수는 자기 자신과 $\pm1$ 을 약수로 가진다(자명한 약수).

기호	의미
$a\mid b$	$a$ 가 $b$ 를 나눈다
$q,r$	나눗셈 정리의 몫, 나머지
$\gcd(a,b)$	최대공약수
$a\equiv r\pmod b$	(다음 페이지에서) $r$ 이 $a$ 를 $b$ 로 나눈 나머지

주요 정리

정리 (나눗셈 정리, Division Algorithm). 정수 $a$ 와 $b>0$ 에 대해, 다음을 만족하는 정수 $q, r$ 이 유일하게 존재한다:¹ $$a = bq + r, \qquad 0 \le r < b.$$ $q$ 는 몫, $r$ 은 나머지.

증명 보기

증명. 존재. 집합 $S=\{a-bq : q\in\mathbb{Z},\ a-bq\ge 0\}$ 을 생각하자. $S$ 는 공집합이 아니다 — $q$ 를 충분히 작은(매우 음수인) 정수로 잡으면 $a-bq$ 가 얼마든지 커지므로 음 아닌 원소가 존재한다. $S\subseteq\mathbb{Z}_{\ge0}$ 이므로 정렬성 원리에 의해 $S$ 는 최소원 $r=a-bq_0$ 을 가진다. $r\ge0$ 임은 $S$ 의 정의에서. 만약 $r\ge b$ 라면 $r'=r-b=a-b(q_0+1)\ge0$ 이고 $r'<r$ 이므로 $r'\in S$ 가 $r$ 보다 작은 원소가 되어 $r$ 의 최소성에 모순. 따라서 $0\le r<b$, 그리고 $q=q_0$ 으로 두면 $a=bq+r$.

유일성. $a=bq+r=bq'+r'$ ($0\le r,r'<b$) 이라 하자. 그러면 $b(q-q')=r'-r$ 이므로 $b\mid(r'-r)$. 그런데 $0\le r,r'<b$ 이므로 $-b<r'-r<b$, 즉 $|r'-r|<b$. $b$ 의 배수 중 절댓값이 $b$ 보다 작은 것은 $0$ 뿐이므로 $r'-r=0$, 즉 $r=r'$. 그러면 $b(q-q')=0$ 이고 $b>0$ 이므로 $q=q'$. ∎

정의·정리 (최대공약수, gcd). 둘 다 0은 아닌 $a,b$ 에 대해, $a,b$ 를 모두 나누는 정수 중 최대인 양의 정수를 $\gcd(a,b)$ 라 한다. ($\gcd(a,0)=|a|$.) gcd는 항상 존재한다 — 공약수 집합이 위로 유계(둘 중 0이 아닌 것의 절댓값)인 양의 정수 집합이므로.

정리 (Euclid 호제법). $b>0$ 이고 $a=bq+r$ ($0\le r<b$, 나눗셈 정리)이면 $\gcd(a,b)=\gcd(b,r)$.²

증명 보기

증명. $d\mid a$ 이고 $d\mid b$ 이면 $d\mid (a-bq)=r$ — 즉 $a,b$ 의 공약수는 $b,r$ 의 공약수다. 역으로 $d\mid b$, $d\mid r$ 이면 $d\mid(bq+r)=a$ — $b,r$ 의 공약수도 $a,b$ 의 공약수다. 두 집합이 같으므로 최대원도 같다. ∎ 이 정리를 반복 적용하면(나머지가 단조감소하며 $0$ 에 도달) 유한 단계 안에 $\gcd$ 가 계산된다 — Euclid 호제법.

예제

예제 1 (Euclid 호제법, 큰 수). $a=76, b=21$: $$76=21\cdot3+13,\quad21=13\cdot1+8,\quad13=8\cdot1+5,\quad8=5\cdot1+3,\quad5=3\cdot1+2,\quad3=2\cdot1+1,\quad2=1\cdot2+0.$$ 나머지가 $0$ 이 되기 직전 값이 $\gcd$: $\gcd(76,21)=1$.

예제 2 (간단한 경우). $\gcd(48,36)$: $48=36\cdot1+12$, $36=12\cdot3+0$ → $\gcd=12$.

예제 3 (음수 입력). $a=-17,b=5$: $-17 = 5\cdot(-4)+3$ ($0\le3<5$). 몫 $-4$, 나머지 $3$. 나머지는 항상 음이 아니다 — $b$ 가 양수인 한, $a$ 의 부호와 무관하게 $0\le r<b$.

예제 4 ($b$ 가 음수일 때 처리). 정리는 $b>0$ 만 다루지만, $b<0$ 인 경우는 $|b|$ 로 나눗셈 정리를 적용한 뒤 부호를 조정해 동일한 형태로 만들 수 있다(Hungerford는 $b>0$ 으로 충분히 일반적이라고 본다 — $a\mid b \iff a\mid(-b)$).

예제 5 (gcd가 1인 두 큰 수). $\gcd(1001,357)$: $1001=357\cdot2+287$, $357=287\cdot1+70$, $287=70\cdot4+7$, $70=7\cdot10+0$ → $\gcd=7$ (1이 아님에 주의 — "서로소"는 다음 페이지에서 별도로 정의).

예제 6 (정렬성 원리 자체의 응용). $n^2\ge n$ 이 모든 양의 정수 $n$ 에 대해 성립함을 정렬성으로 보일 수도 있다: 만약 $n^2<n$ 인 $n$ 의 집합이 공집합이 아니면 최소원 $m$ 이 있고, $0<m<1$ 인 정수가 없으므로($m^2<m \Rightarrow 0<m<1$, 정수론적으로 불가능) 모순. (정렬성이 단순 나눗셈을 넘어 폭넓게 쓰이는 증명 도구임을 보여주는 예.)

흔한 오해와 함정

나눗셈 정리를 "$a/b$ 의 계산"으로 착각 — 정리의 본질은 존재와 유일성의 증명이지, 단순 계산 절차가 아니다. 증명에서 정렬성 원리를 빼면 "직관적으로 당연하다"는 순환논법이 된다.
나머지가 음수일 수 있다고 생각 — 절대 아니다. $b>0$ 인 한 $0\le r<b$ 로 강제된다. $-17$ 을 $5$ 로 나눈 나머지는 $-2$ 가 아니라 $3$.
$\gcd(a,0)$ 을 정의 불가로 착각 — $\gcd(a,0)=|a|$ 로 정의된다(모든 정수가 $0$ 을 나누므로 $0$ 의 약수 전체가 공약수 후보).
Euclid 호제법을 "한 번에 gcd를 줌"으로 착각 — 호제법은 $\gcd(a,b)=\gcd(b,r)$ 이라는 단계 축소 정리이지, 그 자체로 답을 주지 않는다. 나머지가 $0$ 이 될 때까지 반복해야 한다.
나눗셈 정리가 $\mathbb{Z}$ 만의 특권이라고 생각 — 사실 이 증명 패턴(정렬성으로 최소 나머지를 찾는 것)은 다항식환 $F[x]$ 에서 차수를 기준으로 거의 그대로 반복된다(다항식환). 이 평행성이 Euclid 정역이라는 일반 개념을 낳는다.

큰 그림 / 연결

나눗셈 정리는 이 위키의 진짜 출발점이다. 직접적으로 gcd의 선형결합 표현(Bezout)과 소인수분해의 유일성을 낳고, 나머지 개념이 그대로 합동의 정의가 되어 $\mathbb{Z}_n$ 을 만든다. 더 멀리는, 다항식환 $F[x]$ 가 정확히 같은 구조(차수가 음 아닌 정수이므로 정렬성이 다시 작동)를 가져 다항식의 나눗셈 정리로 거의 글자 그대로 반복되고, 이 평행성을 추상화한 것이 Euclid 정역(Euclidean domain)이다 — "나눗셈 정리가 성립하는 정역"이라는 한 줄짜리 공리가 $\mathbb{Z}$ 와 $F[x]$ 를 동시에 포섭한다. 수론(numbertheory 위키)에서는 이 나눗셈 정리가 연분수·Diophantine 방정식의 출발점이 되며, 알고리즘 관점에서는 Euclid 호제법이 계산복잡도 이론에서 다항시간 알고리즘의 고전적 예다.

연습문제

나눗셈 정리로 $a=100, b=7$ 의 $q,r$ 을 구하라.
$\gcd(1001, 357)$ 을 Euclid 호제법으로 구하라.
$a=-50, b=8$ 의 나머지를 구하라.
임의의 정수 $n$ 에 대해 $n^2$ 을 4로 나눈 나머지는 0 또는 1뿐임을 보여라. (힌트: $n=2k$ 또는 $n=2k+1$.)
$\gcd(a,b)=\gcd(b, a-b)$ 임을 보여라.
나눗셈 정리의 유일성 증명에서 "$b$ 의 배수 중 절댓값이 $b$ 보다 작은 것은 $0$ 뿐"이라는 사실을 직접 정당화하라.
$a,b,c$ 가 정수이고 $a\mid b$, $a\mid c$ 이면 임의의 정수 $x,y$ 에 대해 $a\mid(bx+cy)$ 임을 증명하라.
정렬성 원리를 사용해, 양의 정수 전체의 집합에는 최소원 $1$ 이 존재함을 (자명하지만) 형식적으로 논증하라.

힌트 / 정답

$100 = 7\cdot14 + 2$ → $q=14,\,r=2$.
$1001=357\cdot2+287$, $357=287\cdot1+70$, $287=70\cdot4+7$, $70=7\cdot10+0$ → $\gcd=7$.
$-50 = 8\cdot(-7)+6$ → 나머지 $6$.
$n=2k$ → $n^2=4k^2$ (나머지 0). $n=2k+1$ → $n^2=4(k^2+k)+1$ (나머지 1).
공약수 집합이 같음: $d\mid a,d\mid b \iff d\mid b, d\mid(a-b)$ (∵ $a=(a-b)+b$). 따라서 최대원도 같다. (Euclid 호제법의 근거이자 정리의 일반화.)
$kb$ ($k\ne0$) 의 절댓값은 $|k||b|\ge|b|=b$ (∵ $|k|\ge1$ 인 정수). 따라서 $0<|kb|<b$ 인 정수배는 없다 — $kb$ 가 그 범위에 있으려면 $k=0$, 즉 $kb=0$.
$b=ax$, $c=ay'$ 라 두면(정의상 $a\mid b,a\mid c$ 이므로 $b=as$, $c=at$ 인 $s,t$ 존재) $bx+cy=a(sx+ty)$ — $a$ 의 배수이므로 $a\mid(bx+cy)$.
양의 정수 집합은 공집합이 아니고 음이 아닌 정수 집합의 부분집합이므로 정렬성 원리에 의해 최소원이 존재; $1$ 이 그 원소보다 작을 수 없으므로(어떤 양의 정수도 $1$ 보다 작은 양의 정수가 아님) 최소원은 $1$.