유클리드 호제법

2025.10.24 18:05

두 정수 a를 b로 나눈 값을 아래처럼 표현하면 (a ≥ b)

a = bq + r   (단, 0 ≤ r < b)

다음 정리가 성립한다.

(a, b) = (b, r)

즉, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질을 나머지가 0이 될 때까지 반복하면 마지막에 남는 0이 아닌 수가 gcd(a, b)이다.

예시

(1071, 1029)
= (1029, 42)
= (42, 21)
= (21, 0)
= 21

따라서 gcd(1071, 1029) = 21

a,b ∈ Z 이고 a ≥ b 라 하자.

두 정수 a를 b로 나눈 값을 아래처럼 표현할 수 있다.
```
a = bq + r,   0 ≤ r < b
```
(a, b) = d 라고 하고, a = dα, b = dβ 라 해보자.
- 이때 α, β 는 서로소이다. (a와 b의 최대공약수인 d로 a와 b를 나눈 몫들은 더 이상 공약수를 가질 수 없기 때문이다.)
- a = bq + r 에 대입하면
```
d·α = d·β·q + r
r = d(α − β·q)
```
- 따라서 d | r (d는 r의 약수이다).
- d는 b와 r의 공약수이므로 (b, r) ≥ d 이다.
(b, r) = c라 하고 b = cβ′, r = cρ 라 해보자.
- a = bq + r = cβq + cp = c(β′q + ρ)
- 따라서 c | r (c는 r의 약수이다).
- 따라서 c는 a, b의 공약수이며, (a, b) ≥ c 이다.
결국 (a, b) = (b, r) 가 성립한다.
즉, 어떤 수가 a와 b를 나누면 r = a − bq 도 나누고, 반대로 b와 r을 나누는 수는 a도 나눈다.

확장 유클리드 호제법 (Extended Euclidean Algorithm)

확장 유클리드 알고리즘은 유클리드 호제법을 수행하면서 베주 항등식의 x, y 를 함께 계산하는 방법이다.

a·x + b·y = g

유클리드 호제법의 과정을 다음과 같이 나타내보자.

a = bq₀ + r₀
b = r₀q₁ + r₁
r₀ = r₁q₂ + r₂
⋯
r₍ₖ₋₂₎ = r₍ₖ₋₁₎qₖ + rₖ
r₍ₖ₋₁₎ = rₖq₍ₖ₊₁₎ + 0

마지막에 나온 나머지 rₖ 가 바로 gcd(a, b) = g 이다. 각 단계의 나머지 rᵢ 는 a, b의 어떤 정수 계수 조합으로 이루어져 있다. 식으로 표현하면 항상 다음이 성립한다:

rᵢ = sᵢ·a + tᵢ·b

a와 b의 정수 계수 결합(integer linear combination)으로 표현 가능하다고도 표현한다.

단계별로 확인해 보면, 패턴이 반복적으로 유지된다.

첫 번째 단계

a = b·q₀ + r₀

정리하면
r₀ = a - b·q₀
r₀ = 1·a + (-q₀)·b

따라서
s₀ = 1,
t₀ = -q₀

두 번째 단계

b = r₀·q₁ + r₁

정리하면
r₁ = b - q₁·r₀

위에서 r₀ = a - b·q₀ 이므로
r₁ = b - q₁(a - b·q₀)
= (-q₁)·a + (1 + q₀·q₁)·b

즉,
s₁ = -q₁,
t₁ = 1 + q₀·q₁

일반화 (귀납 단계)

각 단계의 나눗셈은 다음과 같다:

r₍ᵢ₋₂₎ = qᵢ·r₍ᵢ₋₁₎ + rᵢ

정리하면:
rᵢ = r₍ᵢ₋₂₎ - qᵢ·r₍ᵢ₋₁₎

귀납 가정으로, 이전 두 항은 이미 a, b의 선형결합이라 하자:

r₍ᵢ₋₁₎ = s₍ᵢ₋₁₎·a + t₍ᵢ₋₁₎·b
r₍ᵢ₋₂₎ = s₍ᵢ₋₂₎·a + t₍ᵢ₋₂₎·b

이를 위 식에 대입하면:

rᵢ = (s₍ᵢ₋₂₎ - qᵢ·s₍ᵢ₋₁₎)·a + (t₍ᵢ₋₂₎ - qᵢ·t₍ᵢ₋₁₎)·b

즉,

sᵢ = s₍ᵢ₋₂₎ - qᵢ·s₍ᵢ₋₁₎
tᵢ = t₍ᵢ₋₂₎ - qᵢ·t₍ᵢ₋₁₎

이 된다.

이제 위의 귀납식을 반복문으로 구현할 수 있다.

초기 값

r₀ = a s₀ = 1 t₀ = 0
r₁ = b s₁ = 0 t₁ = 1

이후 r₍ᵢ₋₁₎ 이 0이 될 때까지 반복한다.

q = r₍ᵢ₋₁₎ // rᵢ
r₍ᵢ₊₁₎ = r₍ᵢ₋₁₎ − q·rᵢ
s₍ᵢ₊₁₎ = s₍ᵢ₋₁₎ − q·sᵢ
t₍ᵢ₊₁₎ = t₍ᵢ₋₁₎ − q·tᵢ

마지막으로 남은 r(i) 가 gcd(a, b)이고, 그때의 s(i)와 t(i)가 바로 베주 항등식의 해 x, y가 된다.

a·sᵢ + b·tᵢ = rᵢ = gcd(a, b)

1071, 1029 유클리드 나눗셈 과정:

1071 = 1029×1 + 42
1029 = 42×24 + 21
42 = 21×2 + 0
gcd(1071, 1029) = 21

1071×(−24) + 1029×25 = 21
x = −24, y = 25