최대공약수(GCD) 계산기 — 유클리드 호제법

이 최대공약수 계산기는 유클리드 호제법으로 두 정수의 최대공약수를 구하고, 정수론이나 프로그래밍 수업에서 보여 주는 방식 그대로 모든 나눗셈 단계를 보여 줍니다. 확장 알고리즘으로 ax + by = gcd(a, b)를 만족하는 베주 계수 x, y와, 두 수가 서로소일 때의 모듈러 역원도 구합니다. 정수를 더 추가하면 목록 전체를 한 번에 계산합니다.

사용 방법

1. 두 정수 a와 b를 입력합니다.
2. 필요하면 최대공약수와 최소공배수에 포함할 정수를 더 나열합니다.
3. 최대공약수를 확인하고 표에서 유클리드 호제법의 단계를 따라갑니다.
4. 베주 계수나 모듈러 역원은 디오판토스 방정식이나 암호 관련 문제에 사용합니다.

계산식

gcd(a, b) = gcd(b, a mod b), 나머지가 0이 될 때까지 반복

각 단계에서 큰 수를 작은 수로 나눈 나머지로 바꾸고, 마지막 0이 아닌 나머지가 최대공약수입니다. 단계를 거꾸로 따라가면 a·x + b·y = gcd(a, b)를 만족하는 정수 x, y를 얻는데, 이것이 베주 항등식입니다. 또한 lcm(a, b) = |a × b| ÷ gcd(a, b)입니다.

예시

a = 1071, b = 462일 때 1071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0입니다. 마지막 0이 아닌 나머지가 gcd = 21입니다. 거꾸로 대입하면 21 = 1071 × (−3) + 462 × 7이므로 x = −3, y = 7이고, 최소공배수는 1071 × 462 ÷ 21 = 23,562입니다.