안녕하세요,,
오늘은 나눗셈 정리에 대해서 알아볼까 합니다.
나눗셈 정리는 정수의 가장 기초적인 정리입니다.
정수는 상당히 어려울 수 있는(그리고 귀찮을 수 있는) 분야입니다.
그리고 제가 설명할 정수는 수(상) 까지는 수학이 되어 있어야 이해할 수 있는 부분입니다.
그럼 시작해 보겠습니다.
**나눗셈 정리**
나눗셈 정리는 아마 여러분이 다 알지만 증명을 해 보지는 않은 그런 정리일 것입니다.
정리는 매우 간단합니다.
정리) 어떤 수를 다른 한 수로 나누었을 때의 몫과 나머지는 하나이다.
- 이걸 좀 더 멋있게 쓰면...
"임의의 정수 a, b (단, b>0)에 대하여 a=bq+r,0≤r<b 인 q,r 이 유일하게 존재한다." 정도가 되겠네요.
증명해 보겠습니다.
pf)
i) 존재성 증명
집합 S를 다음과 같이 정의하겠습니다.
S = {b-aq | b-aq>=0, q는 정수}
이때 자연수의 정렬성(S가 정수집합이고, 공집합이 아니면 S의 최소원소가 존재한다.)에 의해
S가 공집합이 아님을 증명하면 q와 r이 존재함을 증명할 수 있습니다.
여기서 자연수의 정렬성 증명은 생략하겠습니다.(자연수의 정렬성 증명만 한판을 써야되요 ㅋㅋㅋ)
q = -|b| 라 하면
b-aq >= b-(-|b|) >= b + |b| >=0
따라서 S는 0이 아닙니다.
by 자연수의 정렬성, S의 최소원소 r이 존재한다고 할 수 있습니다.
여기서 만약 r이 0이라면 0이 최소원소입니다.
하지만 r이 0이 아니라면 r < a 라는 것을 증명해야 합니다.
귀류법 사용하면
r >= a라 하자.
r > r-a = b-aq-a = b-a(q+1) = S의 원소 이므로 r이 최소원소임에 모순이다.
-> r<a
이제 존재성이 증명되었습니다.
ii) 유일성 증명
b = aq1 +r1, b = aq2 + r2라고 합시다.(귀류법)
0<=r1, r2 < a 이므로
-a < r1 - r2 < a
r1 - r2 = a(q2 - q1) 이므로
-1 < q2-q1 < 1, q2, q1 은 정수이므로 q2-q1은 0이다.
-> q2 = q1, r2 = r1 이므로 q와 r은 유일하다
이렇게 증명이 끝났습니다.
다음에는 유클리드 호제법과 유클리드 알고리즘에 대하여 설명하겠습니다.
오타와 잘못된 점 지적은 환영입니다.