사고력 수학 - 유클리드 호제법

최대공약수를 구하는 방법 중에 유클리드가 다음의 방법을 발견했는데요.

이러한 유클리드 호제법은 프로그래밍 구현시 가장 자주 사용되는 수학적 원리가 되고 있습니다.

 

유클리드는 a와 b의 두수의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대 공약수라는 것을 발견했는데요.

 

이것을 증명하는 것은 간단합니다. 공통된 최대공약수를 g라고 하면

a = g * x

b = g * y

라고 하면 g가 최대 공약수이기 때문에 x와 y는 공약수가 1 밖에 없는 서로소가 됩니다. ----(1)

 

따라서 a = b*q + r 이라고 하면 (여기서 a가 b보다 크다고 가정을 했습니다.)

b = g*y 이므로 a=q*g*y + r 이 되고 a= g*x 이므로

g*x=q*g*y + r 이 됩니다.

따라서 다음과 같이 식을 만들 수 있습니다.

r = g*x - q*g*y = g(x-q*y)

이때 b = g * y 이므로 r과 b는 g 라는 최대 공약수를 갖게 됩니다.

 

따라서 x-q*y 와 g*y 가 서로소 인것만을 증명하면 됨으로 만약 서로소가 아닌 1이 아닌 공약수를 갖는다는 가정이 거짓이라는 것을 증명하면 됩니다.(t라는 공약수가 있다고 가정하면)

x-q*y = t * m

y = t * n

이라고 가정하면 

x-q*t*n=t*m 

으로 나타낼 수 있고

x = t(m+qn) 으로 나타낼 수 있습니다.

 

여기서 (1)부분에서 x와 y는 서로소인데 만약 위의 공식이 성립한다면 x와 y는 t라는 최대공약수를 갖게 됩니다.

x = t(m+qn) 이고 y = t * n 이기 때문에

 

따라서 (1)의 서로소에 위배 되기 때문에 x-q*y 와 g*y 는 서로소가 됩니다.

 

증명을 하기 위해 많이 복잡했다면 그냥 수식을 이용해서 이해를 하시면 빠를것 같습니다.

100과 70의 최대 공약수는 70과 30 (100mod70) 의 최대공약수와 동일합니다.

70과 30의 최대 공약수는 30과 10(70mod30) 의 최대 공약수와 동일한 10이 됩니다.

 

이러한 유클리드 호제법은 큰 수의 최대공약수를 구하는데 편리하게 이용됩니다.

 

그렇다면 다음 두 수의 최대 공약수를 유클리드 호제법을 이용해서 구해 보세요.

 

1234와 4444

 

정답)

1234 와 4444 의 최대공약수는 4444 와 1234(1234 mod 4444) 의 최대 공약수와 같습니다.

4444 와 1234 의 최대공약수는 1234 와 742(4444 mod 1234)의 최대 공약수와 같습니다.

1234 와 742의 최대공약수는 742와 492(1234 mod 742) 의 최대 공약수와 같습니다.

742와 492의 최대공약수는 492와 250‬(742 mod 492)의 최대 공약수와 같습니다.

492와 250의 최대공약수는 250와 242(492 mod 250)의 최대 공약수와 같습니다.

250와 242의 최대공약수는 242와 8(250 mod 242)의 최대 공약수와 같습니다.

242와 8의 최대공약수는 8와 2(242 mod 8)의 최대 공약수와 같습니다.

따라서 최대 공약수는 2입니다.