페미위키:포크 프로젝트/리브레 위키/나눗셈 정리

나눗셈 정리(Division algorithm)는 임의의 정수를 양의 정수로 나누었을 때 몫과 나머지가 하나로 정해진다는 명제다. 여러분이 정수의 나눗셈을 할 때 결과가 하나뿐이라는 걸 보장한다.

1 진술

임의의 정수 a, b (단, b>0)에 대해

$a=bq+r,\quad 0\leq r<b$

인 $q,r$이 유일하게 존재한다.

2 증명

2.1 존재성

정수 $a,b$가 주어지고 b>0이라고 하자. 집합 S를 다음과 같이 정의하자.

$S=\{a-bx:(x\in \mathbb {Z} ){\text{ and }}(a-bx\geq 0)\}$

$x=-|a|$로 두면 $a+b|a|\geq 0$이므로 $a+b|a|\in S$이기 때문에 S는 공집합이 아니다. 그러므로 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 r이라 하자. 그러면 r≥0이고 $r=a-bq$인 $q\in \mathbb {Z}$가 존재한다. 그러면 $a=bq+r$인데, r<b임을 보이자. $r\geq b$라고 가정하자. 그러면 $r-b\geq 0$이므로

$r-b=(a-bu)-b=a-b(u+1)\geq 0$

이다. 따라서 $r-b\in S$인데 구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle r-b \lt r} 이므로 r이 S의 최소원소라는 사실에 모순이다. 따라서 r<b이다. 여기까지 하면

구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle a=bq+r,\quad 0\le r \lt b}

인 $q,r$이 존재한다는 것을 보인 것이다.

2.2 유일성

이제 어떤 $q',r'\in \mathbb {Z}$가 존재해서

구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle a=bq'+r',\quad 0\le r \lt b}

를 만족한다고 가정하자. 그러면

$bq+r=bq'+r'$

이므로 $b(q-q')=r'-r$이다. 이때 구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle 0\le r \lt b,\;0\le r' \lt b} 이므로

구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle -b \lt b(q-q') \lt b,}

따라서 구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle -1 \lt q-q' \lt 1} 이므로 $q-q'=0$이다. 그러므로 $r'-r=0$이 되어 원하는 결론을 얻는다.

3 확장

나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 $\alpha ,\beta$에 대하여 두 서수 $\gamma <\beta$와 $\delta$가 유일하게 존재하여 $\alpha =\beta \cdot \delta +\gamma$이다.

4 같이 보기

빈 문단 이 문단은 비어 있습니다. 내용을 추가해 주세요.