최대 공약수 (Greatest Common Divisor)

목차로 돌아가기

 

우리는 숫자를 나누게 되면 나머지가 남는다고 배웁니다. 이를 엄밀하게 적으면

 

정리 1 정수 \( a, b \) 이 있고 \( b \neq 0 \) 라고 가정하자. 그러면 다음 두 성질을 만족하는 \( q, r \) 이 유일하게 존재한다.

(성질 1) \( a = bq + r \)

(성질 2) \( 0 \leq r < |b| \)

 

증명

우리는 (1) 존재한다는 것을 보여줘야되고 (2) 유일하다는 것을 보여줘야됩니다.

 

먼저서 위의 성질을 만족하는 쌍 \( (q,r) \) 이 존재한다는 것을 보여줍시다. 다음 집합을 생각해봅시다. 

\[  S := \{ a-bq' ~|~ q' \in \mathbb{Z} \text{ 그리고 } a-bq' \geq 0 \} \]

숫자들이 0 보다는 커야되기 때문에 최소가 존재합니다. 집합 \( S \) 내에서 가장 작은 원소를 \( r = a - bq \) 라고 씁시다. 그럼 당연히

\[ a = bq + r \]

이 성립합니다.

 

두번째 성질을 보여주기 위해서는 \( |b| < r \) 이 성립한다고 가정하고 모순을 이끌어내봅시다.

 

I. 먼저 \( b \geq 0 \) 라고 가정해봅시다. 그러면 \( b < r \Rightarrow 0 < r- b < r \) 여기서 \( r- b = a - b(q+1) \) 이므로  \( r - b \in S \) 이는 \( r \)이 \( S \) 내에서 가장 작은 원소라는 것과 모순이 됩니다. 

 

II. 다음으로 \( b < 0 \) 라고 가정해봅시다. 그러면 \( -b < r \) 이기 때문에 \( 0 < r + b < r \)  이 성립합니다. ( \( b \) 가 음수이기에) 위와 같은 이유로 모순이 됩니다.

 

즉 다시 말해서  \( 0 < r < |b| \) 이 성립합니다. 이것으로 (1) 의 증명이 마무리 됩니다.

 

이제 위의 성질들을 만족하는 또 다른 쌍 \( (q', r') \) 이 있다고 가정해봅시다. (성질 1)에 의해서 

\[ bq + r = bq' + r' \]

이 성립합니다. 이항을 하게 되면 \( b(q-q') = (r'-r) \) 이 됩니다. 하지만 \( 0 < r, r' < b \) 이기 때문에 \( -b < r'-r < b \) 이 성립하게 됩니다. 하지만 \( b \) 의 배수이면서 \( -b \) 보다 크고 \( b \) 보다 작은 숫자는 \( 0 \) 밖에 없기 때문에 \( r' - r = 0 \Rightarrow r' = r \) 이 성립합니다. 다음으로 \( b (q-q') = 0 \)인데 \( b \neq 0 \) 이므로 가분성 성질 4.5 에 의해서 \( q-q' = 0 \Rightarrow q = q' \) 가 됩니다. 이로써 (2) 의 증명이 마무리 됩니다.

 

산술 기본 정리 개요의 유클리드 소정리를 증명하기 위해서는 서로소, 최대공약수 라는 개념이 필요합니다.

 

정의 2 정수 \( a, b \) 이 있으면 \( a \) 의 약수이면서 \( b \)의 약수를 공약수 (Common Divisor) 라고 부른다. 공약수 중에서 가장 큰 공약수를 최대 공약수 (Greatest Common Divisor) 라고 부른다. \( a \) 과 \( b \) 의 최대공약수는 \( \mathrm{gcd}(a,b) \) 혹은 간단히 \( (a,b) \) 라고 쓴다. 만약 \( (a,b) = 1 \) 이면 우리는 \( a \) 와 \( b \) 가 서로소 (Relative Prime) 이라고 부른다.

 

참조 3 \( p \) 가 소수라고 가정해봅시다. 만약 \( p \not| a \) 면 \( a \) 와 \( p \) 는 서로소입니다. \( p \) 는 약수가 2개 밖에 없기 때문에 양의 공약수는 \( 1 \) 아니면 \( p \) 중 하나여야 합니다. 하지만 \( p \not| a \) 라고 가정해버렸기 때문에 유일한 양의 공약수는 \( 1 \) 이기에 \( (a,p) = 1 \) 입니다.

 

최대 공약수는 흥미로운 성질을 가지고 있습니다.

 

정리 4 \( d \) 을 \( a \) 와 \( b \) 의 최대공약수라고 하자. 만약 \( d' \)  이 \( a \) 와 \( b \) 의 공약수이면 \( d' | d \).

 

다시 말해, 모든 공약수는 최대 공약수를 나누어야 합니다. 가장 큰 공약수라고만 했기 때문에 더 작은 공약수들이 최대 공약수를 나누어야할 이유는 없습니다. 

 

정리 4를 증명하기 위해서는 다음 집합을 공부해야 됩니다.

\[ S = \{  ax+by ~|~ a,b \in \mathbb{Z} \} \]

여기서 가장 작은 양의 정수 \( e \in S \) 를 고릅시다. 여기서 양의 정수 중에서 고르기 때문에 가장 작은 수를 고를 수 있습니다. 우리의 목표는 최대공약수 \( d \) 와 \( e \) 가 같다는 것을 보여주는 것입니다.

 

정리 5 \( n \in S \) 는 \( e \) 의 배수이다.

 

증명

\( n \) 과 \( e \) 는  둘 다 \( S \) 안에 있기 때문에 \( n = ax + by \) 그리고 \( e = ax' + by' \) 으로 쓸 수 있습니다. 정리 1에 의해서 \( 0 \leq r < e \) 와

\[ n = eq + r \]

를 만족하는 \( q, r \in \mathbb{Z} \) 가 존재합니다.  그렇다면

\[ r = n - eq = ax + by - e(ax'+by') = a(x-ex') + b(y-ey') \]

이기 때문에 \( r \in S \) 이다. 하지만 \( e \) 보다 작고 양수인 \( S \) 의 원소가 존재하지 않습니다. 그렇기에 \( r = 0 \) 이 됩니다. 즉, \( n \) 은 \( e \) 의 배수가 됩니다.

 

정리 6 정수 \( a, b \) 가 있다고 가정하자. 만약 \( d = \mathrm{gcd}(a,b) \) 라고 하면 

\[ ax + by = d \]

을 만족하는 정수 \( x, y \) 가 존재한다.

 

증명

정의에 의해서 \( d | a \) 와 \( d | b \) 모든 정수 \( x, y \) 에 대해서 \( d | ax + by \) 가 성립합니다. 즉 \( d | e \). 여기서 \( d \)  와 \( e \) 가 둘 다 양수이기 때문에 가분성 성질 4.4 에 의해서 \( d \leq e \) 가 성립합니다. 반대로  \( e | a  \) 이고 \( e | b \) 이기 때문에 \( e \) 는 \( a \) 와 \( b \)의 공약수 입니다. 즉 \( e \leq d \). 즉, \( d = e \) 가 성립함을 알 수 있습니다. 다시 말해,

\[ ax + by = d \]

를 만족하는 정수 \( x, y \) 가 존재합니다.

 

정리 7 (유클리드 소정리) \( p \) 를 소수라 하자. \( p | ab \Rightarrow p| a \text{ 혹은 } p |b \) 가 성립한다.

 

증명

\( p | a \) 이면 정리가 사실이기 때문에 \( p \not| a \) 라고 가정해봅시다. 참조 3에 의해서 \( (p,a) = 1 \) 입니다. 즉 \( px + ay = 1 \) 을 만족하는 정수 \( x,y \) 가 존재합니다. 여기에 \( b \) 를 곱하게 되면 

\[ b = pxb + ayb\]

가 성립합니다. \( p | pxb \) 와 \( p | ayb = y(ab) \)  이기 때문에 \( p | pxb + ayb = b \) 가 성립합니다. (가분성 성질 4.2)