최대공약수(Greatest common divisor)

약수와 배수, 나눗셈, 나누어 떨어짐에 대해 학습하였다면 최대공약수를 다루지 않을 수가 없습니다. 정수론에서 최대공약수 개념은 무진장 중요하고 빈번히 등장합니다.

 

 

---

1. 최대공약수

 

1) 공약수

 

정의($N.T$) 1.4) 공약수
$d\in\mathbb{Z}$ 가 두 정수 $m,n$ 의 '공약수(common divisor)'라는 것은 $d\mid m$ 이고 $d\mid n$ 인 것이다.

 

공약수의 개념은 별로 새롭거나 어려울 것이 없습니다.

 

 

2) 최대공약수

 

정의($N.T$) 1.5) 최대공약수
자연수 $g$ 가 0이 아닌 두 정수 $a,b$ 의 '최대공약수(greatest common divisor)'라는 것은 다음 세 조건과 필요충분조건이다.
① $g\geq 1$
② $g\mid a$ 이고 $g\mid b$ 이다. 즉 $g$는 $a$와 $b$의 공약수이다.
③ $c\mid a$ 와 $c\mid b$ 를 동시에 만족하는 임의의 정수 $c$ 에 대하여 $c\leq g$ 를 만족한다. 즉, $c\mid g$ 인 것으로 $g$ 는 $a$ 와 $b$ 의 공약수 중에서 가장 큰 값에 해당한다.
이때 최대공약수 $g$ 는 $g=\gcd(a,b)$ 라 표기한다.

정의($N.T$) 1.6) 두 개 이상의 정수에 대한 최대공약수
둘 이상의 정수에 대한 최대공약수는 다음과 같이 정의한다.
$g\in\mathbb{N}$ 가 0이 아닌 정수로 구성된 집합 $S=\left\{ a_1,a_2,\cdots , a_n \right\}$ 의 최대공약수인 것은 $g$ 가 $S$의 모든 정수를 나누는 가장 큰 정수인 것과 필요충분조건이다. 이때 $g$ 는 $\gcd(a_1,a_2,\cdots ,a_n)=g$ 와 같이 나타낸다.

최대공약수의 정의에 의하여 $g\geq 1$ 이다.
만일 두 약수나 인수의 최대공약수가 1인 경우, 두 정수는 '서로소(relatively prime)'이라고 한다.

 

사실 동그라미 1,2번은 최대공약수라는 용어 자체의 뜻을 '최대'라는 점과 '공약수'인 부분으로 나누어 자세히 설명한 것에 불과합니다. 중학교 1학년때 우리가 배웠던 최대공약수의 뜻과 다를 것이 전혀 없습니다. 

 

또한 '서로소'의 정의는, 집합론에서는 교집합이 공집합이라 의미를 가져 'mutally disjoint' 를 말하는 것이지만, 정수론에서는 공약수가 1이외에 존재하지 않아 최대공약수가 1인 경우를 뜻하며, 'relatively prime' 에 해당합니다. 둘을 구분할 수 있는 것이 좋습니다.

---

예제 1) $\gcd(-9,15)=3$ 이고, $\gcd(6,4)=2$ 이다. $_\blacksquare$

 

 

2) 성질

 

정리($N.T$) 1.3
$\gcd(a,b)=g$ 일 때, $\displaystyle\gcd\left( \frac{a}{g},\frac{b}{g} \right)=1$ 이다.

증명) 귀류법(Contradiction)을 사용하자.

$\displaystyle\gcd\left( \frac{a}{g},\frac{b}{g} \right)=d$ 이고 $d>1$ 이라 가정하자. 최대공약수의 정의에 의하여
$$d\mid \frac{a}{g}\;\;\Rightarrow \;\; dm=\frac{a}{g}\;\;\Rightarrow \;\;(dg)m=a\;\; \Rightarrow \;\; dg\mid a$$
$$d\mid \frac{b}{g}\;\;\Rightarrow \;\; dn=\frac{b}{g}\;\;\Rightarrow \;\;(dg)n=a\;\; \Rightarrow \;\; dg\mid b$$
그러므로 $dg$ 는 $a$와 $b$ 의 공약수이다. 그러면 최대공약수의 정의 조건 중 ②에 의하면 $dg\leq g$ 이여야 한다. 그러므로 $d\leq 1$ 에서 가정에 모순이다. 따라서 $d\leq 1 $ 인데 $d$ 는 최대공약수이므로 $d=1$ 이어야 한다. 이것은 $\displaystyle \frac{a}{g},\displaystyle \frac{b}{g}$ 가 서로소(relatively prime)라는 뜻이다.

 

 

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein