ƯCLN theo thuật toán Euclid

Cho hai số nguyên không âm a, b, không đồng thời bằng 0. Nếu b=0 thì ƯCLN(a,0)=a. Nếu b>0, đặt r=a%b; ta có a=q×b+r. Nếu d là ước chung của a và b thì d cũng là ước của r; ngược lại, nếu d là ước chung của b và r thì d cũng là ước của a. Vì vậy hai cặp có cùng các ước chung: $$\operatorname{gcd}(a,b)=\operatorname{gcd}(b,a\bmod b).$$ Số dư luôn thỏa 0≤r<b, nên đối số thứ hai giảm tới 0.

```python def gcd(a, b): if b == 0: return a return gcd(b, a % b) ``` Cơ sở được đặt trước phép a%b để không chia cho 0. Với a=0, b>0, lời gọi tiếp là gcd(b,0) và trả b. Cặp (0,0) bị loại bởi điều kiện của bài toán, dù đoạn mã riêng lẻ vẫn có thể trả 0 khi bị gọi với cặp đó.

Bản lặp giữ cùng hai số a,b. Cần lưu số dư trước khi đổi a: ```python def gcd_lap(a, b): while b != 0: r = a % b a = b b = r return a ``` Một cách khác là trừ số nhỏ khỏi số lớn cho tới khi hai số bằng nhau. **Bản trừ dưới đây yêu cầu a,b đều dương**: ```python def gcd_tru(a, b): if a == b: return a if a > b: return gcd_tru(a - b, b) return gcd_tru(a, b - a) ``` Với hai số dương khác nhau, tổng a+b giảm sau mỗi bước mà ƯCLN không đổi. Nếu gọi bản này với (0,6), phép trừ vẫn cho (0,6), nên không tiến tới cơ sở. Không dùng điều kiện đầu vào của bản Euclid cho bản trừ khi chưa bổ sung xử lí số 0.