Number Theory - 2.3 최대공약수와 서로소

배수와 약수의 정의

Theorem 2.1

정수 $c$가 존재하여 $b=ac$ 를 만족할 때, $b$는 $0$이 아닌 정수 $a$로 나누어 떨어진다고 하고, $a~\vert~b$ 라고 쓴다.

Theorem 2.2

정수 $a,b,c$ 에 대하여 다음이 성립한다.

$(a)$

$\qquad a ~\vert~ 0,\quad1 ~\vert~ a,\quad a ~\vert~ a$

$\qquad \because 0=a \cdot 0,\quad a=1 \cdot a$

$(b)$

$\qquad a ~\vert~ b \text{ 이고 } c ~\vert~ d\text{ 이면 } ac ~\vert~ bd$ 이다.

$b=aq_1,\,d=cq_2$ 로 두면 $bd=acq_1q_2$ 여서

$ac ~\vert~ acq_1q_2$ 이기 때문이다. $\square$

$(c)$

$\qquad a ~\vert~ b$ 이고 $b ~\vert~ c$ 이면 $a ~\vert~ c$이다.

$(d)$

$\qquad a ~\vert~ b$ 이고 $b \ne 0$ 이면 $\lvert a \rvert \le \lvert b \rvert$이다.

$b=ac$ 이므로 $b\ne0$ 이여서 $c\ne0$ 이다.

양변에 절댓값을 씌우면,

$\lvert b \rvert=\lvert a \rvert \lvert c \rvert$

이 때, $\lvert c \rvert \ge 1$ 이므로 $\lvert b \rvert=\lvert a \rvert \lvert c \rvert \ge \lvert a \rvert$ $\square$

$(e)$

$\qquad a ~\vert~ b$이고, $a ~\vert~ c$ 이면 임의의 정수 $x,\,y$ 에 대해 $a ~\vert~ (bx+cy)$ 이다.

$b=aq_1$ 이고 $c=aq_2$ 라고 하면, $bx+cy=aq_1x+aq_2y=a(q_1x+q_2y)$ 이므로 $a ~\vert~ (bx+cy) \square$

최대공약수의 정의

$a,\,b$ 중 적어도 하나는 $0$이 아닌 정수일 때,

$d ~\vert~ a,\, d ~\vert~ b$이고 임의의 $a,\,b$의 공약수 $c$가 $d \ge c$ 를 만족하면,

$d$는 $a$와 $b$의 최대공약수 greatest common divisor라 한다.

최대공약수의 성질

Theorem 2.3 ⭐️

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

증명

$$ S=\{ au+bv ~\vert~ au+bv > 0,\ \ u,\,v \in \Z \} $$

인 집합 $S$에 대해 $S \ne \varnothing$ 임을 보이자.

일반성을 잃지 않고 $a \ne 0$ 일 때, $\lvert a \rvert = au+b \cdot 0$ 은 $u=1\ or\ u=-1$ 일 때 성립한다.

$a = 0$ 이라면 $a$와 $b$를 바꾸어 주면 되므로

둘 중 하나는 $S$에 존재하므로 $S \ne \varnothing$

정렬성의 원리에 의해 $S$의 가장 작은 원소 $d$가 있고,

$d=ax+by$를 만족하는 정수 $x,y$가 존재한다.

$d=gcd(a,b)$ 를 증명하자.

나눗셈 정리에 의해 $a=qd+r\ (0 \le r < d) ~~(1)$ 를 만족하는 $q,r$이 유일히 존재한다.

$$ \begin{aligned} r&=a-qd\\ &=a-q(ax+by)\\ &=a(1-xq)+b(-qy) ~~~~~~ (2) \end{aligned} $$

이 때, $r$은 $S$의 가장 원소 $d$보다 작다. $(1)$

$r$은 (2)에서 $ax+by$ 꼴이 나왔으므로 집합 $S$에 속하지 않기 위해 $0$이 되어야 한다.

즉, $a=qd$ 이고 $d ~\vert~ a$ 이고 마찬가지로 $d ~\vert~ b$ 를 보인다.

$a$와 $b$의 임의의 공약수 $c$에 대해 $c ~\vert~ ax+by$인데, $d=ax+by$ 이므로 $c ~\vert~ d$ 이고 $\lvert c \rvert \le d$ 이다.

즉, $d$는 $a,b$의 모든 공약수들보다 크거나 같으므로 $d=gcd(a,b)$ $\square$

Corollary 2-3 ⭐️

$a,b$ 가 둘 중 하나는 $0$이 아닌 정수일 때,

$c=ax+by$를 만족하는 정수$x,y$가 존재하면, $d ~\vert~ c$ 이고 이는 필요충분조건이다. $(d=gcd(a,b))$

증명

$$ \begin{aligned} d&=gcd(a,b) \\ &\Rightarrow d ~\vert~ a ~\&~ d ~\vert~ b \\ &\Rightarrow d ~\vert~ (ax+by) \end{aligned} $$

역으로, $d ~\vert~ c$ 이면 $d=ax+by$를 만족하는 $x,y$에서

양변에 정수인 $\dfrac cd$ 를 곱해주면,

$\because d ~\vert~ c$

$c=a \cdot \dfrac {cx}d + b \cdot \dfrac {cy}d$ $\square$

서로소의 정의

둘 중 하나는 $0$이 아는 정수 $x,y$ 에 대해 $gcd(x,y)=1$이면 $a$와 $b$를 서로소 (coprime, relatively prime) 이라고 한다.

Theorem 2.4

$a,b$를 둘 중 하나는 $0$이 아닌 정수라 할 때,

$a,b$가 서로소이면, $1=ax+by$인 정수 $x,y$가 존재하고, 역도 성립한다.

증명

$1=gcd(a,b)=ax+by$ 이므로 Theorem 2.3에 의해 성립한다.

역으로,

$d=gcd(a,b) \Rightarrow d ~\vert~ a ~\&~ d ~\vert~ b$

$a=dq_1,~b=dq_2$

$ax+by=dq_1x+dq_2y=d(q_1x+q_2y) ~\vert~ 1$ 이다.

$d ~\vert~ 1$ 이므로 $\lvert d \rvert \le 1$ 이여야 하고, $d \ge 1$ 이므로 $d=1$ 이다. $\square$

Corollary 2.4 - 1

$gcd(a,b)=d$이면, $gcd\left(\dfrac ad,\, \dfrac bd\right)=1$

증명

$$ \begin{aligned} d=ax+by\\ 1=\Bigl(\dfrac ad\Bigr)x + \Bigl(\dfrac bd\Bigr)y \end{aligned} $$

이므로 $\dfrac ad$와 $\dfrac bd$는 서로소이다.

Corollary 2.4 - 2

$a ~\vert~ c$, $b ~\vert~ c$ 그리고 $gcd(a,b)=1$ 이면 $ab ~\vert~ c$

증명

$c=aq_1=bq_2$

$1=ax+by$를 만족하는 $x,y$가 존재하므로

$$ \begin{aligned} c&=acx+bcy\\ &=a(bq_2)x+b(aq_1)y\\ &=(\cdots)ab \end{aligned} $$

즉, $ab ~\vert~ c~\square$

Theorem 2.5 - 유클리드 보조정리

$a ~\vert~ bc$이고 $gcd(a,b)=1$ 이면 $a ~\vert~ c$ 이다.

증명

$$ \begin{aligned} 1&=ax+by\\ c&=axc+byc\\ & =axc+yaq ~~ \because a ~\vert~ bc\\ & =a(\cdots) \\ \\ &\therefore a ~\vert~ c~~\square \end{aligned} $$