Tính bất biến và dừng của thuật toán Euclid

Bước 1 (Cùng tập ước chung). Giả sử $d$ là số nguyên chia hết cả $a$ và $b$, tức $a=dx$ và $b=dy$ với $x,y$ nguyên. Khi đó $r=a-bq=dx-dyq=d(x-yq)$, nên $d\mid r$, nghĩa là $d$ chia hết cả $b$ và $r$. Ngược lại, nếu $d$ chia hết cả $b$ và $r$, giả sử $b=dy$ và $r=dz$, thì $a=bq+r=dyq+dz=d(yq+z)$, nên $d\mid a$, nghĩa là $d$ chia hết cả $a$ và $b$.

Bước 2 (Hai ước chung lớn nhất bằng nhau). Vì hai cặp $(a,b)$ và $(b,r)$ có cùng tập hợp các ước chung, phần tử lớn nhất của chúng phải bằng nhau: $\gcd(a,b)=\gcd(b,r)$.

Bước 3 (Dừng sau hữu hạn bước). Mỗi bước chia tạo ra số dư thỏa $0\le r<b$, nên dãy các số thứ hai $b > r_1 > r_2 > \cdots \ge 0$ là dãy số nguyên không âm giảm ngặt. Dãy như vậy có nhiều nhất $b$ bước trước khi chạm $0$; tại bước $\gcd(r_{k-1},r_k)=\gcd(r_k,0)=r_k$, số dư khác không cuối cùng $r_k$ chính là $\gcd(a,b)$.