유클리드 호제법 증명 / 최대공약수 알고리즘

1. 유클리드 호제법의 정의

✅ a>b인 두 양의 정수 a,b에 대하여, a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)이라 하면, gcd(a,b)=gcd(b,r) (a,b의 최대공약수=b,r의 최대공약수)이다.

2. 알고리즘 표현

    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0)
            return num2;
        return GCD(num2, num1 % num2);
    }

 

3. 증명

a > b인 두 양의 정수 a, b가 있다. 이 둘의 최대공약수를 G라고 하자.

a = AG, b = BG

 

여기서 A와 B는 서로소이다. G가 두 수의 최대공약수이기 때문이다.( 최대공약수는 모든 공통 약수를 가져가야 하기 때문에 남은 것에 공통 약수는 없다. )

 

a > b이기 때문에, b로 a를 나눌 수 있다.

a = qb + r

 

a=AG, b=BG를 대입 후 r 기준으로 변형

AG = qBG + r
G(A - qB) = r

 

b의 정의에 따르면, r과 b 사이에는 G라는 공통 약수가 생기게 된다.

r = G(A - qB)
b = G(B)

 

유클리드 호제법을 증명하기 위해서는 r, b 사이의 G가 '최대공약수'가 되어야 한다. 그래야 a, b의 최대공약수 G가 b, r의 최대공약수와 같아지기 때문이다.

그렇다면, `A - qB` 와 `B`가 서로소라면 우리가 원하는 유클리드 호제법이 증명된다.

 

이 둘을 서로소가 아니라고 생각해서 전개한 결과에 모순이 생기게 된다면, 그게 바로 서로소라는 사실이 증명되는 것이다.

그러면 이 둘이 서로소가 아니라면, 1보다 큰 최대공약수인 t가 존재한다는 것이고, 그 식은 다음과 같다.

A - qB = mt
B = nt

 

여기서 m과 n은 몫이다.

 

B를 대입하면 다음과 같다.

A - qnt = mt

 

이 식을 조금 변형시키면 다음과 같다.

A = mt + qnt = t(m + qn)
B = t(n)

여기서 모순이 나타난다.

우리가 아까 A와 B는 서로소라고 했는데, 결과는 서로소가 아니라고 나온다.

결과가 모순이니까 가정도 틀렸다는 것이고, 유클리드 호제법 증명이 끝났다.

 

 

참고 링크

https://sseong40.tistory.com/3