1. 정리 :
a, b (a>b, a와 b는 양의 정수)의 최대공약수가 G라고 한다면,
b와 a를 b로 나눈 나머지 r(0 <= r <b) 역시 최대공약수를 G로 가진다.
2. 증명 :
a와 b의 최대공약수를 G라 한다면, a = mG, b=nG 이고, m, n은 서로소(1을 제외한 공약수 없음)인 양의 정수이다.
a를 b로 나눈 나머지를 r이라고 할 때 a = bq + r 이 성립하는 유일한 정수 q가 존재한다.
위 식 a = bq + r 에 a = mG, b=nG를 각각 대입하면 mG = nGq + r이고, r= G(m-nq)이다.
b=nG 이므로 b와 r의 최대공약수가 G가 되려면 n과 m-nq가 서로소가 되어야 한다.
아래 내용을 이해하기 위해서는 귀류법을 알아야 합니다.
(* 귀류법 : 부정하려는 명제가 맞다고 가정했을 때 생기는 모순을 통해 그 명제를 부정하는 방법)
만약 n과 m-nq에 공약수가 존재한다고 가정하면
n= Lk, m-nq = Lk’(k, k’는 서로소인 양의 정수)로 표현할 수 있게 된다.
이 때 n = Lk 이고 m = nq + Lk’ = Lkq + Lk’ = L(kq + k’)이므로
이는 n과 m이 서로소라는 가정에 모순되게 된다.
따라서 앞에서 n과 m-nq에 공약수가 존재한다는 가정이 부정되게 되므로,
n과 m-nq는 서로소이고
따라서 b와 r의 최대공약수는 G가 된다.
(증명 끝)