반응형
중고교 수학에서 젯수와 피젯수를 몫과 나머지에 관한 식으로 정리한 적이 있습니다. 이제 그 정리가 왜 성립하고, 유일하게 존재하는지를 증명하여 확실히 옳음을 확인해 보겠습니다.
1. 나눗셈 정리
정리(N.T) 1.4
[나눗셈 정리(Division Theorem)]
임의의 두 정수 a,b(b≥1) 이 주어졌을 때, 다음의 등식을 만족하는 유일한 정수 q 와 r 이 존재한다. 이들을 각각 '몫(quotient)'과 '나머지(remainder)'이라 부른다.
a=bq+r(0≤r<b) 이 관계를 나눗셈 과정으로 생각하면, a 는 나누어지는 수이니 '피젯수'이고, b 는 나누는 수이니 '젯수'라 한다.1
증명) 존재성과 유일성을 각각 순서대로 증명해보자.
i) 존재성 : T={a,a−b,a−2b,⋯} 이라 가정하자. S를 T에 속한 음이 아닌 정수의 집합 S={a−mb∣m∈Z,a−mb≥0} 라 정의한다. 여기서 a−mb≥0 을 만족하는 정수 m 중 m=−|a| 를 택하자. 그러면
a−mb=a+|a|b≥0(∵b≥1)
이 되고, 이는
a+|a|={2a (a≥0)0 (a<0)
이기 때문이다.
만일 a−mb=a+|a|b=0∈S 이면 0 은 S 의 최소원소가 된다. 만일 a−mb=a+|a|b≠0 이더라도 S 는 적어도 하나의 원소를 가지기 때문에, 공집합이 아니다. 고로 자연수의 정렬성(Well-Ordering Principle)에 의하여 공집합이 아닌 자연수의 부분집합은 최소 원소를 가지고, 이를 r 이라 가정하자. 그러면
r=a−mb=a−qb≥0
인 정수 r이 존재하고, 이때의 m을 특별히 m=q 라 표기한다. 또한 r 의 범위가 r<b 임을 보여야 하는데 만일 r≥b 라 가정하면 r−b 는 자연수이므로 r−b∈S 이다. 그런데 r이 S 의 최소 원소이고 r>r−b 이므로 이는 모순이다. 따라서 r<b 이다.
ii) 유일성
a=bq′+r′ 을 만족하는 q′,r′∈Z 가 존재한다고 가정하자. (0≤r′≤b) 이때 a=bq+r 을 만족함을 이미 알고 있으므로 양변을 각각 빼면
0=b(q−q′)+(r−r′)⇒1b(r−r′)=q−q′
가 된다. b≥1 이고 0≤r≤1,0≤r′≤1 이므로 0≤r−r′<1 이다. 따라서
0≤1b(r−r′)<1b<bb=1
이다. 그러면 자연스럽게 우변에서도
0≤q−q′<1 이다.
그러나 q−q′∈Z 이므로 q−q′=0 이어야 한다. 따라서 1b(r−r′) 이므로 r=r′ 이고 q=q′ 이다. ◼
[참고문헌]
Introduction to Number Theory - William W. Adams, Larry Joel Goldstein
- 문법적으로 사이시옷 표기를 적지 않는 것이 적절하나 저는 그냥 적겠습니다. 그리고 '제(除)'는 '덜다 제'라는 한자입니다. 나눈다는 것은 결국 쪼개어 줄인다는 의미가 있기 때문에 이러한 표현을 사용한 것으로 보입니다. [본문으로]
'정수론(Number Theory) > 나눗셈 이론' 카테고리의 다른 글
| 유클리드 호제법, 유클리드 알고리즘(Euclid algorithms) (1) | 2024.01.19 |
|---|---|
| 정수에서 서로소의 의미(relatively prime in the Number theory) (0) | 2024.01.18 |
| 베주 항등식(Bezout's identity) (0) | 2024.01.18 |
| 최대공약수(Greatest common divisor) (0) | 2023.02.05 |
| 나눗셈과 나누어 떨어짐(Divisibility) (0) | 2023.02.05 |
댓글