Division Theorem(나눗셈 정리) 증명

나눗셈 정리란 다음과 같다

 

핵심은 다음과 같다.

위 조건을 만족시키는 정수 q와 r이 반드시 존재한다.

그리고 q와 r은 반드시 유일하다.

 

그러면 위 두 가지 사실을 증명해 보도록 하자.

1. b=aq+r을 만족시키는 정수 q와 r이 존재한다.

2. 이 q와 r은 유일하다.

 

존재성의 증명

집합 S = {b-na | n은 정수,b-na>=0}

여기서 a,b,n은 모두 정수이므로 b-na>=을 만족시키는 정수쌍(a,b,c)가 반드시 존재한다.

따라서 S는 공집합이 아니므로, 정렬 원리에 의하여 S는 가장 작은 원소 r을 가진다.

 

집합 S의 가장 작은 원소 r이 존재한다는 것을 증명하였다.

 

그러면 이 r이 반드시(0<=r<a)라는 것을 증명 해보자

 

수학에서는 어떠한 사실을 증명할 때, 특정 사실을 가정한 후 논리를 전개해 나가면서 모순에 도달하면, 가정한 사실이 거짓이라는 것을 반증하는 기술을 많이 사용한다

 

r >= a라고 가정을 해보자.

b-na = r의 양변에 a를 빼면

b-n(a+1) = r - a 이라는 식이 도출된다

 

r - a >=0이므로 b-n(a+1)은 집합 S의 원소이며

r보다 작은 값을 가진다.

여기서 모순이 발생한다

집합 S의 가장 작은 원소를 r이라고 정의하였는데

b-n(a+1)이라는 r보다 더 작은 S의 원소가 도출된 것이다. (모순)

 

 

따라서 방금 우리가 한 위 가정(r>=a)은 거짓이라는 결론에 도달하게 된다.

 

b=aq+r을 만족시키는 q와 r값이 존재한다는 것을 증명 완료하였다.

이제는 q와 r값이 유일하다는 것을 증명할 차례이다.

 

유일성의 증명

b=a*q+r을 만족하는 서로다른 q와 r 쌍이 존재하고, 그 값을 q1,r1,q2,r2라고 해보자

그러면 다음 식이 성립한다

 

b = a*q1+r1 (0 <= r1 < a) ... 1

b = a*q2+r2 (0 <= r2 < a) ... 2

 

1식과 2식을 빼면

a(q2-q1) = r1-r2이다

 

-a < r1-r2 < a 이므로

-a < a(q2-q1) < a이고

-1 < q2 - q1 < 1이다

 

q1,q2는 정수이므로

위 등식을 만족하는 q2-q1은 0이다

 

따라서 q1=q2이고 r1=r2이다.

서로 다른 q와 r쌍은 존재하지 않으며 유일하다는 것이 증명되었다.