Mình có bài tập tìm ƯSCLN(a,b), mình search trên mạng thì tìm thấy thuật toán Euclid, có đoạn như thế này :

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ận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:

91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)

Cuối cùng ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14.
Cái này là dựa trên cơ sở toán học nào ? Mình nghĩ mãi mà không hiểu .


Mong các bác giải thích giúp. Cám ơn !



p/s: câu "...chia hết bởi..." là gì ?