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

This page was last edited on 14 November 2021, at 12:56.
< 페미위키:포크 프로젝트‎ | 리브레 위키

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

1 진술

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

이 유일하게 존재한다.

2 증명

2.1 존재성

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

로 두면 이므로 이기 때문에 S는 공집합이 아니다. 그러므로 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 r이라 하자. 그러면 r≥0이고 가 존재한다. 그러면 인데, r<b임을 보이자. 라고 가정하자. 그러면 이므로

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

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

이 존재한다는 것을 보인 것이다.

2.2 유일성

이제 어떤 가 존재해서

구문 분석 실패 (알 수 없는 함수 "\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} 이므로 이다. 그러므로 이 되어 원하는 결론을 얻는다.

3 확장

나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 에 대하여 두 서수 가 유일하게 존재하여 이다.

4 같이 보기

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