유클리드 호제법 증명

유클리드 호제법은 2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나 입니다.

정보올림피아드에서 2개의 최대 공약수를 구하는 문제가 종종 나오는데...

이때 유클리드 호제법을 이용해서 문제를 풀어 나가면 훨씬 빠르고 유용하게 사용할 수 있습니다.

예를 들면 131 과 109 의 최대 공약수를 구하는 문제같은 경우 131이 3의 배수인지 아닌지 판단 하고 109가 3의 배수인지 아닌지 판단 하는 것보다는 다음과 같이 구하면 훨씬 수월하게 풀릴것 같네요.

131 % 109 = 22 이므로

22 와 109 의 최대공약수와 동일 하고...

109 % 22 = 21 

따라서 22와 21의 최대 공약수와 동일 하기 때문에 최대공약수는 1이 나오게 됩니다.

131이 소수인지 아닌지 판단 하는 것보다 이렇게 판단하는 것이 훨씬 덜 고민이 되는 방향이 아닐까요?

이것보다 더 큰 소수가 나올때 더 유용할것 같네요.

그러면 유클리드 호제법의 정의에 대해 알아 보겠습니다.

유클리드 호제법의 정의는 a와 b의 두수가 있다고 하면 

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대 공약수와 같다는 성질을 이용한 것입니다.

이 원리는 기원전 300년 경에 쓰인 유클리드의 원론에 기록되어 있다고 하는데요.

오늘은 유클리드 호제법에 대해 증명을 해 보도록 하겠습니다.

a 와 b 의 두 수가 있고 a를 b로 나눈 나머지 r 이 있다고 하면 어떤수를 q라고 가정하면

a = q * b + r 과 같이 표현을 할 수가 있습니다. 

이때 0 <= r < b 입니다.

여기서 a,b 의 두수의 최대공약수 k 가 있다고 하면

a = mk, b = nk 로 나타낼수 있는데요 이때 m과 n은 서로 소입니다.

그러면 다음과 같이 표현할 수 있겠네요. 어떤 수를 q라고 하면

mk = q * nk + r

r = mk - qnk = (m-qn) * k 로 표현 할 수 있습니다.

즉 r은 a와 b의 최대 공약수인 k를 가슴에 품고 있다는 것입니다

즉 (m-qn)을 l 이라고 가정하면 r = l * k 가 되는 것입니다.

여기서 b=nk의 n 과 m-qn 이 서로소인것을 증명하면 됩니다.(a 와 b의 최대공약수는 b와 r의 최대공약수가 같음을 증명하기 때문에)

만약에 서로소가 아니라고 가정을 하면

n=xG, m-qn = yG 와 같이 공통인 G(G는 1이 아닌수) 가 있다고 하면

m - qn = m - q*xG = yG

m=yG + qxG =(y+qx)*G 와 같이 나타낼수 있습니다.

따라서 m은 G의 배수이고 n도 G의 배수가 됩니다.

m - qn 을 계산하면 m과 n의 공약수 G의 값으로 계산을 하면 G의 배수의 값이 남을수가 없게 됩니다. 

따라서 n과 m-gn 이 서로소가 될수 밖에 없습니다.

따라서 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

이것을 c언어의 재귀함수 방법으로 프로그래밍을 하면 다음과 같습니다.

long long gcd(long long a,long long b)

{

      if(b==0) return a;

      return gcd(b,a%b); //여기서 r = a % b 입니다.

}