유클리드 호제법을 쉽게 이해하는 법, 최대공약수를 소인수분해로 구하는 것은 금도끼로 장작을 패는 것과 같다 (feat. 유클리드 알고리즘)
이 글에서는 두 자연수의 최대공약수를 구하는 방법인
유클리드 호제법의 오해와 본질에 대한
설명을 담았습니다.
1. 최대공약수를 구하는 방법
어떤 자연수를 소인수분해 하는것은
정수론의 궁극적인 최종 목표 중의 하나랍니다.
현대의 수학 수준으로는 숫자가 조금 커지면
슈퍼컴퓨터로도 적절한 시간내에 계산할 수 없습니다.
실제로 현대의 암호 체계가 바로
이 소인수분해의 어려움을 기반으로 하고 있습니다.
일단, 자연수 n 을 소인수분해만 하면
약수를 모두 구할 수 있고,
약수의 개수나 약수의 총합도 구할 수 있고,
Ф(n) 도 구할 수 있고,
등등...
할 수 있는 것이 많습니다.
즉, 최대공약수를 구한다는 것은
소인수분해를 하고 나면 저절로 얻어지는
부산물에 지나지 않습니다.
최대공약수를 소인수분해로 구하는 것은
금도끼로 장작을 패는 것과 같다
그런데, 현재까지 소인수분해 없이
두 자연수의 최대공약수를 구하는 유일한 방법이
유클리드 호제법입니다.
2. 유클리드 호제법
유클리드 호제법(互除法)은 명칭 자체가
'서로 서로 나누면서 계산하는 방법' 이라는 뜻인데,
나눗셈이 본질이 아님에도,
한국과 일본에서는 나눗셈으로 설명하기때문에
초보자들이 처음 배울 때 혼란을 많이 겪습니다.
유클리드 호제법은 무려 2300년 전 고대 그리스시절
유클리드가 쓴 '원론'에 나오는데요,
인류 역사상 가장 오래된 알고리즘이고
지금도 여전히 사용되는 원리입니다.
그리고, 명칭은
고대부터 지금까지 쭉 '유클리드 알고리즘' 입니다.
'호제법' 같은 나눗셈을 의미하는 내용은 전혀 없구요.
3. 유클리드 알고리즘의 원리
유클리드 알고리즘의 본질은
나눗셈이 아니라 뺄셈입니다.
두 자연수 a, b 의 최대공약수를 보통
gcd(a, b) 또는 (a, b) 로 표기합니다.
(a, b) = g 라 하면, (a < b)
a = g·A
b = g·B
로 쓸 수 있고,
b-a = g·(B-A)
가 됩니다.
즉, b-a 도 g 를 인수로 가집니다. 그러면,
g=(a, b)=(a, b-a)
로 쓸 수 있죠.
자세히보면, (a, b) 보다 (a, b-a) 가
구성요소로 들어가 있는 숫자가 작습니다.
즉, 이 시행을 반복하면 숫자가 점점 작아져서
점점 계산하기가 편해지겠죠.
유클리드 알고리즘의 시행은 아래와 같습니다.
① (a, b) 에서 둘 중에 작은 수는 남기고,
큰 수는 두 수의 차로 대신한다.
② 앞의 ① 의 시행을 원하는 만큼 반복한다.
예를 들어, 238 과 63 의 최대공약수를
유클리드 알고리즘으로 계산하는 과정은
아래와 같습니다.
즉, 두 수의 최대공약수는 7 이죠.
원래 (7, 0) 까지 진행하고 종료하도록 되어 있지만,
(7, 7) 에서 종료하는것이 알기 쉽습니다.
그 전에라도 (14, 7) 같은데서 멈추고 암산해도 됩니다.
여기서, 반복되는 뺄셈을 간편하게 하기위해
아래와 같이 나눗셈을 쓰면 편리해 집니다.
각 단계에 쓰인 나눗셈은 아래와 같습니다.
나눗셈을 하고나서 몫은 버리고, 나머지를 가져다가
다음 단계의 최대공약수 계산에 사용합니다.
뺄셈으로 된 알고리즘을 직접 따라가 보면
나눗셈으로 다시 쓴 로직을 바로 깨달을 수 있습니다.
나눗셈은 반복적인 뺄셈을
효율적으로 줄여주는 도구에 불과하죠
중,고등학생이 정수론을 배울때
유클리드 알고리즘은 골수에 새겨넣어야 하는
기본지식에 해당합니다.
나눗셈에 현혹되지말고, 본질을 이해하고 공부하면
두 배로 재미있게 즐길 수 있습니다.