[include(틀:정수론)]
[목차]
== 개요 ==
{{{+2 Division Algorithm}}}

처음 [[나눗셈]]을 배울 때 몫과 나머지가 당연히 존재한다고 생각하고 나눗셈을 한다. 하지만 [[소인수분해]]의 존재성과 마찬가지로 몫과 나머지의 존재성은 당연한 결과가 아니며[* 당장 [[정수]]에서 [[유리수]]로만 올라가도 [[체(대수학)|나머지가 존재하지 않는다]].] 수학적인 증명이 필요하다. 나눗셈 정리는 우리가 [[나눗셈]]을 통해 몫과 나머지를 자연스럽게 구하게 할 수 있게 만들어 주는 정리이다. 자세한 정리는 아래와 같다.
>임의의 양의 정수 [math(a,b)]에 대하여, [math(b=aq+r,\,\left(0\leq r<a\right))]를 만족시키는 정수 [math(q,r)]이 '''유일'''하게 '''존재'''한다.

== 증명 ==
크게 존재성과 유일성, 두 파트로 나뉜다.
=== 존재성 ===
집합 [math(A=\left\{b-na|n\in \mathbb{Z},\, b-an\geq0\right\})]을 생각하자. 그럼 집합 [math(A)]는 공집합이 아니고,[* [math(n=0)]일 때, [math(b\in A)]이므로.] [math(A\subseteq \mathbb{N})][* 집합론에서는 0도 자연수에 포함한다고 본다. 그러는 편이 덧셈의 항등원이 존재하니 더 풍부한 성질을 갖기고 하고...]이므로 well-ordering 원리에 의해 집합 [math(A)]에는 가장 작은 [[원소]]가 존재한다. 그 원소를 [math(r)]이라 하면 적당한 정수 [math(q)]에 대해 [math(r=b-aq)]로 표시된다. 즉, [math(b=aq+r)]이고 [math(r\geq0)]이다. 만약 [math(r\geq a)]라 가정하면 [math(b-\left(q+1\right)a=b-aq-a=r-a\geq0)]이므로 [math(r-a\in A)]이다. 그런데 [math(a>0)]이므로 [math(r-a<r)]이고, 이는 곧 [math(r)]이 집합 [math(A)]의 가장 작은 원소라는 사실에 모순된다. 따라서 [math(r<a)]이다.
=== 유일성 ===
정수 [math(p,s)]가 [math(b=ap+s,\,\left(0\leq s<a\right))]을 만족시킨다고 하자. 그러면 [math(ap+s=aq+r)]로 부터 [math(\left(p-q\right)a=r-s)]이다. 여기서 만약 [math(p\neq q)]이라고 하면,[* 즉 몫과 나머지가 유일하지 않다고 하면] [math(\left|a\right|\leq\left|p-q\right|\cdot\left|a\right|)][* [math(p,q)]가 둘 다 정수이고, [math(p\neq q)]이므로, 두 수의 차의 [[절대값]]은 최소 1 이상이다.][math(=\left|\left(p-q\right)a\right|=\left|r-s\right|<\left|a\right|)]가 되어 모순이다. 따라서 [math(p=q)]이어야 하고, 이는 곧 [math(r=s)]를 의미한다. 즉, 몫과 나머지가 유일하게 존재한다.

== 활용 ==
이 당연해 보이는 성질을 어떻게 활용하냐면, [[정수론]]에서의 [[유클리드 호제법]]이나 [[다항식]]에서의 [[나머지 정리]] 등, 여러 가지로 활용된다. [[유클리드 호제법]]은 이 나눗셈 정리가 없다면 애초에 성립조차 할 수 없으며, 이 나눗셈 정리의 [[다항식]] 버전이 고등학교에서 배우는 [[나머지 정리]]가 되기 때문. 또한, [[최대공약수]]의 성질의 증명에서도 활용된다. 즉, 나눗셈 정리는 [[정수론]]의 기초 중에 기초라고 할 수 있다.

한편, [[현대대수학]]에서는 이를 다항식, 그것도 사칙연산 모두가 잘 정의되는 [[체(대수학)|체]]를 계수로 하는 다항식만이 아니라 계수가 [[환(대수학)|환]]일 경우에 대해서까지 소개한다. 가환환일 경우와 비가환환일 경우를 모두 고려하여 왼쪽곱, 오른쪽곱에 대해 따로 증명할만큼의 ~~쪼잔함~~ 세심한 증명이 매우 인상적인 증명인데, 학습에 있어 반드시 스스로의 힘으로 해내야 할만큼 중요한 증명까지는 아니어도 교과서에 적힌 증명을 한번쯤은 읽고 따라해보는 것이 좋다. [[수학적 귀납법]]을 적절히 이용하는 것이 핵심. 다만 f의 계수와 g의 계수들을 갖고 매우 짜증나는(...) 계산을 이어가야 하기 때문에 고역이라 하지 않을 수 없다. 그래도 이를 따라하다보면 '''정수론에서의 증명과 매우 유사한''' 패턴임을 실감할 수 있는데, 이는 정수론을 대수학의 스타일로 일반화해나가는 장대한 여정의 첫 걸음으로 꼽히기도 한다.

== [[가우스 정수]] 상에서의 나눗셈 정리 ==
[[가우스 정수]]에서도 비슷하게 나눗셈 정리를 주장할 수 있는데, 이 경우는 조금 형태가 달라진다.
아래에서 말하는 [math(N(\pi))]는 가우스 노름으로, [math(\pi=a+bi)]에 대하여 [math(N(\pi)=\left|\pi\right|^2=a^2+b^2)]. 즉 복소수의 유클리드 노름의 제곱으로 정의된다. 이렇게 정의해도 [[노름(수학)|노름]]이 지녀야 할 3가지 조건은 전부 만족하기 때문에[* 첫번째 조건만 살짝 바뀌어서 복소수체의 원소 [math(u)]에 대하여 [math(|u|)]가 아니라 [math(N(u))]가 적용되는 점만 다르다.] 문제 없이 노름으로 작동한다.

>임의의 두 가우스 정수 [math(\alpha, \beta\left(\beta\neq 0\right))]에 대하여, [math(\alpha=\beta\gamma+\rho)]이며 [math(N(\rho)<N(\beta))][* 정확하게는 [math(\displaystyle N(\rho)\leq\frac{1}{2}N(\beta))]]를 만족시키는 가우스 정수 [math(\gamma, \rho)]가 '''{{{#red 거의}}} 유일'''하게 '''존재'''한다.

여기서 '''거의'''라는 문구가 들어가는 이유는 다름아니라 [math(\gamma)]를 정하는 방법에 의해서 발생하는 문제로[* 참고로, 다음과 같이 [math(\displaystyle \frac{\alpha}{\beta}=c+di)]일 때, [math(\gamma=\lfloor c\rfloor+\lfloor d\rfloor i)]로 [math(\gamma)]를 정한다면 유일하다고 단언할 수 있다. 다만, 이 경우에는 나머지의 노름을 제수의 노름과 비교했을 때 그다지 줄어들지 않을 수도 있어서 유클리드 호제법이 적용되기에는 그다지 좋은 성질을 지니고 있다고 할 수 없다. 위와 같이 정하는것은 나머지의 노름이 '''반드시''' 제수의 노름의 절반 이하로 줄어들기 때문에, 유클리드 호제법을 적용하기 좋은 성질을 지니고 있기 때문. 특히 유클리드 정역의 조건상 반드시 제수의 노름보다 나머지의 노름이 줄어들어야 하기에 줄어드는 폭이 큰 본 문단의 기준이 유클리드 정역의 조건을 보다 잘 만족한다. 라고 표현할 수 있다.], [math(\alpha, \beta)]가 복소수이며, [math(\beta\neq 0)]인 이상 [math(\displaystyle \frac{\alpha}{\beta})]는 복소평면상의 복소수로 정해지는 것을 알 수 있다. 그런데, [math(\gamma)]는 가우스 정수인 이상 '''복소평면상의 격자점'''에 있어야 하므로, 이를 정하는 방법을 [math(\displaystyle \frac{\alpha}{\beta})]에 '''가장 가까운''' 격자점으로 정하기 때문에 발생하는 문제로, 다음과 같은 예시를 들 수 있다.

>[math(\alpha=14+13i, \beta=3+i)]
이 경우 [math(\displaystyle \frac{\alpha}{\beta}=5.5+2.5i)]이기에 가장 가까운 격자점에 해당하는 가우스 정수는 [math(5+2i)], [math(5+3i)], [math(6+2i)], [math(6+3i)]의 4개가 존재하며, 그 모두가 위의 나눗셈 정리를 만족하는 [math(\gamma)]가 되는 것을 알 수 있으며, 각각에 대하여 다음과 같이 [math(\rho)]가 정해지며, 그 모두가 [math(\displaystyle N(\beta)=10>5=\frac{1}{2}N(\beta)=N(\rho))]를 만족한다.
>[math(\gamma=5+2i, \rho=1+2i)]
>[math(\gamma=5+3i, \rho=2-i)]
>[math(\gamma=6+2i, \rho=-2+i)]
>[math(\gamma=6+3i, \rho=-1-2i)]

비슷한 경우로 [math(\alpha=23+65i, \beta=6+6i)]인 경우는 [math(\displaystyle \frac{\alpha}{\beta}=\frac{22}{3}+\frac{7}{2}i)]이므로 가장 가까운 격자점은 [math(7+3i, 7+4i)]의 2가지가 있으며, 각각에 대해서 [math(\gamma, \rho)]는 다음과 같다. 역시 [math(\displaystyle N(\beta)=72>\frac{1}{2}N(\beta)=36>26=N(\rho))]를 만족하는 것을 알 수 있다.
>[math(\gamma=7+3i, \rho=-1+5i)]
>[math(\gamma=7+4i, \rho=5-i)]

이와 같이 격자점의 정 중앙에 위치한 경우는 극단적인 케이스지만, [math(\displaystyle \frac{\alpha}{\beta}=a+bi)]에서 [math(a=\lfloor a\rfloor+0.5)]이거나 [math(b=\lfloor b\rfloor+0.5)]인 경우라면 유일하지 않기 때문에 '''거의'''라는 말이 사용되는 것.
일반적으로 [math(\displaystyle \frac{\alpha}{\beta}=a+bi)]의 실수부나 허수부중 하나라도 '''정수+0.5'''의 형태일 경우, 그 외의 상황에서는 유일하던 가우스 정수쌍은 2배로 늘어나며, 둘 모두 '''정수+0.5'''의 형태라면 최대 4개까지 공존할 수 있다. 다르게 표현하자면 [math(\displaystyle \frac{\alpha}{\beta})]의 [math(r)] 근방을 잡았을 때, 이 [math(r)]근방에 격자점이 들어가는 최소의 [math(r)]에 대하여 근방에 들어가는 격자점의 수가 가우스 정수쌍의 수와 같아지는 것. 또한 [math(r)]근방에 연관된 또 다른 특징으로는 [math(\rho)]는 [math(r^2\beta)]가 되는데, 만약 [math(r)]근방에 격자점이 4개 들어가는 경우. 즉 격자의 정 중앙에 위치한 경우의 나머지의 가우스 노름은 제수의 가우스 노름의 '''정확하게 절반'''이 된다. 위의 예시에서는 제수의 가우스 노름은 10이지만 나머지의 가우스 노름은 정확하게 그 절반인 5가 됨을 알 수 있다.[* 이에 대해서의 증명은 간단한데, 격자점 정사각형의 중앙에서 꼭지점까지의 거리가 [math(\displaystyle \frac{1}{\sqrt 2})]이므로 가우스 노름에 의해 격자점과 중앙점의 차이의 노름이 [math(\displaystyle \frac{1}{2})]임과 유클리드 노름의 제곱인 가우스 노름이 곱에 대하여 보존된다는 것을 이용하면 쉽게 보일 수 있다. 즉, 가우스 정수에서의 나머지의 노름은 제수의 노름의 절반을 넘을 수 없다. 정확하게는 격자점에서 [math(\displaystyle \frac{\alpha}{\beta}=a+bi)]까지의 거리와 비율이 같으며, 그 최대값은 정중앙에 해당하는 [math(\displaystyle \frac{1}{2})]가 되는 것.][*증명 [math(\displaystyle \frac{\alpha}{\beta})]에 가장 가까운 격자점을 [math(\delta)], 그리고 그 차이를 [math(\epsilon)]이라고 하면 [math(\displaystyle \frac{\alpha}{\beta}=\delta+\epsilon)]이 되는걸 이용한다. [math(\displaystyle \frac{\alpha}{\beta}=\delta+\epsilon)]이기에 [math(\displaystyle \alpha=\beta\cdot\delta+\beta\epsilon)]이 되고, [math(\delta)]는 가우스 정수이므로 [math(\delta=\gamma, \beta\epsilon=\rho)]라고 둔 뒤, [math(\beta\epsilon=\rho)]만 남기고 이항하여 노름을 씌우면 증명이 끝난다. [math(\epsilon)]이 격자점 내부의 점이기 때문에 격자점과의 최대 거리는 [math(\displaystyle \frac{1}{\sqrt 2})]이라는 것은 앞 각주에서 보였기 때문.]
== 관련 문서 ==
 * [[유클리드 호제법]]
 * [[나머지 정리]]
 * [[최대공약수]]


[[분류:정수론]]