def gcd(a,b):
    while (b != 0):
        r = a % b # chia lấy phần dư
        a = b
        b = r
    return a

• Định lý Bézout chỉ ra rằng, nếu thì tồn tại hai số sao cho . Phương trình này được gọi là đồng nhất thức Bézout (Bézout identity). Hai số được gọi là hệ số Bézout (Bézout coefficents) của hai số .
• Phương trình Diophantine là phương trình có dạng được mô tả dựa trên định lý Bézout. Phương trình có nghiệm khi và chỉ khi . Một khi phương trình có nghiệm thì sẽ có vô số nghiệm.
  • Giả sử phương trình có nghiệm . Họ nghiệm của phương trình sẽ là . Để ý rằng:
    (Lưu ý, chú thích trên không phải là phần chứng minh họ nghiệm. Bài viết này không trình bày phần chứng minh)
  • Giả sử phương trình có nghiệm , thì là nghiệm của phương trình .

• Dùng thuật toán Euclid để tìm :
• Vậy . Công việc chúng ta là tìm một nghiệm của .
• Đi ngược từ dưới lên:
• Vậy một nghiệm của phương trình là .
• Suy ra một nghiệm của phương trình là . (ans)

m = xm*a + ym*b
n = xn*a + yn*b
r = xr*a + yr*b

def ext_gcd(a,b):
    m, n = a, b
    xm, ym = 1, 0
    xn, yn = 0, 1
    while (n != 0):
        q = m // n # chia lấy phần nguyên
        r = m % n # chia lấy phần dư
        xr, yr = xm - q*xn, ym - q*yn
        m = n
        xm, ym = xn, yn
        n = r
        xn, yn = xr, yr
    return (xm, ym) # m = gcd(a,b) = xm * a + ym * b

• Đặt nghiệm , với (điều kiện thứ nhất) và chia hết cho tất cả các giá trị còn lại (điều kiện thứ hai). Khi đó sẽ là nghiệm bài toán.
• Vấn đề đặt ra là tìm các giá trị để khi lấy tổng sẽ cho ra nghiệm của bài toán.
• Nếu ta đặt , thì sẽ chia hết cho mọi giá trị còn lại , ngoại trừ . Tuy nhiên, như vậy chỉ mới thỏa một điều kiện.
• Để , thì phải được nhân modulo với một thừa số bằng . Lúc này, . Việc nhân thêm thừa số này không ảnh hưởng đến tính thỏa mãn của điều kiện thứ nhất.

• .

• Họ nghiệm hệ phương trình là