Thuật toán Euclid được dùng để tìm ước chung lớn nhất của hai số nguyên không âm như sau:

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

Dựa trên định lý .

  • Đị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 .

Để tìm nghiệm của phương trình , thuật toán tìm ra một nghiệm của phương trình , rồi sau đó suy ra một nghiệm của phương trình . Từ đây có thể tiếp tục đưa ra họ nghiệm của phương trình và kết thúc bài toán.

Ví dụ, tìm một 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 .
  • Suy ra một nghiệm của phương trình . (ans)

Có thể suy ra họ nghiệm phương trình đã cho là

Tuy nhiên, khi trình bày thuật toán này trên máy tính, cần có cách làm ngắn gọn hơn là việc lưu trữ lại các bước của thuật toán Euclid.

Ý tưởng khác là song song với việc tìm ước chung lớn nhất của , ta duy trì bộ số thỏa mãn các điều kiện sau:

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

Như vậy thì khi thuật toán Euclid kết thúc, ta có số thu được là , cùng với xmxn là các hệ số Bézout của . Toàn bộ thuật toán như sau:

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

Nếu thì ta nói là nghịch đảo của theo modulo (hoặc ngược lại, là nghịch đảo của theo modulo ). Ký hiệu hoặc .

Phần này nói về cách tìm nghịch đảo của theo modulo .

Ta có:

Như vậy, nghịch đảo của theo modulo tồn tại khi và chỉ khi (điều kiện để phương trình trên có nghiệm). Để tìm được nghịch đảo modulo, ta phải giải phương trình và chọn ra nghiệm . Lưu ý, việc giải phương trình hay giải phương trình không ảnh hưởng nhiều đến việc tìm nghịch đảo modulo.

Ví dụ, ta có . Sử dụng hàm ext_gcd(103, 16) ta biết được .

Như vậy có hai điều rút ra được:

Họ nghiệm của phương trình . Điều này cho thấy khoảng cách giữa hai nghiệm liên tiếp là , chứng tỏ tồn tại duy nhất một nghịch đảo modulo của trong tập .

Nghịch đảo modulo là cách để chúng ta áp dụng “phép chia” vào hai vế của một phép đồng dư (congruence).

Với ví dụ cụ thể, mời các bạn tìm đọc bài viết về thuật toán mã hóa RSA.

Hệ phương trình đồng dư ẩn sau:

có nghiệm khi và chỉ khi đôi một nguyên tố cùng nhau và nghiệm là duy nhất theo modulo .

Chỉ ra một nghiệm:

Với .

Để tìm ra nghiệm trên:

  • Đặ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.

Theo định lý số dư Trung Quốc, nghiệm tìm được là duy nhất theo modulo , nên cách giải bài toán này có thể áp dụng để tìm số dư của chia cho , với dữ liệu cho biết số dư của khi lần lượt chia cho .

Ví dụ, biết . Hỏi

Ở đây mặc dù ta đã biết rồi, nhưng đây chỉ là một nghiệm trong họ nghiệm của hệ phương trình:

Ta vẫn cần phải tìm nghiệm cho hệ này để ra một nghiệm có giá trị nhỏ hơn, sau đó đem sẽ ra kết quả bài toán.

$$i$$ 1 2
$$a_i$$ 2 1
$$b_i$$ 7 11
$$p_i=\frac{B}{b_i}$$ 11 7
$$q_i\equiv p_i\pmod{b_i}$$ 2 8
$$x_i=a_ip_iq_i$$ 44 56


  • .

Vậy:

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

Trên thực tế, có một vài phép biến đổi để tìm mà không cần dùng chiêu “đao to búa lớn” như thế này. Tuy nhiên, cách giải này vô cùng quan trọng vì nó định ra được những bước tính toán cụ thể rạp khuôn để áp dụng vào lập trình, ít tốn kém hơn là dùng máy tính để “mô phỏng” cách làm bằng tay, vốn phụ thuộc nhiều vào khả năng quan sát tinh tế của người giải toán.