두 정수 A와 B의 최대공약수(GCD)는 A와 B를 나누어떨어지게 하는 수 중 가장 큰 정수라는 사실을 기억해 봅시다.
유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 쉽게 알아내는 방법입니다.

알고리즘

A와 B의 최대공약수 GCD(A,B)를 알아내는 유클리드 호제법은 다음과 같습니다:
  • A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춥니다. 
  • B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈춥니다. 
  • A를 A = B⋅Q + R의 형식으로 씁니다
  • GCD(A,B) = GCD(B,R)이므로 유클리드 호제법을 이용하여 GCD(B,R)을 찾습니다.

예제:

270과 192의 최대공약수를 찾아 봅시다
  • A=270, B=192
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 270/192=1 나머지 78입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다: 270 = 192 * 1 +78
  • GCD(270,192)=GCD(192,78)이므로 GCD(192,78)를 찾습니다
A=192, B=78
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 192/78 = 2 나머지 36입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 192 = 78 * 2 + 36
  • GCD(192,78)=GCD(78,36) 이므로 GCD(78,36)을 찾습니다
A=78, B=36
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 78/36 = 2 나머지 6입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 78 = 36 * 2 + 6
  • GCD(78,36)=GCD(36,6)이므로 GCD(36,6)을 찾습니다
A=36, B=6
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 36/6 나머지 0입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 36 = 6 * 6 + 0
  • GCD(36,6)=GCD(6,0) 이므로 GCD(6,0)을 찾습니다
A=6, B=0
  • A ≠0
  • B =0, GCD(6,0)=6
이제까지의 과정을 정리하면 다음과 같습니다:
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6

Understanding the Euclidean Algorithm

유클리드 호제법은 다음과 같은 성질을 이용한다는 것을 알 수 있습니다.
  • GCD(A,0) = A
  • GCD(0,B) = B
  • A = B⋅Q + R이고 B≠0이면 GCD(A,B) = GCD(B,R) 이 때 Q는 정수, R은 0에서 B-1의 정수
처음 두 개의 성질을 이용하면 두 수 중 하나가 0일 때 최대공약수를 찾을 수 있습니다. 세 번째 성질을 이용하면 크고 복잡한 문제를 더 작고 쉬운 문제로 줄여서 풀 수 있습니다.
유클리드 호제법은 첫 두 성질 중 하나를 이용하여 문제를 쉽게 풀 수 있을 때까지 세 번째 성질을 이용하여 문제를 보다 쉬운 문제로 바꿔 나갑니다.
이를 증명함으로써 이런 성질이 어떻게 작용하는지 이해할 수 있습니다.
GCD(A,0)=A는 다음과 같이 증명할 수 있습니다:
  • A를 나누어떨어지게 하는 가장 큰 정수는 A입니다.
  • 모든 정수 C에 대해 C ⋅ 0 = 0이므로 모든 정수는 0을 나누어떨어지게 합니다. 그러므로 A도 0을 나누어떨어지게 합니다.
  • A와 0을 모두 나누어떨어지게 하는 가장 큰 수는 A입니다.
GCD(0,B)=B에 대한 증명도 비슷합니다 (A를 B로 바꾸기만 하면 됩니다).
GCD(A,B)=GCD(B,R)을 증명하기 위해 GCD(A,B)=GCD(B,A-B)임을 먼저 보여야 합니다.
Suppose we have three integers A,B and C such that A-B=C.
GCD(A,B)가 C를 나누어떨어지게 한다는 것에 대한 증명
정의에 의해 GCD(A,B)는 A를 나누어떨어지게 합니다. 결과적으로 A는 GCD(A,B)의 배수입니다. i.e. 모든 정수 X에 대해 X⋅GCD(A,B)=A
정의에 의해 GCD(A,B)는 B를 나누어떨어지게 합니다. 결과적으로 B는 GCD(A,B)의 배수입니다. i.e. 모든 정수 Y에 대해 Y⋅GCD(A,B)=B
A-B=C로 다음을 도출할 수 있습니다:
  • X⋅GCD(A,B) - Y⋅GCD(A,B) = C
  • (X - Y)⋅GCD(A,B) = C
그러므로 GCD(A,B)는 C를 나누어떨어지게 한다고 할 수 있습니다.
아래 그림은 위의 증명을 나타냅니다:
Proof that the GCD(B,C) evenly divides A
정의에 의해 GCD(B, C)는 B를 나누어떨어지게 합니다. 결과적으로 B는 GCD(B, C)의 배수이어야 합니다. i.e. 모든 정수 M에 대해 M⋅GCD(B,C)=B
정의에 의해 GCD(B, C)는 C를 나누어떨어지게 합니다. 결과적으로 C는 GCD(B, C)의 배수이어야 합니다. i.e. 모든 정수 N에 대해 N⋅GCD(B,C)=C
A-B=C로 다음을 도출할 수 있습니다:
  • B+C=A
  • M⋅GCD(B,C) + N⋅GCD(B,C) = A
  • (M + N)⋅GCD(B,C) = A
그러므로 GCD(B,C)는 A를 나누어떨어지게 한다고 할 수 있습니다.
아래 그림은 위의 증명을 나타냅니다:
Proof that GCD(A,B)=GCD(A,A-B)
  • 정의에 의해 GCD(A,B)는 B를 나누어떨어지게 합니다.
  • GCD(A,B)는 C를 나누어떨어지게 한다는 것을 증명했습니다.
  • GCD(A,B)가 B와 C를 모두 나누어떨어지게 하므로 이는 B와 C의 공약수입니다.
GCD(B,C)는 B와 C의 “최대” 공약수이므로 GCD(A,B)는 GCD(B,C)보다 작거나 같아야 합니다.
  • 정의에 의해 GCD(B,C)는 B를 나누어떨어지게 합니다.
  • GCD(B,C)는 A를 나누어떨어지게 한다는 것을 증명했습니다.
  • GCD(B,C)가 A와 B를 모두 나누어떨어지게 하므로 이는 A와 B의 공약수입니다.
GCD(A,B)는 A와 B의 “최대” 공약수이므로 GCD(B, C)는 GCD(A, B)보다 작거나 같아야 합니다.
GCD(A,B)≤GCD(B,C)이고 GCD(B,C)≤GCD(A,B)이므로 다음과 같은 결론을 내릴 수 있습니다:
GCD(A,B)=GCD(B,C)
이는 다음과 같습니다:
GCD(A,B)=GCD(B,A-B)
아래 그림은 위의 증명을 나타냅니다:
Proof that GCD(A,B) = GCD(B,R)
GCD(A,B)=GCD(B,A-B)라는 것을 증명했습니다
항목 간 순서는 상관이 없으므로 GCD(A,B)=GCD(A-B,B)라고 할 수 있습니다
GCD(A,B)=GCD(A-B,B) 를 반복적으로 적용하면 다음과 같이 됩니다:
GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=...=GCD(A-Q⋅B,B)
그렇지만 A= B⋅Q + R이므로  A-Q⋅B=R입니다
그러므로 GCD(A,B)=GCD(R,B)입니다
항목 간 순서는 상관이 없으므로 다음이 성립합니다:
GCD(A,B)=GCD(B,R)
다음 글에서 유클리드 호제법을 확장하여 모듈러 역수를 구하는 법에 대해 알아보도록 합시다.