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

 

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

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

 

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

 

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

 

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

 

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

 

Part 1 : $a \mid b$ 이고 $b \neq 0$ 이면 $|a| \leq |b|$

 

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

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

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

 

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

 

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

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

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

 

 

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

 

$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 \leq d$

 

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

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

 

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

 

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

 

Proof : 

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

 

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

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

 

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

 

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

 

Proof : 

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

 

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

 

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

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

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

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

 

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

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

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

 

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

 

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

 

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

 

Proof :

 

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

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

 

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

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

 

 

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

 

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

 

Proof : 

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

 

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

 

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

 

$\mathrm{gcd} \left ( a , b \right ) = d \;\Rightarrow\; \mathrm{gcd} \left ( \frac{a}{d}, \frac{b}{d} \right ) = 1$

 

Proof :

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

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

 

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

 

$a \mid bc$ 이고 $\mathrm{gcd} \left ( a, b \right ) = 1\;\Rightarrow\; a\mid c$

 

Proof : 

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