ko 나눗셈 알고리즘
수학이야기 2015. 1. 12. 15:28정수론에 쓰이는 나눗셈 알고리즘을 정리해 둔다.
공집합이 아닌 자연수 집합의 모든 부분집합 S⊂N(S≠ϕ)는 최소 원소를 가진다. 다시 말하면 ∀b∈S에 대하여 a≤b인 원소 a가 존재한다. 이것은 자연수가 가진 고유한 성질로 증명없이 받아들이는 공리로 생각하자.
S⊂N(S≠ϕ)에서
(1) 1∈S
(2) k∈S⇒k+1∈S
을 만족하면 S=N이다.
증명S≠N라고 가정하자.
N−S≠ϕ이므로 최소 원소가 존재한다. 최소 원소를 m이라고 하자.
가정 (1)에서 1∈S이므로 m≠1이다. m>1이므로 m−1∈N이다.
m−1<m이고 m은 N−S의 최소 원소이므로 m−1∈S이다.
가정 (2)에 따라 m−1∈S이면 m∈S이므로 모순이다.
∴S=N
가정 (2)를 {1,2,⋯,k}⊆S⇒k+1∈S를 바꾸면 강한 수학적 귀납법이다.
∀a,b∈N에 대하여 na≥b인 양의 정수 n이 존재한다.
증명 명제가 거짓이라고 가정하자. 즉, 모든 자연수 n에 대하여 na≤b인 어떤 자연수 a,b가 있다고 하자.
이제 아래와 같은 집합을 생각하자.
S={b−na|n∈N}
S는 모두 자연수로 이루어져 있으므로 최소 원소가 존재한다.
그 원소가 b−ma라고 하자.
b−(m+1)a∈S이다. 그런데 b−(m+1)a=b−ma−a<b−ma이므로 모순이다.
따라서 아르키메데스 성질은 참이다.
두 정수 a,b(b>0)가 주어지면 아래를 만족하는 정수 q와 r이 유일하게 존재한다.
a=qb+r0≤r<b
a를 b로 나누었을 때, q를 몫(quotient) r은 나머지(remainder)로 부른다.
증명 아래와 같은 집합을 생각하자.
S={a−xb|x∈Z;a−xb≥0}
b≥1이므로 |a|b≥|a|이다.
a−(−|a|)b=a+|a|b≥a+|a|≥0
x=−|a|로 생각한다면 a−xb∈S이므로 S≠ϕ이다.
이제 S의 최소 원소를 r=a−qb라고 하자. 0≤r은 당연하므로 r<b임을 보이면 된다.
만약 r≥b라고 하면
a−(q+1)b=(a−qb)−b=r−b≥0
이므로 r−b∈S이다. 이것은 r이 최소 원소라는 가정에 모순이다.
따라서, q,r이 존재한다. 이제 유일하게 존재함을 증명하기 위해 아래와 같이 다른 표현이 있다고 가정하자.
a=qb+r=q′b+r′
r′−r=b(q−q′)
|r′−r|=b|q−q′|
0≤r,r′<b이므로 0≤|r′−r|<b이다.
따라서, 0≤|q−q′|<1이므로 |q−q′|=0이다.
∴q=q′,r=r′
따름정리
두 정수 a,b가 주어지면 아래를 만족하는 정수 q와 r이 유일하게 존재한다.
a=qb+r0≤r<|b|
정수를 정수로 나눌 때, 언제나 몫과 나머지는 유일하게 존재한다.
Français
Deutsch
Italiano
Español
English
简体中文
日本語
