< 페미위키:포크 프로젝트 | 리브레 위키
나눗셈 정리(Division algorithm)는 임의의 정수를 양의 정수로 나누었을 때 몫과 나머지가 하나로 정해진다는 명제다. 여러분이 정수의 나눗셈을 할 때 결과가 하나뿐이라는 걸 보장한다.
진술
임의의 정수 a, b (단, b>0)에 대해
인 이 유일하게 존재한다.
증명
존재성
정수 가 주어지고 b>0이라고 하자. 집합 S를 다음과 같이 정의하자.
로 두면 이므로 이기 때문에 S는 공집합이 아니다. 그러므로 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 r이라 하자. 그러면 r≥0이고 인 가 존재한다. 그러면 인데, r<b임을 보이자. 라고 가정하자. 그러면 이므로
이다. 따라서 인데 구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle r-b \lt r} 이므로 r이 S의 최소원소라는 사실에 모순이다. 따라서 r<b이다. 여기까지 하면
- 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle a=bq+r,\quad 0\le r \lt b}
인 이 존재한다는 것을 보인 것이다.
유일성
이제 어떤 가 존재해서
- 구문 분석 실패 (알 수 없는 함수 "\lt"): {\displaystyle a=bq'+r',\quad 0\le r \lt b}
를 만족한다고 가정하자. 그러면
이므로 이다. 이때 구문 분석 실패 (알 수 없는 함수 "\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} 이므로 이다. 그러므로 이 되어 원하는 결론을 얻는다.
확장
나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 에 대하여 두 서수 와 가 유일하게 존재하여 이다.
같이 보기