Greatest Common Divisor

Divisible

Definition 1. $b \in \mathbb{Z}$ is divisible by $a \neq 0$, denoted $a \,|\, b$, if $\exists c \in \mathbb{Z}$ such that $b = ca$. We write $a \nmid b$ if $b$ is not divisible by $a$.

$b$가 $a$로 divisible, 즉 나누어 떨어진다는 것은 $a$의 적당한 정수배가 $b$와 같다는 뜻이다. 이때 어떠한 정수라도 가능하며, 따라서 0은 모든 정수로 나누어 떨어진다. 

Theorem 1

Theorem 1. For $a, b, c \in \mathbb{Z}$, the following hold:
(a) $a \,|\, 0, 1 \,|\, a, a \,|\, a$.
(b) $a \,|\, 1 \Longleftrightarrow a = \pm 1$.
(c) $a \,|\, b \wedge c \,|\, d \Longrightarrow ac \,|\, bd$.
(d) $a \,|\, b \wedge b \,|\, c \Longrightarrow a \,|\, c$.
(e) $a \,|\, b \wedge b \,|\, a \Longleftrightarrow |a| = |b|$.
(f) $a \,|\, b \wedge b \neq 0 \Longrightarrow |a| \leq |b|$.
(g) $a \,|\, b \wedge a \,|\, c \Longrightarrow a \,|\, (bx + cy), \forall x, y \in \mathbb{Z}$.

Greatest Common Divisor

Definition 2. Let $a, b \in \mathbb{Z}$, not both zero. The greatest common divisor of $a$ and $b$, denoted by gcd($a, b$), is $d \in \mathbb{N}$ satisfying the following:
(a) $d \,|\, a \wedge d \,|\, b$.
(b) $c \,|\, a \wedge c \,|\, b \Longrightarrow c \leq d$.

gcd, 즉 최대공약수는 말 그대로 공약수 이면서((a)), 공약수 중에 최대인 수((b))를 말한다. 이때 조건 (b)는 다음의 정리를 통해 조금 변형시킬 수 있다.

Theorem 2

Theorem 2. Let $a, b \in \mathbb{Z}$, not both zero. Then gcd($a, b$) = $d$ $\Longleftrightarrow$ 
(a) $d \,|\, a \wedge d \,|\, b$.
(b) $c \,|\, a \wedge c \,|\, b \Longrightarrow c \,|\, d$.

Proof. ($\Longleftarrow$) By Theorem 1 (f), it is clear.
($\Longrightarrow$) By Theorem 2, $d = ax + by$ for some $x, y \in \mathbb{Z}$. Then $c \,|\, ax + by = d$. $\blacksquare$

Theorem 3

Theorem 3. Let $a, b \in \mathbb{Z}$, not both zero. Then $\exists x, y \in \mathbb{Z}$ such that gcd($a, b$) = $ax + by$.

Proof. Let $S := \{ax + by > 0 \,|\, x, y \in \mathbb{Z}\}$. If $a \neq 0$, then $a \cdot \frac{|a|}{a} + b \cdot 0 \in S$. Thus $S \neq \emptyset$. Then by Well-Ordering Principle, there is the least element $d = ax + by \in S$ for some $x, y \in \mathbb{Z}$. 
By Division Algorithm, $!\exists q, r \in \mathbb{Z}$ such that $a = qd + r (0 \leq r < d)$. Then $0 \leq r = a(1-qx) + (-bq)y < d$. If $r > 0$, then $r \in S \bigotimes$. Thus $r = 0 \Longrightarrow a = qd \Longrightarrow d \,|\, a$. By similar way, we have $d \,|\, b$. 
If $c \,|\, a \wedge c \,|\, b$, then $c \,|\, ax + by = d \Longrightarrow c \leq d$. Thus gcd($a, b$) = $d$. $\blacksquare$

    이 정리는 다른 정리들을 증명할 때 상당히 강력한 관계식이 되며, 최대공약수의 대략적인 형태를 예측할 수 있게 해준다. 정확히 최대공약수를 결정하려면 일반적으로는 Euclidean Algorithm을 적용해야 하며, 이를 통해 선형 결합의 계수를 알 수 있다.

    예컨대 $$\begin{align*} a =& \,\,q_1b + r_1 (0 < r_1 < b) \\ b =& \,\,q_2r_1 + r_2 (0 < r_2 < r_1) \\ r_1 =& \,\,q_3r_2 + r_3 (0 < r_3 < r_2) \\ \vdots \\ r_{n-2} =& \,\,q_nr_{n-1} + r_n (0 < r_n < r_{n-1}) \\ r_{n-1} =& \,\,q_{n+1}r_n + 0 \end{align*}$$을 얻었다고 하자. 이때 $$r_n = r_{n-2} - q_nr_{n-1}$$이 성립하고, $$r_{n-1} = r_{n-3} - q_{n-1}r_{n-2}$$이므로 $$r_{n} = r_{n-2} - q_n(r_{n-3} - q_{n-1}r_{n-2}) \\ = (1 + q_nq_{n-1})r_{n-2} + (-q_n)r_{n-3}$$이 성립한다. 즉 구하고자 하는 최대공약수 $r_n$은 위에서 얻은 식들을 역으로 대입하여 올라감으로써 선형 결합으로 표현될 때 그 계수를 구해낼 수 있다.

Theorem 4

Theorem 4. Let $a, b \in \mathbb{Z}$, not both zero. $\forall 0 \neq k \in \mathbb{Z}$, gcd($ka, kb$) = |k| gcd($a, b$).

Proof. Let $k > 0$, and let gcd($a, b$) = $d$. Since $d \,|\, a, d \,|\, b$, $kd \,|\, ka, kd \,|\, kb$. By Theorem 2, $d = ax + by$ for some $x, y \in \mathbb{Z}$. Then $kd = kax + kby$. Suppose that $c \,|\, ka, c \,|\, kb$. Then $c \,|\, kax + kby = kd \Longrightarrow c \leq kd$. Thus gcd($ka, kb$) = $kd$ = $k$ gcd($a, b$).
Let $k < 0$. Then gcd($ka, kb$) = gcd($|ka|, |kb|$) = gcd($|k|a, |k|b$) = $|k|$ gcd($a, b$). $\blacksquare$