ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố. Nhưng có 1 phương pháp tối ưu nhất là sử dụng thuật toán Euclid dựa trên dãy liên tiếp các phép chia có dư.

Ví dụ: Tính ước số chung lớn nhất của 91 và 287.

Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:

• 287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)

*Định nghĩa

Ước chung lớn nhất của hai số nguyên a và b là số nguyên dương lớn nhất mà a và b chia hết.

Bội số chung nhỏ nhất của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b.
**********************************
*ƯCLN của hai số có thể tìm được bằng việc phân tích hai số đó ra thừa số nguyên tố. Nhưng có 1 phương pháp tối ưu nhất là sử dụng thuật toán Euclid dựa trên dãy liên tiếp các phép chia có dư.
**********************************

 *Viết chương trình con (hàm, thủ tục) tính bội số chung nhỏ nhất của hai số nguyên dương a, b.

Ta nhận thấy rằng, bội số chung nhỏ nhất của hai số nguyên dương a, b có thể được tính theo công thức:

ab/d

trong đó d là ước chung lớn nhất của a và b.

Bởi vậy:

Nên viết hàm để tính bội chung nhỏ nhất của hai số nguyên dương vì chương trình con cần trả ra một giá trị;

- Hàm tính bội chung nhỏ nhất của hai số nguyên dương a, b cần sử dụng hàm tính ước chung lớn nhất của a và b.

- Hàm tính ước chung lớn nhất của hai số nguyên dương a, b:

 

Viết chương trình con (hàm, thủ tục) tính bội số chung nhỏ nhất của hai số nguyên dương a, b.

Ta nhận thấy rằng, bội số chung nhỏ nhất của hai số nguyên dương a, b có thể được tính theo công thức:

ab/d

trong đó d là ước chung lớn nhất của a và b.

Bởi vậy:

Nên viết hàm để tính bội chung nhỏ nhất của hai số nguyên dương vì chương trình con cần trả ra một giá trị;

- Hàm tính bội chung nhỏ nhất của hai số nguyên dương a, b cần sử dụng hàm tính ước chung lớn nhất của a và b.

- Hàm tính ước chung lớn nhất của hai số nguyên dương a, b: