Relatively Prime

Relatively Prime

Definition 1. (Relatively Prime) Let $a, b \in \mathbb{Z}$, not both zero. Then $a$ and $b$ are relatively prime if gcd($a, b$) = 1.

두 정수의 최대공약수가 1일 경우 두 수를 relatively prime, 즉 서로소라고 부른다. 최대공약수를 두 수가 나눗셈이라는 연산에서 가지는 공통되는 성질의 최대치라고 생각해보자. 이러한 관점에서 서로소는 두 수가 더 이상 나눗셈에서 봤을 때 공통되는 성질을 가지지 않는다는 것으로 이해할 수 있다.

Theorem 1

Theorem 1. Let $a, b \in \mathbb{Z}$, not both zero. Then $a$ and $b$ are relatively prime $\Longrightarrow$ $\exists x, y \in \mathbb{Z}$ such that $1 = ax + by$.

Proof. ($\Longrightarrow$) By Theorem 3, gcd($a, b$) = 1 = $ax + by$ for some $x, y \in \mathbb{Z}$.
($\Longleftarrow$) If $c \,|\, a \wedge c \,|\, b$, then $c \,|\, ax + by = 1 \Longrightarrow c \leq 1$. Thus gcd($a, b$) = 1. $\blacksquare$

Corollary 1

Corollary 1. Let $a, b \in \mathbb{Z}$, not both zero. If gcd($a, b$) = $d$, then gcd($\frac{a}{d}, \frac{b}{d}$) = 1.

Proof. By Theorem 3, $d = ax + by$ for some $x, y \in \mathbb{Z}$. Then $1 = \frac{a}{d}x + \frac{b}{d}y$. Since $d \,|\, a$ and $d \,|\, b$, $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime. $\blacksquare$

위에서 최대공약수는 두 수가 나눗셈이라는 연산에서 가지는 공통되는 성질의 최대치라고 말했었다. 이때 두 수에서 최대공약수를 모두 덜어낸다면, 더 이상 두 수는 나눗셈에서 공통되는 성질을 가지지 않고 이는 두 수가 서로소임을 뜻한다.

Corollary 2

Corollary 2. Let $a, b \in \mathbb{Z}$, not both zero. If $a \,|\, c$ and $b \,|\, c$ for $c \in \mathbb{Z}$, with gcd($a, b$) = 1, then $ab \,|\, c$.

Proof. Let $c = ma$ and $c = nb$ for some $m, n \in \mathbb{Z}$. By Theorem 3, $1 = ax + by$ for some $x, y \in \mathbb{Z}$. Then $c = c \cdot 1 = c(ax + by) = acx + bcy = a(nb)x + b(ma)y = ab(nx + my) \Longrightarrow ab \,|\, c$. $\blacksquare$

$a, b$가 $c$의 약수이고 서로소라는 뜻은 $c$를 만들어내는데 두 수의 기여가 배타적이라는 것이다. 즉 $c$의 약수라는 관점에서 두 수의 기여에는 공통되는 부분이 없다는 뜻이므로 두 수를 곱한 것 또한 약수로 들어가게 된다.