나눗셈 정리

정수론 Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈	약수·배수	배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
	약수들의 합에 따른 수의 분류	완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
	정리	베주 항등식 · 산술의 기본정리 · 나눗셈 정리
	기타	유클리드 호제법 · 서로소
디오판토스 방정식		페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류	소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야	대수적 정수론(국소체) · 해석적 정수론
산술함수	뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리	그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타	에라토스테네스의 체 · 윌런스의 공식

}}}}}}}}} ||

1. 개요2. 증명

2.1. 존재성2.2. 유일성

3. 활용4. 가우스 정수 상에서의 나눗셈 정리5. 관련 문서

1. 개요

Division Algorithm

처음 나눗셈을 배울 때 몫과 나머지가 당연히 존재한다고 생각하고 나눗셈을 한다. 하지만 소인수분해의 존재성과 마찬가지로 몫과 나머지의 존재성은 당연한 결과가 아니며[1] 수학적인 증명이 필요하다. 나눗셈 정리는 우리가 나눗셈을 통해 몫과 나머지를 자연스럽게 구하게 할 수 있게 만들어 주는 정리이다. 자세한 정리는 아래와 같다.

임의의 양의 정수 [math(a,b)]에 대하여, [math(b=aq+r,\,\left(0\leq r<a\right))]를 만족시키는 정수 [math(q,r)]이 유일하게 존재한다.

2. 증명

크게 존재성과 유일성, 두 파트로 나뉜다.

2.1. 존재성

집합 [math(A=\left\{b-na|n\in \mathbb{Z},\, b-an\geq0\right\})]을 생각하자. 그럼 집합 [math(A)]는 공집합이 아니고,[2] [math(A\subseteq \mathbb{N})][3]이므로 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)]이다.

2.2. 유일성

3. 활용

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

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

4. 가우스 정수 상에서의 나눗셈 정리

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

임의의 두 가우스 정수 [math(\alpha, \beta\left(\beta\neq 0\right))]에 대하여, [math(\alpha=\beta\gamma+\rho)]이며 [math(N(\rho)<N(\beta))][7]를 만족시키는 가우스 정수 [math(\gamma, \rho)]가 거의 유일하게 존재한다.

여기서 거의라는 문구가 들어가는 이유는 다름아니라 [math(\gamma)]를 정하는 방법에 의해서 발생하는 문제로[8], [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가 됨을 알 수 있다.[9][증명]

5. 관련 문서

[1] 당장 정수에서 유리수로만 올라가도 나머지가 존재하지 않는다.[2] [math(n=0)]일 때, [math(b\in A)]이므로.[3] 집합론에서는 0도 자연수에 포함한다고 본다. 그러는 편이 덧셈의 항등원이 존재하니 더 풍부한 성질을 갖기고 하고...[4] 즉 몫과 나머지가 유일하지 않다고 하면[5] [math(p,q)]가 둘 다 정수이고, [math(p\neq q)]이므로, 두 수의 차의 절대값은 최소 1 이상이다.[6] 첫번째 조건만 살짝 바뀌어서 복소수체의 원소 [math(u)]에 대하여 [math(|u|)]가 아니라 [math(N(u))]가 적용되는 점만 다르다.[7] 정확하게는 [math(\displaystyle N(\rho)\leq\frac{1}{2}N(\beta))][8] 참고로, 다음과 같이 [math(\displaystyle \frac{\alpha}{\beta}=c+di)]일 때, [math(\gamma=\lfloor c\rfloor+\lfloor d\rfloor i)]로 [math(\gamma)]를 정한다면 유일하다고 단언할 수 있을 것 처럼 보인다. 문제는, 이 경우에는 나머지의 노름을 제수의 노름과 비교했을 때 그다지 줄어들지 않을 수도 있고, 오히려 늘어날 가능성도 절대로 배제할 수 없어서([math(\alpha=8+81i, \beta=36+12i)]라고 두면 [math(\displaystyle \frac{\alpha}{\beta}=\frac{7}{8}+\frac{47}{24}i)]이므로 [math(\gamma=\lfloor c\rfloor+\lfloor d\rfloor i=i)]가 된다. 이를 토대로 [math(\rho)]를 구하면 [math(20+45i)]가 되어서 [math(N(\beta)=1440, N(\rho)=2425)]가 된다.) 유클리드 호제법이 적용되기에는 절대로 좋은 성질을 지니고 있다고 할 수 없다. 위와 같이 정하는것은 나머지의 노름이 반드시 제수의 노름의 절반 이하로 줄어들기 때문에, 유클리드 호제법을 적용하기 좋은 성질을 지니고 있기 때문. 특히 유클리드 정역의 조건상 반드시 제수의 노름보다 나머지의 노름이 줄어들어야 하기에 줄어드는 폭이 큰 본 문단의 기준이 유클리드 정역의 조건을 보다 잘 만족한다. 라고 표현할 수 있다.[9] 이에 대해서의 증명은 간단한데, 격자점 정사각형의 중앙에서 꼭지점까지의 거리가 [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})]이라는 것은 앞 각주에서 보였기 때문.