유클리드 호제법 계산기

a = q * b + r 이므로 gcd(a, b) = gcd(b, r); r = 0이 될 때까지 반복하고, 그때의 b가 답

a = q * b + r

알고리즘의 한 단계를 등식으로 쓴 것입니다. a는 그 단계에서 둘 중 큰 수, b는 작은 수, q는 b가 a에 몇 번 통째로 들어가는지, r은 남는 부분입니다. 이것이 이 페이지의 단계 표기 그대로이며, 1071 = 2 * 462 + 147이 한 단계입니다

a, b

비교하는 두 수입니다. 이 둘은 단계마다 역할이 바뀝니다. 한 단계의 b가 다음 단계의 a가 되고, r이 새로운 b가 됩니다. 그 뒤바뀜 때문에 입력 필드의 이름이 나누어지는 수와 나누는 수가 아닙니다. 첫 단계에서 1071은 나누어지는 수지만 둘째 단계에서는 462가 그렇고, 한 단계에만 맞는 이름은 나머지 단계에서 틀린 이름이 됩니다

q

몫이며, b가 a에 통째로 몇 번 들어가는지를 나타냅니다. 짝을 내림차순으로 정리한 뒤에 시작하므로 언제나 1 이상입니다. 이 페이지에서 q = 0을 볼 수 없는 이유도 같습니다. q가 눈에 띄지 않는 단계는 나머지가 0이라 나눗셈이 정확히 떨어지는 마지막 단계뿐입니다

r

나머지이며 언제나 b보다 작고 음수가 되지 않습니다. 알고리즘의 정지 규칙은 r = 0이고, 이는 생략하지 않고 마지막 단계로 인쇄됩니다. 147 = 7 * 21 + 0이 탐색이 끝났고 21이 답이라고 말해 주는 줄입니다

gcd(a, b)

최대공약수, 곧 a와 b를 나머지 없이 나누는 가장 큰 정수입니다. 답은 마지막 단계의 b를 루프에서 그대로 꺼낸 것이고 다시 계산한 값이 아닙니다. 1071과 462라면 21이며, 그래서 1071 = 21 × 51이고 462 = 21 × 22이며, 이 둘을 함께 나누는 더 큰 수는 없습니다

610 = 1 * 377 + 233

최악의 경우의 첫 단계로, 이웃한 피보나치수입니다. 여기서는 모든 몫이 1이고 수가 거의 줄지 않는데, 그래서 이 짝이 열세 단계를 씁니다. 래메의 정리는 이 정도 크기의 어떤 짝도 그보다 많은 단계를 쓸 수 없다고 말합니다

분수를 약분하는 일이 가장 흔한 쓰임입니다. 462/1071을 기약분수로 쓰려면 두 수의 최대공약수가 필요한데, 이 페이지는 그 값과 근거를 함께 줍니다. 21, 그리고 그것을 만들어 낸 세 단계입니다. 위아래를 21로 나누면 22/51이 되고, 인쇄된 단계가 있으면 그 약분을 믿는 대신 확인할 수 있습니다. 같은 필요는 비를 간단히 해야 할 때마다 나타납니다. 기어비, 화면 비율, 축척 도면, 그리고 두 수의 짝이 아니라 비례식으로 쓰고 싶은 모든 두 측정값이 그렇습니다. 두 번째 쓰임은 코드와 수업에 있습니다. 이 알고리즘은 첫 번째로 흥미로운 알고리즘으로 가르쳐집니다. 끝이 나고, 빠르고, 등식 하나에서 눈으로 확인되는 이유로 옳습니다. 모듈러 역원을 구하는 표준적인 방법이기도 하고, 확장판은 같은 단계를 따라 두 수를 더 들고 갑니다. RSA 키 생성 안에서 벌어지는 일이 바로 그 단계입니다. 세 번째 쓰임은 소인수분해를 하기 전의 가늠입니다. 1071이 3 × 357이고 462가 2 × 3 × 7 × 11임을 찾는 것은 일이지만, 둘의 최대공약수가 21임을 찾는 것은 나눗셈 세 번입니다. 그래서 이 페이지를 먼저 돌려 보면 약분이 쉬울지 시작하기 전에 알 수 있습니다. 과정이 아니라 답만 필요할 때는 gcf-calculator가 같은 질문을 더 짧은 형식으로 던지고 두 수를 넘어 여러 수를 한 번에 다룹니다. lcm-calculator는 이 인수를 써서 최소공배수를 구하는데, lcm = (a / gcd) * b이기 때문입니다. 나머지 하나의 의미를 수가 음수일 때까지 따지는 일은 remainder-calculator가 맡고, 이 페이지는 그 경우를 만나지 않습니다.

1. 교과서의 그 짝: 1071과 462

   1. 462가 1071에 몇 번 들어가는지 봅니다. 두 번이고 2 × 462 = 924이므로 1071 − 924 = 147이 남습니다
   2. 이제 짝은 462와 147입니다. 147은 462에 세 번 들어가고 3 × 147 = 441이므로 21이 남습니다
   3. 이제 짝은 147과 21입니다. 21은 147에 정확히 일곱 번 들어가고 0이 남습니다
   4. 나머지가 0이므로 알고리즘이 멈추고 답은 21입니다

   기본 입력이고, 이 알고리즘을 처음 소개할 때 쓰는 그 예입니다. 결과에 대해 두 가지를 확인해 볼 만합니다. 두 수를 21로 나누면 51과 22가 나오는데 이 둘은 공약수가 없고, 그래서 21이 그냥 공약수가 아니라 최대공약수입니다. 그리고 여기에는 소인수분해가 전혀 없었다는 점에 주목하십시오. 시행 나눗셈으로 1071의 인수를 찾으려면 32까지 올라가야 하지만, 이 알고리즘은 이미 손에 쥔 수로만 나눕니다. 세 단계이고, 한 단계마다 앞 단계보다 쌉니다.

2. 한 단계로 충분한 경우: 12와 60

   1. 짝을 내림차순으로 정리합니다. 60이 앞, 12가 뒤입니다
   2. 60 = 5 × 12 + 0이므로 12는 60을 정확히 나눕니다
   3. 나머지가 곧바로 0이라 알고리즘은 한 단계 만에 멈춥니다
   4. 답은 12, 곧 둘 중 작은 수입니다. 큰 수를 나누기 때문입니다

   가능한 가장 짧은 비자명한 실행이고, 마지막 단계를 생략하지 않고 인쇄하는 이유를 보여 주는 경우입니다. 60 = 5 * 12 + 0이라는 줄이 답의 전부입니다. 나머지가 0에 닿았다고 말해 주고, 이것이 이 알고리즘이 멈추는 유일한 방법입니다. 그 줄을 빼면 단계는 빈 문자열이 되고, 독자는 한 단계짜리 답과 아직 돌지 않은 페이지를 구분할 방법이 없습니다. 어느 한 수가 다른 수를 정확히 나누면 최대공약수는 그냥 작은 쪽입니다.

3. 서로소인 두 수: 9와 20

   1. 20 = 2 × 9 + 2이므로 짝은 9와 2가 됩니다
   2. 9 = 4 × 2 + 1이므로 짝은 2와 1이 됩니다
   3. 2 = 2 × 1 + 0이므로 알고리즘이 멈춥니다
   4. 답은 1이고, 이는 9와 20이 1보다 큰 공약수를 갖지 않는다는 뜻입니다

   최대공약수가 1인 것은 실패가 아니라 정상적인 답이고 이름도 있습니다. 두 수가 서로소입니다. 9/20이라는 분수가 이미 기약분수라 더 줄일 것이 없다는 신호이기도 합니다. 단계가 접히지 않았다는 점에 주목하십시오. 어느 쪽도 상대를 정확히 나누지 못했기 때문에 알고리즘은 세 단계를 거쳐 1까지 내려갔습니다. 수가 커질수록 서로소인 짝이 흔해집니다. 임의로 고른 두 수가 공약수를 가질 확률은 빠르게 떨어지고, 암호에서 모듈러 역원을 만들 때 이 방법이 쓸모 있는 이유가 바로 그것입니다.

두 수 모두 정수여야 하고, 둘 다 1에서 1000000 사이여야 합니다. 0은 특별한 경우로 다루지 않고 거부합니다. a와 0의 최대공약수는 a이고 그것은 완벽히 좋은 답이지만, 이 페이지는 그것을 보여 줄 수 없습니다. 첫 단계가 a = q * 0 + r이 되는데 그 q가 존재하지 않기 때문입니다. 구멍 난 과정을 인쇄하는 대신 페이지는 입력을 거절합니다. 음수도 같은 이유로 거부합니다. 인쇄되는 단계는 두 수가 1 이상이라고 전제하고, 음수 피연산자라면 몫과 나머지가 무엇을 뜻하는지에 대한 규칙이 필요한데 이 페이지는 그것을 어디에도 밝히지 않습니다. 1000000이라는 상한은 알고리즘 때문이 아닙니다. 훨씬 큰 수에서도 잘 돌아갑니다. 가는 길의 모든 뺄셈과 곱셈과 나머지가 보통의 배정도 정밀도 연산에서 정확하도록, 그리고 인쇄되는 단계가 읽을 수 없을 만큼 길어지지 않도록 두는 값입니다. 그런데도 작은 두 수가 많은 단계를 낼 수 있습니다. 610과 377은 열세 단계를 씁니다. 다만 실제로는 상한이 단계 수를 제한하고, 참고표에 단계 수 열이 있어 그것이 달라지는 모습을 볼 수 있습니다. 단계는 세로셈이 아니라 등식으로 인쇄되므로, 익숙한 나눗셈 기호를 찾고 있다면 이 페이지는 그것을 주지 않습니다. 두 입력은 서로 바꿔 넣을 수 있습니다. 페이지가 시작 전에 내림차순으로 정리하므로, 3 = 0 * 5 + 3이 어떤 모습인지 이 페이지에서 볼 수는 없습니다. 그 단계가 만들어지지 않기 때문입니다. 수가 음수일 수 있거나 나머지의 관례를 명시적으로 보고 싶다면 remainder-calculator가 그 질문을 맡습니다.

최대공약수를 한 문장으로 말하면 무엇인가요?

두 수를 나머지 없이 정확히 나누는 가장 큰 정수입니다. 1071과 462라면 21입니다. 1071 = 21 × 51이고 462 = 21 × 22이며, 51과 22는 공약수가 없고, 그래서 21이 최대입니다. 3과 7도 두 수를 모두 나눕니다. 다만 공약수일 뿐 최대공약수는 아닙니다. 페이지의 주 출력은 언제나 이 수이고, 그 아래의 단계는 그 근거입니다.

왜 마지막 단계는 언제나 + 0으로 끝나나요?

나머지가 0인 것이 알고리즘을 멈추는 유일한 사건이기 때문입니다. 루프는 짝을 더 작은 짝, 곧 둘째 수와 나머지로 바꾸고 수는 매 단계 줄어들므로 언젠가 0에 닿을 수밖에 없습니다. 147 = 7 * 21 + 0이 그 일이 벌어지는 단계이고, 최대공약수는 그 단계의 나누는 수인 21입니다. 페이지가 그것을 감추지 않고 인쇄하는 이유는, 마지막 0이 아닌 나머지에서 단계 목록이 멈추면 탐색이 끝났다는 사실을 독자가 스스로 알아내야 하기 때문입니다.

두 수를 넣는 순서가 결과에 영향을 주나요?

아니요. 페이지가 첫 단계 전에 내림차순으로 정리하므로 462와 1071은 1071과 462와 똑같은 세 줄을 냅니다. 이는 알고리즘의 성질이 아니라 페이지가 택한 방식입니다. gcd(a, b) = gcd(b, a)라는 규칙 덕분에 어느 순서로도 답은 맞지만, 정리를 하지 않으면 3과 5라는 짝의 첫 줄이 3 = 0 * 5 + 3이 됩니다. 합법적인 나눗셈이지만 작은 수를 큰 수로 나누는 일이 방법의 일부인 것처럼 읽힙니다. 입력 필드의 이름이 나누어지는 수와 나누는 수가 아닌 이유도 같습니다. 그 두 역할은 단계마다 뒤바뀝니다.

답이 1로 나오면 무슨 뜻인가요?

두 수가 1보다 큰 공약수를 갖지 않는다는 뜻이고, 실패가 아니라 완전한 답입니다. 그런 두 수를 서로소라고 부르며, 이 페이지의 9와 20이 그 예입니다. 실용적인 정보도 담겨 있습니다. 9/20이라는 분수가 이미 기약분수라 더 줄일 것이 없다는 뜻입니다. 수가 커질수록 서로소인 짝이 흔해지고, 암호에서 이 방법이 중요한 이유가 거기에 있습니다. RSA 키를 만드는 일은 주어진 수와 공약수를 갖지 않는 수를 찾는 일이기 때문입니다.

큰 수일수록 단계가 많아지나요?

아니요. 참고표가 그것을 구체적으로 보여 줍니다. 1000000과 999998은 두 단계로 끝나지만 세 자리 수인 610과 377은 열세 단계를 씁니다. 단계를 많이 만드는 것은 크기가 아니라 수가 줄어드는 속도이고, 가장 느리게 줄어드는 짝이 이웃한 피보나치수입니다. 그때는 나머지가 나누는 수에 가깝습니다. 이 결과가 래메의 정리이고, 단계 수에 자릿수에 따라서만 커지는 상한을 씌웁니다. 이 알고리즘이 빠르다고 하는 이유입니다.

두 수를 그냥 소인수분해하는 것과 무엇이 다른가요?

소인수분해가 훨씬 큰일이고, 이 페이지는 그 일을 하지 않습니다. 시행 나눗셈으로 1071을 소인수분해하려면 제곱근 근처인 32까지 나눠 보아야 하지만, 알고리즘은 이미 들고 있는 수로 나누면서 세 단계 만에 끝납니다. 이 정도로 작은 수에서는 차이가 보이지 않지만, 소인수분해는 수가 커질수록 급격히 어려워지는 반면 유클리드 호제법은 거의 영향받지 않습니다. 그 간격이 이 방법을 아직도 가르치는 이유의 전부이고, 위의 답이 두 번째 계산이 아니라 루프에서 나오는 이유이기도 합니다. 둘 다 돌리면 인쇄된 단계가 그 위에 인쇄된 수와 어긋날 위험이 생깁니다.

• Euclidean Algorithm — 점화식 gcd(a, b) = gcd(b, a mod b), 끝난다는 증명, 그리고 연분수와의 연결 — Wolfram MathWorld (United States)
• Greatest Common Divisor — 최대공약수가 무엇인지, 그리고 gcd(a, 0) = a가 알고리즘이 멈추는 기저 사례인 이유 — Wolfram MathWorld (United States)
• Lamé's Theorem — 크기에 비해 가장 많은 단계를 쓰는 짝은 언제나 이웃한 두 피보나치수라는 결과 — Wolfram MathWorld (United States)
• 教育部关于印发义务教育课程方案和课程标准(2022年版)的通知 — 이 통지의 첨부 목록 제5항이 《义务教育数学课程标准(2022年版)》에 해당하며, 최대공약수는 초등학교 고학년 수와 연산 영역의 내용이므로 원문과 학년군 구분은 이 첨부를 기준으로 합니다 — 中华人民共和国教育部