[기초 정수론] 07. 나눗셈 정리

1. 나눗셈 정리

 주어진 정수  a, b에 대해, b>0, 다음을 만족하는 유일한 정수 q,r이 존재한다. 

a=qb+r   0 ≤ r < b

a를 b로 나누는 연산에서, q를 몫(quotient), r은 나머지(remainder)라 부른다. 

 

Proof

다음 집합이 공집합이 아님을 먼저 보이도록 하자. 

S={a-xb|x는 정수; a-xb≥0}

a-xb를 음이 아닌 수로 만드는 x의 값이 있음을 실제로 구하면 충분하다. 정수 b≥1 이므로 |a|b ≥ |a| 이고 따라서

a-(-|a|)b = a+a|a|b ≥ a + |a| ≥ 0

x=-|a|라 하면 a-xb는 S에 속한다. 이제 정렬성의 원리를 적용할 준비가 되었다. 이로부터 집합 S는 가장 작은 정수 r을 포함한다. S의 정의에 의해, 다음을 만족하는 정수 q가 존재한다. 

r=a-qb   0 ≤ r

r<b임을 보이자. 만일 아니라면, r≥b이고 다음 식

a-(q+1)b=(a-qb)-b=r-b ≥0

을 만족한다면, a-(q+1)b는 집합 S에 속한다. 하지만, a-(q+1)b=r-b<r이고 r이 S의 가장 작은 원소라는데 모순이다. 따라서 r<b이다. 

 이제, r과 b의 유일성을 보이자. a가 다음 두 가지 형태로 표현될 수 있다고 가정하자. 

a=qb+r=q'b+r', 0 ≤ r <b, 0 ≤ r' < b

그러면 r' - r = b(q - q')이고 곱의 절대값은 절대값의 곱과 같으므로,

| r' - r | = b | q - q' |

이다. 두 부등식, -b < r ≤  0 과 0 < r' < b를 더함으로써, -b < r'-r <b 또는 |r'-r| < b를 얻을 수 있다. 따라서 b| q- q'|<b이고 이는

0 ≤|q-q'| <1

을 나타낸다. 

 |q - q'|이 음이 아닌 정수이므로, | q-q' |=0. 따라서 q=q'. 이로부터 r=r'도 얻을 수 있고, 증명이 마무리 되었다. 

 

2. 일반화된 나눗셈 정리

a, b가 정수이면 (b≠0) 다음 식을 만족하는 유일한 정수 q,r이 존재한다.

a=qb+r  0 ≤ r < |b|

 

Proof

b가 음인 경우만 고려하면 된다. |b| > 0이므로, 정리 2.1에 의해 다음을 만족하는 유일한 정수 q', r을 만들 수 있다. 

a=q'|b|+r  0 ≤ r < |b|

|b| = -b이므로 0 ≤ r < |b|인 a=qb+r을 만족하기 위해 q=-q'라 택하면 된다. 

 

1) b=2인 경우 가능한 나머지는 r=0 또는 r=1이다. r=0인 경우, 정수 a는 a=2q 형태를 가지고 짝수라 부른다. r=1인 경우는 a=2q+1이고 홀수라 한다. 

2) (2q)^2=4k 또는 (2q+1)^2=4(q^2+q)+1=4k+1이다. 즉, 정수의 제곱은 4로 나누었을 때 나머지가 0 또는 1이다.

3) 나눗셈 정리에 의하여 모든 정수는 4q, 4q+1, 4q+2, 4q+3으로 표현된다. 이 분류에서 4q+1, 4q+3만 홀수이다. 이들을 제곱하여 다음을 얻는다. 

 

그리고 마찬가지로,

 

즉, 모든 홀수의 제곱은 8k+1 형태이다. 

 

 

3. 예제

모든 1 이상의 정수 a에 대해 a(a^2+3)이 정수임을 보일 수 있다. 나눗셈 정리에 의해 모든 a는 3q, 3q+1,3q+2로 표현된다. 첫 번째 경우를 살펴보면, 

 

이것은 당연히 정수이다. 비슷하게, a= 3q+1인 경우 역시

 

이고 a(a^2+2)/3은 정수이다. 마지막으로 a=3q+2인 경우 역시 마찬가지이다. 

 

결과적으로, 우리의 결론은 모든 경우에 성립한다.