Template:Euclidean algorithm steps

Compute the Euclidean algorithm step by step:
a = 119; b = 61 a = 119; b = 61

= q₀ × + r₀
q₀ = ; r₀ =
Since r₀ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₁ × + r₁
q₁ = ; r₁ =
Since r₁ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₂ × + r₂
q₂ = ; r₂ =
Since r₂ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₃ × + r₃
q₃ = ; r₃ =
Since r₃ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₄ × + r₄
q₄ = ; r₄ =
Since r₄ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₅ × + r₅
q₅ = ; r₅ =
Since r₅ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₆ × + r₆
q₆ = ; r₆ =
Since r₆ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₇ × + r₇
q₇ = ; r₇ =
Since r₇ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₈ × + r₈
q₈ = ; r₈ =
Since r₈ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₉ × + r₉
q₉ = ; r₉ =
Since r₉ = 0 the algorithm is finished. Thus GCD( , ) = .

---

= q₁₀ × + r₁₀
q₁₀ = ; r₁₀ =
Since r₁₀ = 0 the algorithm is finished. Thus GCD( , ) = .

Start

1