나눗셈 정리(Division algorithm)는 임의의 정수를 양의 정수로 나누었을 때 몫과 나머지가 하나로 정해진다는 명제다. 여러분이 정수의 나눗셈을 할 때 결과가 하나뿐이라는 걸 보장한다.
진술[편집 | 원본 편집]
임의의 정수 a, b (단, b>0)에 대해
- [math]\displaystyle{ a=bq+r,\quad 0\le r \lt b }[/math]
인 [math]\displaystyle{ q,r }[/math]이 유일하게 존재한다.
증명[편집 | 원본 편집]
존재성[편집 | 원본 편집]
정수 [math]\displaystyle{ a,b }[/math]가 주어지고 b>0이라고 하자. 집합 S를 다음과 같이 정의하자.
- [math]\displaystyle{ S=\{a-bx:(x\in \mathbb{Z})\text{ and } (a-bx\ge 0)\} }[/math]
[math]\displaystyle{ x=-|a| }[/math]로 두면 [math]\displaystyle{ a+b|a|\ge 0 }[/math]이므로 [math]\displaystyle{ a+b|a|\in S }[/math]이기 때문에 S는 공집합이 아니다. 그러므로 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 r이라 하자. 그러면 r≥0이고 [math]\displaystyle{ r=a-bq }[/math]인 [math]\displaystyle{ q\in\mathbb{Z} }[/math]가 존재한다. 그러면 [math]\displaystyle{ a=bq+r }[/math]인데, r<b임을 보이자. [math]\displaystyle{ r\ge b }[/math]라고 가정하자. 그러면 [math]\displaystyle{ r-b\ge 0 }[/math]이므로
- [math]\displaystyle{ r-b=(a-bu)-b=a-b(u+1)\ge 0 }[/math]
이다. 따라서 [math]\displaystyle{ r-b\in S }[/math]인데 [math]\displaystyle{ r-b \lt r }[/math]이므로 r이 S의 최소원소라는 사실에 모순이다. 따라서 r<b이다. 여기까지 하면
- [math]\displaystyle{ a=bq+r,\quad 0\le r \lt b }[/math]
인 [math]\displaystyle{ q,r }[/math]이 존재한다는 것을 보인 것이다.
유일성[편집 | 원본 편집]
이제 어떤 [math]\displaystyle{ q',r'\in \mathbb{Z} }[/math]가 존재해서
- [math]\displaystyle{ a=bq'+r',\quad 0\le r \lt b }[/math]
를 만족한다고 가정하자. 그러면
- [math]\displaystyle{ bq+r=bq'+r' }[/math]
이므로 [math]\displaystyle{ b(q-q')=r'-r }[/math]이다. 이때 [math]\displaystyle{ 0\le r \lt b,\;0\le r' \lt b }[/math]이므로
- [math]\displaystyle{ -b \lt b(q-q') \lt b, }[/math]
따라서 [math]\displaystyle{ -1 \lt q-q' \lt 1 }[/math]이므로 [math]\displaystyle{ q-q'=0 }[/math]이다. 그러므로 [math]\displaystyle{ r'-r=0 }[/math]이 되어 원하는 결론을 얻는다.
확장[편집 | 원본 편집]
나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 [math]\displaystyle{ \alpha, \beta }[/math]에 대하여 두 서수 [math]\displaystyle{ \gamma \lt \beta }[/math]와 [math]\displaystyle{ \delta }[/math]가 유일하게 존재하여 [math]\displaystyle{ \alpha = \beta \cdot \delta + \gamma }[/math]이다.