Number Theory with Code - 2. G.C.D and Euclid Algorithm

예고한 것처럼 '최대 공약수'를 다룬다. 두 정수의 '최대 공약수'가 두 수의 '일차결합'으로 표현된다는 점은 반드시 명심하자.

또한 이번 글에서 접혀있지 않은 증명은 모두 숙지해야 이후의 삶이 편해진다.

Definition

G.C.D(the Greatest Common Divisor)

Let $a$ and $b$ be integers. $d$ is the greatest common divisor if and only if

1. $d>0$
2. $d|a$ and $d|b$
3. $e|a$ and $e|b$ $\Rightarrow e<d$

말 그대로, 최대공약수 $d$는 다른 모든 공약수($e$)보다 큰 공약수이다.

정의는 이해가 되는데, 최대공약수를 구하는 방법이 궁금하다. 지난 시간에 공부한 $a,b$ 의 일차결합 전체의 집합 $$L(a,b)=\{ax+by|x,y\in \mathbb{Z}\}$$ 이 나설 차례다.

$L(a,b)$의 임의의 원소가 $a,b$의 공약수의 배수임은 이미 언급했었다.

Theorem

G.C.D(the Greatest Common Divisor)

$L(a,b)$에서 양수들만 모은 집합 $\{ax+by|x,y\in \mathbb{Z},ax+by>0\}$ 의 최소원은 $a,b$ 의 최대공약수이다.

[단독] 일차 결합은 공약수의 배수라 했으니 '최대공약수'는 모든 공약수의 배수가 된다!

'최소'라는 단어에 반응해서 '정렬성'을 떠올렸다면 훌륭하다. 온통 문자로 뒤덮혀서 뭔지 모를 집합에서 어떤 성질이 성립한다는 명제는 존재를 보장해주는 공리나 정리가 사용될 확률이 높다.

Proof

$X=\{ax+by|x,y\in \mathbb{Z},ax+by>0\}$ 의 최소원을 $d=a{x}_0+b{y}_0$라 하자. (존재는 '정렬성'이 보장해 준다!)

$d$가 $a,b$의 약수임을 보이면 증명이 끝난다. Division Algorithm 에 의해 다음을 만족하는 몫 $q$ 와 나머지 $r$ 이 존재한다. $$a=dq+r,0\le r<d$$

(1) $d$ 는 $a,b$의 약수

$r>0$ 이면 모순이 발생함을 보여서 $d$ 가 $a$의 약수임을 보인다. $$0<r=a-dq=a-(a{x}_0+b{y}_0)q=a(1-x_{0}q)+b(-y_{0}q)\in X$$ $a,b$의 일차결합이면서 양수인 것을 모두 모아 둔 집합이 $X$이기 때문에 $r\in X$ 가 됨을 보았다.

그런데 $r$ 은 $d$ 로 나눈 나머지이므로 $r<d$이기도 하다. 이는 $d$가 $X$ 의 최소원이라는 사실에 모순된다. 따라서, $r=0$ 이어야 한다.

$d$가 $b$ 의 약수라는 것도 같은 방법으로 증명할 수 있다.

(2) $d$ 는 $a,b$의 다른 공약수의 배수

$d$ 가 $a,b$의 공약수란 것은 알겠는데 '최대'라는 사실은 어떻게 알 수 있는가?

증명을 시작하기 전에 $a,b$의 일차결합은 모든 공약수의 배수가 됨을 말했었다.

$e$ 가 $a,b$의 공약수 $\iff$ $\mathrm{\exists }{k}_1,k_2\in \mathbb{Z},e{k}_1=a,e{k}_2=b$ 이므로 $a,b$의 임의의 일차결합은 $e$의 배수가 된다. $$ax+by=e{k}_{1}x+e{k}_{2}y=e(k_{1}x+k_{2}y)$$ 최소원이라 해도 $d$ 역시 $a,b$의 일차결합이니 $e|d$이다.

그런데, 0 을 제외하면 배수는 약수보다 절댓값이 크다!

세 개 이상의 정수에 대해서도 같은 방식으로 최대공약수가 일차결합으로 표현된다.

Theorem

집합 $\{ax+by+cz|x,y,z\in \mathbb{Z},ax+by+cz>0\}$ 의 최소원은 $a,b,c$ 의 최대공약수이다.

증명은 앞의 증명과 완전히 같으므로 생략한다. 다시 한 번 말하지만 4개 이상의 정수에 대해서도 같은 방식이 적용된다.

이 명제의 증명은 어렵지 않으나 상황 파악을 위해서 구체적인 예를 몇 개 다루어 보는 것이 좋겠다. 중고교 과정에서는 문자가 아닌 구체적인 두 수에 대해 '소인수 분해' 등을 통해서 최대공약수를 구했을 것이다. 그래서 일차결합으로 최대공약수가 표현된다는 사실이 잘 와닿지 않을 수 있기 때문이다.

20, 36 의 최대공약수는 4 이다. 일차결합으로 표현해 보자. $$4=20(2)+36(-1)$$ 이런 식으로 최대공약수를 알고 있는 적당한 두 수를 선택하여 일차결합으로 표현가능함을 확인하길 바란다.

caution

역은 성립하지 않는다!

만약 정수 $a,b$에 대해서 $ax+by=2$ 를 얻었다면, $a,b$의 최대공약수가 2라고 할 수 있는가? No!

일차결합은 공약수(최대공약수 포함)의 배수임에 틀림없으니 2의 약수 중 하나가 최대공약수이겠지만 $$3(2)+2(-2)=2$$ 처럼, 그 자체로는 최소의 것인지 모르니 최대공약수라 장담할 수 없다.

위의 경고에 해당되지 않는 특수한 경우인 $ax+by=1$가 매우 중요하다. (일차결합을 보고 최대공약수가 1임을 알 수 있다.) 이 사실은 연습 문제에서 자주 사용될 것이다.

최대공약수가 1인 두 수를 '서로 소'라고 한다. $ax+by=1$에서 $a,b$는 물론 조연인 $x,y$ 역시 서로 소인 것은 덤이다

.

Property

1. $gcd(a,b)=1$ 이고 $a|bc$ 이면, $a|c$ 이다.
   일차결합 문법으로 써보자. $$1=ax+by\Rightarrow c=acx+bcy$$ 여기서 $a|ac,a|bc$ 이므로 $a|c$ 이다.
2. $gcd(a,b)=1$ 이고 $a|c,b|c$ 이면, $ab|c$ 이다.

최대공약수가 두 수의 일차결합으로 표현됨을 알았지만, 집합 $$X=\{ax+by|x,y\in \mathbb{Z},ax+by>0\}$$ 의 최소원은 어떻게 구하라는 것인지 궁금할 것이다. 여기서 유클리드 알고리듬(Euclid Algorithm) 이 등장한다.

$d$ 가 $a,b$ 의 최대공약수일 때, $d=gcd(a,b)$ 로 표기한다.

Lemma

보조 정리

두 정수 $a,b$ 에 대해서 $q,r$ 에 대해 $b=aq+r$ 일 때(물론 $q,r\in \mathbb{Z}$), $$gcd(a,b)=gcd(r,a)=gcd(b-aq,a)$$ 가 성립한다.

보조 정리의 식에서 $q,r$을 몫과 나머지라고 한 적 없다. 주로 몫과 나머지에 적용되지만 아니어도 성립한다.

Proof

$d=gcd(a,b)$, $d^{\prime }=gcd(r,a)$ 라 하자.

$d|d^{\prime }$ 이고 $d^{\prime }|d$ 를 보이면 $d=d^{\prime }$ 을 얻을 수 있다. 일차결합은 공약수의 배수이므로 $$d|r=b-aq=a(-q)+b(1)$$ 가 성립한다. $d|a$ 임은 주어진 것이므로 $d$는 $r,a$의 공약수이다.

공약수는 최대공약수의 약수이므로 $d|d^{\prime }$를 얻는다. 같은 방식으로 $d^{\prime }|d$ 역시 보일 수 있다.

최대공약수가 일차결합으로 표현된다는 사실과 보조 정리를 이용한 문제들을 몇 개 풀어보자.

1. $gcd(a,b)=1$이고 $gcd(a,c)=1$일 때, $gcd(a,bc)=1$임을 보여라.
   $ax+by=1$이고 $au+cv=1$을 만족하는 $x,y,u,v$가 존재한다. 두 식을 곱하면 $$a^{2}xu+abyu+acxv+bcyv=1\Rightarrow a(axy+byu+cxv)+bc(yv)=1$$ 앞서 말한 상황이다. $a,bc$의 일차결합으로 1을 만들었으니 $gcd(a,bc)=1$이다.
2. 양의 정수 $a,n$에 대하여 $gcd(a,a+n)|n$ 임을 보여라.
   일차결합으로 표현하면 자명해진다. $$a+n=a\cdot 1+n$$ 보조정리로부터 $gcd(a,a+n)=gcd(n,a)$가 됨을 안다. $gcd(n,a)$ 가 $n$의 약수인 것은 당연!
3. $gcd(a,b)=1$일 때, $gcd(a+b,a)=1$임을 보여라.
4. $gcd(a,b)=1$일 때, $gcd(a+b,ab)=1$임을 보여라.

보조 정리의 힘으로 최대공약수를 구하는 알고리즘을 확보할 수 있다. 편의상 $a$는 양수로 가정하자.

Theorem

Euclid Algorithm

몫과 나머지를 반복적으로 구하는 다음 과정를 수행한다.

$$\begin{array}{cc}b=a{q}_1+r_1& 0<r_1<a\\ a=r_1{q}_2+r_2& 0<r_2<r_1\\ \cdot & \cdot \\ \cdot & \cdot \\ \cdot & \cdot \\ r_{n-2}=r_{n-1}{q}_n+r_n& 0<r_n<r_{n-1}\\ r_{n-1}=r_n{q}_{n+1}+0& \end{array}$$

나머지는 점차 감소하므로 언젠가는 0이 되는데, 보조 정리로부터 $r_n=gcd(a,b)$ 이다.

반복적으로 나머지를 구할 뿐인데 왜 이리 복잡해 보이는지 모르겠다. (첨자만 붙으면 정신이 혼미하다.) 그나저나 $a,b$가 주어졌을 때, 몇 번만에 Euclid Algorithm이 끝날까?

Lemma

위의 과정에서 $r<\frac{1}{2}\cdot b$이 성립한다.

$a<\frac{1}{2}\cdot b$ 인 경우는 $r<a$이므로 성립한다. $a\ge \frac{1}{2}\cdot b$ 인 경우는 $r=b-a<\frac{1}{2}\cdot b$가 되어 성립한다.

이 결과는 반복적으로 적용되므로 $r_{n+2}<\frac{r_n}{2}$이라 할 수 있다. 전체 과정은 대략 $2\cdot {\log }_{2}a$ 에 가까운 자연수 회수 안에서 끝난다.

'가까운 자연수'라는 표현이 등장한 차에 새로운 함수를 하나 정의하자.

Definition

Floor function (바닥함수): $[\cdot ]$ 혹은 $\lfloor \cdot \rfloor$

정수 $n$에 대하여 $n\le x<n+1$ 일 때, $[x]=n(\lfloor x\rfloor =n)$

교육과정에서 '최대정수함수'라는 용어를 본 것 같은데, '바닥함수'로 쓰겠다. 어감이 좋다.

이쯤에서 연습을 조금 하는 것이 좋겠다.

1. $gcd(a,b)=1$ 이고 $gcd(c,d)=1$ 일 때, $\frac{a}{b}+\frac{c}{d}$ 이 정수이면 $b=d$임을 증명하라.
   먼저 $b|d$ 임을 보이자. $\frac{a}{b}+\frac{c}{d}=k$ 로 두고 양변에 $k$를 곱해서 $$ad+bc=k\cdot bd\Rightarrow ad=b(c-kd)\Rightarrow b|ad$$ 를 얻는다. $gcd(a,b)=1$ 이므로 $b|d$ 가 성립한다. $d|b$ 역시 같은 방식...
2. $gcd(a,b)=1$ 이고 $gcd(c,d)=1$ 일 때, $b\ne d$ 이면 $\frac{a}{b}+\frac{c}{d}$ 가 정수가 아님을 보여라. (위 문제와 같은 문제이다.)
3. 임의의 정수 $n$에 대하여 $\frac{21n+4}{14n+3}$ 이 기약분수임을 보여라. ( $21n+4$ 와 $14n+3$ 이 서로소임을 보여라. 제1회 IMO 1번 문제)
   일차결합으로 최대공약수를 찾으면 된다. $$1=(21n+4)(-2)+(14n+3)(3)$$
4. 두 자연수 $a=11,111,111$과 $b=11,111,\cdots ,111$ (1988 자릿수) 의 최대공약수를 구하라.
   자릿수끼리의 몫과 나머지 를 구하면 $1988=8\cdot 248+4$ 이므로 $$b=aq+1111,q={10}^4\{1+{10}^8+({10}^8{)}^2+\cdots +({10}^8{)}^{247}\}$$ 이 성립한다. 이로부터 $gcd(a,b)=gcd(1111,a)=1111$ 를 얻는다.

---

With Code!

다음 코드에서 내부 함수(inner function)이 핵심이고 외부 코드는 $a,b$ 가 제대로 된 입력인지 걸러낸다.

python3 JavaScript

def GCD(a,b):
    if a!=int(a) or b!=int(b):
        print('장난치지 마라!')
        return
    elif a==0 and b==0:
        print('둘 모두 0이면 최대공약수는 정의되지 않는다!')
        return
        
    if a>b :
        a,b=b,a
    
    def gcd(a,b):
        if a==0:
            return b
        return gcd(b%a, a)
    
    print(f'{a}, {b}의 최대공약수는 {gcd(a,b)} 입니다.')

function GCD (a, b) {
    if(a!==parseInt(a) || b!==parseInt(b))
        return '뭐 하냐?';
    else if (a===0 && b===0) 
        return '0은 모든 수의 배수라서 둘 다 0이면 최대공약수 정의 안된다!';
    
    if(a>b) {
        [a,b]=[b,a];
    }
 
    console.log('a : '+a+ ' b: '+b);
 
    function gcd(a, b){
        if(a==0) return b;
        return gcd(b%a,a);
    }
 
    return `두 정수 a와{b} 의 최대공약수는 ${gcd(a,b)} 입니다.`;
}