잔글 (→확장) |
잔글 (봇: 자동으로 텍스트 교체 (-집합 (수학)|집합 +집합)) |
||
(사용자 5명의 중간 판 5개는 보이지 않습니다) | |||
1번째 줄: | 1번째 줄: | ||
'''나눗셈 정리'''(Division algorithm)는 임의의 [[정수]]를 양의 정수로 나누었을 때 몫과 나머지가 하나로 정해진다는 [[명제]]다. 여러분이 정수의 나눗셈을 할 때 결과가 하나뿐이라는 걸 보장한다. | |||
'''나눗셈 정리(Division algorithm) | |||
== 진술 == | == 진술 == | ||
임의의 정수 ''a'', ''b'' (단, ''b''>0)에 대해 | 임의의 정수 ''a'', ''b'' (단, ''b''>0)에 대해 | ||
8번째 줄: | 7번째 줄: | ||
== 증명 == | == 증명 == | ||
=== 존재성 === | === 존재성 === | ||
정수 <math>a,b</math>가 주어지고 ''b''>0이라고 하자. [[ | 정수 <math>a,b</math>가 주어지고 ''b''>0이라고 하자. [[집합]] ''S''를 다음과 같이 정의하자. | ||
: <math>S=\{a-bx:(x\in \mathbb{Z})\text{ and } (a-bx\ge 0)\}</math> | : <math>S=\{a-bx:(x\in \mathbb{Z})\text{ and } (a-bx\ge 0)\}</math> | ||
<math>x=-|a|</math>로 두면 <math>a+b|a|\ge 0</math>이므로 <math>a+b|a|\in S</math>이기 때문에 ''S''는 공집합이 아니다. 그러므로 [[정렬순서공리]]에 의해 ''S''의 최소원소가 존재한다. 이 원소를 ''r''이라 하자. 그러면 ''r''≥0이고 <math>r=a-bq</math>인 <math>q\in\mathbb{Z}</math>가 존재한다. 그러면 <math>a=bq+r</math>인데, ''r''<''b''임을 보이자. <math>r\ge b</math>라고 가정하자. 그러면 <math>r-b\ge 0</math>이므로 | <math>x=-|a|</math>로 두면 <math>a+b|a|\ge 0</math>이므로 <math>a+b|a|\in S</math>이기 때문에 ''S''는 공집합이 아니다. 그러므로 [[정렬순서공리]]에 의해 ''S''의 최소원소가 존재한다. 이 원소를 ''r''이라 하자. 그러면 ''r''≥0이고 <math>r=a-bq</math>인 <math>q\in\mathbb{Z}</math>가 존재한다. 그러면 <math>a=bq+r</math>인데, ''r''<''b''임을 보이자. <math>r\ge b</math>라고 가정하자. 그러면 <math>r-b\ge 0</math>이므로 | ||
26번째 줄: | 25번째 줄: | ||
== 확장 == | == 확장 == | ||
나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 <math>\alpha, \beta</math>에 대하여 두 서수 <math>\gamma < \beta</math>와 <math>\delta</math>가 유일하게 존재하여 <math>\alpha = \beta \cdot \delta + \gamma</math>이다. | |||
나눗셈 정리는 ordinal으로도 확장할 수 있다. 즉 두 서수 <math>\alpha, \beta</math>에 대하여 두 서수 <math>\gamma < \beta</math>와 <math>\delta</math>가 유일하게 존재하여 <math>\alpha = \beta \cdot + \gamma</math>이다. | |||
== 같이 보기 == | == 같이 보기 == | ||
{{빈 문단}} | |||
{{각주}} | |||
[[분류:정수론]] | [[분류:정수론]] | ||
[[분류:추상대수학]] | [[분류:추상대수학]] | ||
[[분류:수학 정리]] | [[분류:수학 정리]] |
2020년 9월 20일 (일) 15:44 기준 최신판
나눗셈 정리(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]이다.