정수론, 그 일곱 번째 이야기 | 최대공약수

 

최대공약수를 정의하기 위해서는, 나누어진다가 무엇인지에 대해서부터 알아야 한다.

나누어진다는 말은 다음과 같이 정의한다.

 

정수 $a,b$에 대해 $a\ne 0$이고, $b=ac$인 정수 $c$가 존재한다면 $b$는 $a$로 나누어진다고 말한다.

 

$b$가 $a$로 나누어지는 경우에는 $a\mid b$로 쓰고, 나누어지지 않으면 $a\nmid b$ 라 쓴다.

 

이는 다양한 성질이 있지만, 이 글에서는 대표적으로 쓰이는 성질인 아래 두 가지를 증명하겠다.

 

정수 $a,b$에 대하여      1. $a\mid b$ 이고 $b\ne 0$ 이면 $|a|\le |b|$      2. $a\mid b$ 이고 $a\mid c$ 이면 임의의 정수 $x,y$ 에 대해 $a\mid (bx+cy)$

 

Part 1 : $a\mid b$ 이고 $b\ne 0$ 이면 $|a|\le |b|$

 

$a\mid b$ 이면 $\mathrm{\exists }c\in \mathbb{Z}s.t.b=ac$ 이고, $b\ne 0$ 이므로 $c\ne 0$

$b=ac$ 의 양 변에 절댓값을 취하면 $|b|=|ac|=|a||c|$이고, $c\ne 0$에서 $|c|\ge 1$

따라서 $|b|=|a||c|\ge |a|$ 이므로, $|b|\ge |a|$ 이다.

 

Part 2 : $a\mid b$ 이고 $a\mid c$ 이면 임의의 정수 $x,y$ 에 대해 $a\mid (bx+cy)$

 

$a\mid b$ 이고 $a\mid c$ 이므로 $\mathrm{\exists }r,s\in \mathbb{Z}s.t.b=ar,c=as$

따라서 어떤 정수 $x,y$ 에 대해 $bx+cy=arx+asy=a(rx+sy)$

그런데 $(rx+sy)\in \mathbb{Z}$ 이므로 $a|(bx+cy)$ 가 성립한다.

 

 

이제 위의 정의를 이용하면, 최대공약수를 정의할 수 있다. 최대공약수는 아래처럼 정의한다.

 

$a,b$ 가 둘 중 하나는 $0$ 이 아닌 정수일 때, 아래 조건을 만족하는 $d\in \mathbb{N}$ 을 $a,b$의 최대공약수라 한다.      1. $d\mid a,d\mid b$      2. 정수 $c$ 가 $c\mid a$ 이고 $c\mid b$ 이면 $c\le d$

 

적어도 하나는 $0$이 아닌 정수 $a,b$ 에 대해, 최대공약수 $d$ 를 $\gcd (a,b)$ 로 표현한다.

만약 $gcd(a,b)=1$ 이라면, $a,b$ 를 서로소 (relatively prime) 이라고 한다.

 

때로는 최대공약수임을 보일 때 아래의 성질을 만족함을 보이는 경우가 있는데, 두 조건은 동치이다.

 

$a,b$ 가 둘 중 하나는 $0$ 이 아닌 정수일 때, $\gcd (a,b)=d$ 와 아래 조건은 필요충분조건이다.      1. $d\mid a,d\mid b$      2. 정수 $c$ 가 $c\mid a$ 이고 $c\mid b$ 이면 $c\mid d$ 이다.

 

Proof : 

조건 1. 은 같으므로, 조건 2. 에 대해서만 동치임을 보이자. $\gcd (a,b)=d$ 라고 하면 $\mathrm{\exists }x,y\in \mathbb{Z}s.t.ax+by=d$ 이고, 따라서 $c\mid a,c\mid b$ 이면 $c\mid d$ 이다.

 

만약 어떤 정수 $d$ 가 위의 두 조건을 만족한다면, 어떤 정수 $c$ 에 대해 $c\le d$ 가 성립해야 $d$ 가 최대공약수가 된다. 이 때, $c\mid d$ 이므로 $c\le |c|\le |d|=d$ 이므로 $c\le d$

따라서 주어진 조건은 최대공약수의 정의와 동치이다.

 

최대공약수는 아래와 같은 성질을 만족하는데, 증명과정이 짧은 편이 아니므로 잘 알아두자.

 

적어도 하나는 $0$이 아닌 정수 $a,b$ 에 대해 $$\gcd (a,b)=ax+by$$     를 만족하는 정수 $x,y$ 가 존재한다.

 

Proof : 

집합 $S$를 다음과 같이 정의하자. $$S=\{au+bv:au+bv>0,u,v\in \mathbb{Z}\}$$ 먼저 $S\ne \varnothing$ 임에 주목하자. $u=a,v=b$일 때 $a^2+b^2>0$ 이 되므로 $S$ 의 원소이기 때문이다.

 

따라서 정렬성의 원리에 의해 $S$ 는 최소원소 $\min S=d$ 를 가진다. 그리고 $S$ 의 정의에 의해 $d=ax+by$ 를 만족하는 정수 $x,y$ 가 존재한다.

 

나눗셈 정리에 의해, $a=qd+r,0\le r<d$ 를 만족하는 정수 $q,r$ 이 유일하게 존재함을 알 수 있다.

이 때, $$r=a-qd=a-q(ax+by)=a(1-qx)+b(-qy)$$ 과 같은 식이 성립하는데 만약 $r>0$ 이라면 $r\in S$ 이고 $r<d$ 이므로 $\min S=d$ 임에 모순.

따라서 $r=0$ 이 성립하고, $a=qd$ 이므로 $d\mid a$ 임을 의미한다.

같은 방법으로, $d|b$ 임도 보일 수 있다. 따라서 $d\mid ad\mid b$ 임을 보였다.

 

이제 어떤 정수 $c$ 가 $c\mid ac\mid b$ 라고 하자. 이는 $c\mid (ax+by)$ 임을 의미하고,

$d=ax+by$ 가 성립하므로 $c\mid d$ 이다.

그런데 $d>0$이므로 $|d|=d$가 성립하여, $c\le |c|\le |d|=d$ 에서 $c\le d$

 

따라서 $d$ 는 $a,b$의 최대공약수가 되고, $d=ax+by$ 를 만족하는 정수 $x,y$가 존재한다.

 

위의 정리로부터 아래와 같은 따름정리를 얻을 수 있다.

 

$a,b$ 가 둘 중 하나는 $0$ 이 아닌 주어진 정수라 하면, 두 집합 $$T=\{ax+by:x,y\in \mathbb{Z}\}$$ $$D=\{dk:d=gcd(a,b),k\in \mathbb{Z}\}$$     에 대해 $D=T$가 성립한다.

 

Proof :

 

모든 정수 $x,y$ 에 대해 $d\mid a$ 와 $d\mid b$ 가 성립하므로 $d\mid (ax+by)$ 이다.

그러므로 $T$ 의 모든 원소는 $d$ 의 배수가 되고, $T\subseteq D$ 이다.

 

또한, 적당한 정수 $x_0,y_0$ 에 대해 $d=a{x}_0+b{y}_0$ 로 표현할 수 있고, 따라서 $d$의 배수 $dk$ 는 $$dk=k(a{x}_0+b{y}_0)=a\left(k{x}_0\right)+b\left(k{y}_0\right)$$ 로 표현된다. 따라서 $dk$ 는 $a,b$ 의 선형 조합이므로 정의에 의해 $T$ 의 원소이다.

따라서 $D\subseteq T$ 이므로 $D=T$ 이다.

 

 

또, 둘 중 하나는 0이 아닌 두 정수 $a,b$가 서로소일 필요충분조건 중 아래와 같은 것이 있다.

 

$a,b$ 가 서로소이다 $\iff$ $ax+by=1$ 을 만족하는 정수 $x,y$가 존재한다.

 

Proof : 

$a,b$ 가 서로소이면 $\gcd (a,b)=1$ 이다. 따라서 $ax+by=1$ 을 만족하는 정수 $x,y$ 가 존재한다.

 

$ax+by=1$ 을 만족하는 정수 $x,y$ 가 존재할 때 $\gcd (a,b)=d$ 라고 하면 $d\mid a$, $d\mid b$ 가 성립하므로 $d\mid (ax+by)$ 에서, $d\mid 1$ 이다. $d$ 는 양의 정수이므로 $d=1$ 이 되어, $a,b$ 는 서로소이다.

 

위의 결과는 꽤 유용하게 사용할 수 있는데, 다음과 같은 명제를 보자.

 

$\gcd (a,b)=d\Rightarrow \gcd (\frac{a}{d},\frac{b}{d})=1$

 

Proof :

$\mathrm{\exists }x,y\in \mathbb{Z}s.t.ax+by=d$ 이므로, 양 변을 $d$ 로 나누면 $\frac{a}{d}x+\frac{b}{d}y=1$

따라서 $\gcd (\frac{a}{d},\frac{b}{d})=1$ 이 성립한다.

 

또한, 여기서 꼭 다루어야 할 중요한 정리가 있는데, 유클리드 보조정리라 불리는 아래의 명제이다.

 

$a\mid bc$ 이고 $\gcd (a,b)=1\Rightarrow a\mid c$

 

Proof : 

$\mathrm{\exists }x,y\in \mathbb{Z}s.t.ax+by=1$ 이고, 양 변에 $c$ 를 곱하면 $$c=(ax+by)c=acx+bcy$$ 가 성립한다. 여기서 $a\mid bc$ 이므로 $a\mid (acx+bcy)$ 이다. 이를 다시 쓰면 $a\mid c$ 이다.