Теорема. (Алгоритм Евкліда)

Якщо а = b·q₀ + r₁, 0 ≤ r₁ < b,

b = r₁q₁ + r₂, 0 ≤ r₂ < r_1,

………………………..

r_n-2 = r_n-1q_n-1 + r_n, 0 ≤ r_n < r_n-1,

r_n-1 = r_nq_n.

то (а; b) = r_n.

Доведення. На основі Леми 2 отримаємо з першого рядка (a, b) = (b, r₁); з другого рядка (b, r₁) = (r₁, r₂), і т.д. Отже, (a, b) = (r_т-1, r_n). Але, r_т-1 r_n і на основі Леми 1 (r_т-1, r_n) = r_n, а тому (a, b) = (r_n).