최대공약수와 유클리드 알고리즘

정의 $b=ac\;(a\not=0)$일 때, $b$는 $a$로 나누어 떨어진다고 하고 기호로 $a|b$로 적는다. 나누어 떨어지지 않을 때는 $a\not| \;\; b$로 적는다. 이 때, $a$는 $b$의 약수(divisor), $b$는 $a$의 배수(multiple)라고 한다.

$b=ac$라면 $b=(-a)(-b)$이다. 언제나 음수와 양수가 짝으로 있으므로 약수와 배수를 연구할 때 양의 정수만 생각해도 충분하다. 또한 나누는 수는 $0$이 아닌 수로 생각한다.

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

1) $a|0,\;1|a,\;a|a$

2) $a|1\iff a=\pm1$

3) $a|b \wedge c|d\Rightarrow ac|bd$

4) $a|b \wedge b|c\Rightarrow a|c$

5) $a|b \wedge b|a\iff a=\pm b$

6) $a|b \wedge b\not=0\Rightarrow |a|\big||b|$

7) $a|b \wedge a|c\Rightarrow \forall x,y\in \mathbb{Z}, a|(bx+cy)$

정의 어떤 정수 $d$가 정수 $a,b$의 약수일 때, 공약수(common divisor)로 부르고 공약수 가운데 가장 큰 정수를 최대공약수(greast common divisor)로 부른다. 최대공약수는 $gcd(a,b)$로 적는다.

$d=gcd(a,b)$, $d>0$라면 아래를 만족한다.

1) $d|a \wedge d|b$

2) $c|a \wedge c|b\Rightarrow c\leq d$

정리 동시에 $0$이 아닌 두 정수 $a,b$가 주어지면 아래를 만족하는 정수 $x,y$가 존재한다.

$$gcd(a,b)=ax+by$$

증명 아래와 같은 집합을 생각하자. 

$$S=\{au+bv|au+bv>0,\;\;u,v\in \mathbb{Z}\}$$

$a\not=0$라고 하면 $|a|=au+b\cdot 0 $에서 $a$의 부호에 따라 $u=-1$ 또는 $u=1$을 고르면 되므로 $S\not\phi$이다.

순서 정리에 따라서 $S$의 최소 원소가 존재한다. 최소 원소를 $d=ax+by$라고 하자.

$d=gcd(a,b)$임을 밝히자.

나눗셈 알고리즘에 따라 $a=qd+r$인 몫 $q$와 나머지 $r$이 정해진다. ($0\leq r<d$)

$$r=a-qd=a-q(ax+by)=a(1-qx)+b(-qy)$$

$r\not=0$이라면 $r\in S$인데 $d$가 최소 원소라는데 모순이다. $\therefore r=0$

따라서, $d|a$이다. 마찬가지로 $d|b$이다.------(1)

양수 $c$가 $c|a\wedge c|b$라면 $c|(ax+by)$이므로 $c|d$이다. $c=|c|\leq|d|=d$----(2)

(1)(2)에 의하여 $d=gcd(a,b)$이다.

아래 집합은 $d=gcd(a,b)$의 모든 배수를 원소로 가지는 집합이 됨을 알 수 있다.

$$T=\{ax+by|x,y\in \mathbb{Z}\}$$

정의 $1=gcd(a,b)$이면 $a$와 $b$는 서로소(relatively prime)이라고 한다.

정리 $a$와 $b$는 서로소라면 $1=ax+by$인 정수 $x,y$가 존재한다.

정리 $gcd(a,b)=d$라면 $\displaystyle{gcd(\frac{a}{d},\frac{b}{d})=1}$는 서로소

정리 $a|c\wedge b|c \wedge gcd(a,b)=1 \Rightarrow ab|c$

정리 $a|bc\wedge gcd(a,b)=1 \Rightarrow a|c$

유클리드 알고리즘(The Euclidean Agorithm)

두 정수 $a$와 $b$의 최대공약수를 구하는 알고리즘이 있다.

$$a=q_1 b+r_1\quad 0\leq r_1 <b$$

$$b=q_2 r_1+r_2\quad 0\leq r_2 <r_1$$

$$r_1=q_3 r_2+r_3\quad 0\leq r_3 <r_2$$

$$\vdots$$

$$r_{n-2}=q_{n} r_{n-1}+r_{n}\quad 0\leq r_{n} <r_{n-1}$$

$$r_{n-1}=q_{n+1}r_{n}+0\quad\quad\quad$$

보조정리 $a=qb+r\Rightarrow gcd(a,b)=gcd(b,r)$

증명 $d=gcd(a,b)$이면 $d|a\wedge d|b$이므로 $d|(a-qb)$이다. 즉, $d|r$

$d$는 $b$와 $r$의 공배수이다.

$c$가 $b$와 $r$의 공배수라고 하자.

$c|(qb+r)$이므로 $c|a$이다.

$c$는 $a$와 $b$의 공배수이므로 $c\leq d$이다.

보조정리에 의하여

$$gcd(a,b)=gcd(b,r_1)=gcd(r_1 ,r_2)=\cdots=gcd(r_{n-1},r_{n})=gcd(r_{n},0)=r_{n}$$

이제 거꾸로 정리해 나가면 $gcd(a,b)=ax+by$를 만족하는 정수 $x,y$를 찾을 수 있다.

$$r_{n}=r_{n-2}-q_{n} br_{n-1}= r_{n-2}-q_{n}(r_{n-3}-q_{n-1} br_{n-2})$$

$$=(1+q_{n}q_{n-1})r_{n-2}+(-q_{n})r_{n-3}$$

 

보기 $gcd(108,42)=108x+42y$를 만족하는 정수를 구해보자.

$$108=2\cdot 42+24$$

$$42=1\cdot 24+18$$

$$24=1\cdot 18+6$$

$$18=3\cdot 6$$

$$\therefore gcd(108,42)=6$$

$$6=24-1\cdot 18=24-(42-1\cdot 24)=2\cdot 24-1\cdot42=2(108-2\cdot42)-42=2\cdot 108+(-5)\cdot 42$$

$$\therefore x=2, y=-5$$

정의 어떤 정수 $d$가 정수 $a,b$의 배수일 때, 공배수(common multiple)로 부르고 공배수 가운데 가장 작은 정수를 최소공배수(least common multiple)로 부른다. 최소공배수는 $lcm(a,b)$로 적는다.