ƯCLN, BCNN và thuật toán Euclid

Trừ đi một bội của $b$ khỏi $a$ không thể tạo thêm hay làm mất ước chung với $b$: bất kỳ số nào chia hết cả $a$ và $b$ cũng phải chia hết phần dư $r=a-bq$, và ngược lại.

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)$.

Với mỗi ước nguyên tố $p$, $\gcd(a,b)$ lấy số mũ nhỏ hơn của $p$ trong $a,b$ còn $\operatorname{lcm}(a,b)$ lấy số mũ lớn hơn; cộng số nhỏ hơn và số lớn hơn trong hai số luôn bằng đúng tổng của hai số đó.

Bước 1. Viết phân tích thừa số nguyên tố của $a$ và $b$ trên mọi số nguyên tố $p$: $a=\prod_p p^{e_p}$ và $b=\prod_p p^{f_p}$, với $e_p,f_p\ge0$ và chỉ có hữu hạn số mũ khác không.

Bước 2. Một số nguyên dương $d=\prod_p p^{c_p}$ chia hết cả $a$ và $b$ khi và chỉ khi $c_p\le e_p$ và $c_p\le f_p$ với mọi $p$, nên ước lớn nhất chọn $c_p=\min(e_p,f_p)$: $\gcd(a,b)=\prod_p p^{\min(e_p,f_p)}$. Lập luận đối ngẫu cho bội chung chọn số mũ nhỏ nhất không nhỏ hơn cả hai, cho $\operatorname{lcm}(a,b)=\prod_p p^{\max(e_p,f_p)}$.

Bước 3. Với hai số thực bất kỳ, $\min(e_p,f_p)+\max(e_p,f_p)=e_p+f_p$. Nhân hai tích theo từng thừa số nguyên tố vì thế cho $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=\prod_p p^{\min(e_p,f_p)+\max(e_p,f_p)}=\prod_p p^{e_p+f_p}=\left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right)=ab$.