유클리드 호제법 단계별 계산기 사용법
두 자연수의 최대공약수(GCD)를 구하는 가장 효율적인 방법이 유클리드 호제법입니다. 두 수를 입력하면 이 계산기가 나눗셈을 반복하는 전 과정을 표로 보여주면서 최종 최대공약수를 계산합니다.
방법은 간단합니다. 큰 수 a를 작은 수 b로 나눈 나머지 r을 구한 뒤, b와 r을 새로운 한 쌍으로 삼아 같은 과정을 반복합니다. 나머지가 0이 되는 순간, 그 직전에 나누는 수로 쓰였던 값이 바로 두 수의 최대공약수입니다. 예를 들어 252와 105는 252=105×2+42, 105=42×2+21, 42=21×2+0의 과정을 거쳐 최대공약수 21을 얻습니다.
이 방법은 유클리드가 기원전 300년경에 정리한 것으로 알려진 매우 오래된 알고리즘이지만, 지금도 컴퓨터 과학의 암호학·분수 약분 등 다양한 분야에서 실제로 사용될 만큼 효율적입니다. 몇 단계 만에 답이 나오는지 직접 확인하면서 호제법의 원리를 익히는 데 활용해 보세요.
두 수의 크기 차이가 크더라도 나눗셈을 반복할수록 숫자가 빠르게 작아지기 때문에, 어떤 자연수 쌍이라도 비교적 적은 단계 안에 최대공약수를 찾을 수 있습니다. 분수를 약분하거나 두 수의 최소공배수를 구할 때도 최대공약수가 기초가 되므로 함께 알아두면 유용합니다.
자주 묻는 질문
두 수 a, b의 최대공약수를 구할 때 a를 b로 나눈 나머지로 b를 대체하는 과정을 나머지가 0이 될 때까지 반복하는 방법입니다. 나머지가 0이 되는 순간의 나누는 수가 바로 두 수의 최대공약수(GCD)입니다.
이 계산기는 0이 아닌 자연수 두 개를 입력하도록 안내합니다. 수학적으로 gcd(a, 0)=a로 정의되지만, 단계별 나눗셈 과정을 보여주는 이 도구의 목적에 맞지 않아 0 입력 시 오류 메시지를 표시합니다.