유클리드 호제법

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 를 함께 계산하는 방법이다.

베주 항등식, Bézout’s identity

임의의 정수 a, b 에 대해 gcd(a, b) = g 라 하면,

정수 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₀ = a − bq₀ = 1·a + (−q₀)·b

즉, r₀ = s₀·a + t₀·b (여기서 s₀ = 1, t₀ = −q₀)

⸻

🔹 다음 단계

r₁ = b − r₀q₁
    = b − q₁(a − bq₀)
    = (−q₁)·a + (1 + q₀q₁)·b

따라서 r₁ = s₁·a + t₁·b (여기서 s₁ = −q₁, t₁ = 1 + q₀q₁)

⸻

🔹 귀납적 단계

유클리드 알고리즘의 일반식은

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

이므로, 이를 정리하면

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

앞서 귀납 가정으로 r₍ᵢ₋₁₎ = s₍ᵢ₋₁₎·a + t₍ᵢ₋₁₎·b, r₍ᵢ₋₂₎ = s₍ᵢ₋₂₎·a + t₍ᵢ₋₂₎·b 라 하면, 라 하면,

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

즉, rᵢ = sᵢ·a + tᵢ·b sᵢ = s₍ᵢ₋₂₎ − qᵢ·s₍ᵢ₋₁₎ tᵢ = t₍ᵢ₋₂₎ − qᵢ·t₍ᵢ₋₁₎

이 귀납적으로 성립한다.

⸻

🔹 결론

마지막 단계에서 r_k = \gcd(a, b) = g 이므로,

r_k = s_k·a + t_k·b

따라서

\boxed{a·x + b·y = g}

을 만족하는 정수 x = s_k,, y = t_k 가 존재한다.

다음 불변식을 유지하면서 gcd와 베주 계수를 함께 계산할 수 있다.

초기값:

r0 = a, s0 = 1, t0 = 0
r1 = b, s1 = 0, t1 = 1

반복식:

q = r(i−1) // r(i)
r(i+1) = r(i−1) − q·r(i)
s(i+1) = s(i−1) − q·s(i)
t(i+1) = t(i−1) − q·t(i)

r(i+1) = 0 이 되면 반복을 중단한다. 이때 gcd(a, b) = r(i), 그리고 a·s(i) + b·t(i) = r(i)가 성립한다.

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