유클리드 호제법(Euclidean Algorithm)

가로가 $33$, 세로가 $12$인 직사각형을 한 변의 길이가 $a$ ($a$는 자연수)인 정사각형의 타일로 빈틈없이 채우려면 가로와 세로가 모두 $a$의 배수이므로 $a$는 $33$과 $12$의 공약수여야 한다. 이때, $33$과 $12$의 최대공약수는 $a$의 최대값이므로, 직사각형을 같은 크기의 정사각형으로 나누었을 때 얻을 수 있는 정사각형의 변의 길이의 최대값이다.

그림에서 $33$을 $12$로 나누면

$$33=12\times 2+9$$

이므로 □$ABCD$ 에 내접하는 정사각형의 최대 변의 길이는 $12$보다 작으므로 나머지 부분인 가로 $9$ ($33$ 을 $12$로 나눈 나머지)와 세로 $12$인 직사각형 $A_1{B}_{1}C{D}_1$ 에 내접하는 정사각형의 최대 변의 길이와 같다.

다시, $12$를 $9$로 나누면

$$12=9\times 1+3$$

이므로 정사각형의 최대 변의 길이는 $9$보다 작으며 나머지 부분인 세로가 $3$ ($12$를 $9$로 나눈 나머지), 가로가 $9$인 직사각형 $A_1{B}_{1}C{D}_1$ 에 내접하는 최대 변의 길이와 같다.

그런데

$$9=3\times 3+0$$

이므로 □$A_1{B}_{1}C{D}_1$ 에 내접하는 정사각형의 최대 변의 길이는 $3$이다. 즉, $33$과 $12$의 최대공약수는 $3$이다. 위의 과정을 정리하면 다음과 같다.

$$\begin{array}{rl}(33\text{과 }12\text{의 최대공약수})& =(12\text{와 }33\text{을 12로 나눈 나머지 }9\text{ 와의 최대공약수})\\ & =(9\text{와 }12\text{를 9로 나눈 나머지 }3\text{의 최대공약수})\\ & =3\end{array}$$

정리

$$a=bg+r(0\le r<b),(a\text{와 }b\text{의 최대공약수})=(b\text{와 }r\text{의 최대공약수})$$

증명

$a$ 를 $b$ 로 나누었을 때 몫을 $q$, 나머지를 $r$ 라 하면

$$a=bq+r(0\le r<b)$$

이때, $a,b$ 의 최대공약수를 $G$, $b,r$ 의 최대공약수를 $G^{\prime }$ 이라 하자.

1. $a=a^{\prime }G,b=b^{\prime }G$에서 $r=a-bq=(a^{\prime }-b^{\prime }q)G$이므로 $G$ 는 $r$ 의 약수이다. $G$ 는 $b,r$ 의 공약수 이므로, $G$ 는 $b,r$ 의 최대공약수인 $G^{\prime }$ 의 약수이다.

2. $b=b^{\prime \prime }{G}^{\prime },r=r^{\prime }{G}^{\prime }$이라 하면 $a=bq+r=(b^{\prime \prime }q+r^{\prime })G^{\prime }$이므로 $G^{\prime }$ 는 $a$ 의 약수이다. $G^{\prime }$ 는 $a,b$ 의 공약수 이므로, $G^{\prime }$ 는 $a,b$ 의 최대공약수인 $G$ 의 약수이다.

1, 2에서 $G$ 와 $G^{\prime }$은 서로 약수이므로 $G=G^{\prime }$이다. 즉, $a,b$ 의 최대공약수와 $b,r$의 최대공약수는 서로 같다.

유클리드 호제법(Euclidean Algorithm)

$a,b\in \mathbb{Z},a\ge b>0$ 일 때, 다음과 같이 나머지를 반복적으로 구한다.

$$\begin{array}{rl}a& =b{q}_1+r_1,(0\le r_1<b)\\ b& =r_1{q}_2+r_2,(0\le r_2<r_1)\\ r_1& =r_2{q}_3+r_3,(0\le r_3<r_2)\\ & ⋮\\ r_{n-2}& =r_{n-1}{q}_n+r_n,(0\le r_n<r_{n-1})\\ r_{n-1}& =r_n{q}_{n+1}+0\end{array}$$

예시 1

두 자연수 $2465$, $3132$의 최대공약수를 구하여라.

$$\begin{array}{cccc}3& 2465& 3132& 1\\ & 1901& 2465& \\ 5& 564& 667& 1\\ & 515& 564& \\ 9& 49& 103& 2\\ & 45& 98& \\ 4& 4& 5& 1\\ & 4& 4& \\ & 0& 1& \end{array}$$

따라서 $\gcd (2465,3132)=1$이다.

베주 항등식(Bézout’s identity)

유클리드 호제법을 이용하여 주어진 두 정수 $a,b$의 최대공약수 $d$를 구할 수 있을 뿐만 아니라 $ax+by=d$를 만족시키는 정수 쌍 $x,y$도 얻을 수 있다. 그 방법은 다음과 같다.

$$d=\gcd (a,b)=r_n=r_{n-2}-q_n{r}_{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_n{q}_{n-1})r_{n-2}-q_n{r}_{n-3}$$

여기에

$$r_{n-2}=r_{n-4}-q_{n-2}{r}_{n-3}$$

를 대입하면

$$r_n=(1+q_n{q}_{n-1})(r_{n-4}-q_{n-2}{r}_{n-3})-q_n{r}_{n-3}=(1+q_n{q}_{n-1})r_{n-4}-[q_n+q_{n-2}(1+q_n{q}_{n-1})]r_{n-3}$$

다시 여기에

$$r_{n-3}=r_{n-5}-q_{n-3}{r}_{n-4}$$

를 대입한다. 이와 같은 과정을 되풀이하면 $ax+by=d$를 만족시키는 정수 쌍 $x,y$를 구할 수 있다.

예시 2

다음 식을 만족하는 정수 $x,y$ 중 하나를 구하여라.

$$78=1482x+1326y$$

유클리드 호제법에 의해

$$\begin{array}{cccc}1& 1482& 1326& 8\\ & 1326& 1248& \\ 2& 156& 78& \\ & 156& & \\ & 0& & \end{array}$$

$\gcd (1482,1326)=78$이다. 이제 유클리드 호제법을 역추적하여 $78=1482x+1326y$를 만족하는 정수 $x,y$를 구하면

$$\begin{array}{rl}78& =1326-(156\times 8)\\ & =1326-8\cdot (1482-1326)\\ & =1326-8\cdot 1482+8\cdot 1326\\ & =-8\cdot 1482+9\cdot 1326\end{array}$$

$x=-8$, $y=9$이다.

유클리드 호제법 표를 이용하면

$$\begin{array}{cccc}1& a& b& 8\\ & b& 8a-8b& \\ & a-b& 9b-8a& \end{array}$$

$78=1482\times (-8)+1326\times 9$ 이므로 $x=-8$, $y=9$이다.

서로소의 성질

정수 $a,b$가 $a\ne 0,b\ne 0$일 때, $a$와 $b$가 서로소(relatively prime)이기 위한 필요충분조건은 다음과 같다.

$$\gcd (a,b)=1⟺\exists x,y\in \mathbb{Z}\text{ such that }ax+by=1$$

증명

(⇐ 방향)
정수 $x,y\in \mathbb{Z}$가 존재하여 $ax+by=1$ 이면, 모든 $a,b$의 공약수 $d$는 $ax+by$를 나누어야 하므로 $d\mid 1$ 이다. 따라서 $d=\pm 1$이므로 $\gcd (a,b)=1$

(⇒ 방향)
$\gcd (a,b)=1$이라면, 유클리드 호제법을 통해 $\gcd (a,b)$를 구하는 과정을 역추적하여
항상 $ax+by=1$의 꼴로 표현할 수 있다.

유일한가?

$a,b\in \mathbb{Z}$에 대해

$$ax+by=1$$

을 만족하는 어떤 하나의 정수 해 $(x_0,y_0)$가 존재한다고 하자. 그러면 이 방정식의 모든 해는 다음과 같이 일반해의 형태로 표현된다.

$$x=x_0+bt,y=y_0-at\text{(단, }t\in \mathbb{Z})$$

즉, $t$에 정수 값을 마음대로 넣으면 무한히 많은 $(x,y)$쌍이 나온다.

예시 3

$$\gcd (5,3)=1\Rightarrow 5x+3y=1$$

한 해는 $x=2,y=-3$이다.

하지만 이외에도

• $x=2+3=5,y=-3-5=-8$
• $x=2-3=-1,y=-3+5=2$
• $x=2+3t,y=-3-5t$

처럼 무수히 많은 정수해가 존재한다.

예제

1. $\gcd (120,45)$를 구하시오.¹

2. $\gcd (252,105)$를 구하시오.²

3. $\gcd (19278,7497)$를 구하시오.³

4. 두 자연수 $a=1111$과 $b=11\cdots 111$($1$이 $2025$개)의 최대 공약수를 구하시오.⁴

5. 임의의 자연수 $n$에 대하여 $\frac{21n+5}{14n+3}$이 기약분수임을 증명하시오. ⁵

6. 임의의 자연수 $n$에 대하여 $\frac{5n^2+15n+7}{3n^2+9n+4}$ 가 기약분수임을 증명하시오.⁶

7. $\gcd (19278,7497)=1071=19278x+7497y$ 를 만족하는 정수 $x,y$를 하나만 구하여라. ⁷

Footnotes

1. $120=45\times 2+30$, $45=30\times 1+15$, $30=15\times 2+0$이므로, 최대공약수는 $15$이다. ↩

2. $252=105\times 2+42$, $105=42\times 2+21$, $42=21\times 2+0$이므로, 최대공약수는 $21$이다. ↩

3. $19278=7497\times 2+4284$, $7497=4284\times 1+3213$, $4284=3213\times 1+1071$, $3213=1071\times 3+0$이므로, 최대공약수는 $1071$이다. ↩

4. $a=1111=101\times 11$, $b=11\cdots 111=10101\cdots 01=10101\times 11\cdots 11+1$이므로, 최대공약수는 $1$이다. ↩

5. $2(21n+5)-3(14n+3)=1$이므로, $21n+5$와 $14n+3$은 서로소이다. 따라서 $\frac{21n+5}{14n+3}$은 기약분수이다. ↩

6. 기약분수란 분자와 분모의 최대공약수가 1인 분수를 의미하므로, 최대공약수를 구하여 1인지 확인하자. $(5n^2+15n+7)-(3n^2+9n+4)=2n^2+6n+3$, $(3n^2+9n+4)-(2n^2+6n+3)=n^2+3n+1$, $(2n^2+6n+3)-2(n^2+3n+1)=1$이므로, 최대공약수는 1이다. ↩

7. $1071$ $=4284-3213=4284-(7497-4284)$ $=2\cdot 4284-7497$ $=2\cdot (19278-2\cdot 7497)-7497$ $=2\cdot 19278-5\cdot 7497$ 이므로 $x=2$, $y=-5$이다. ↩