I. Giới Thiệu Chung

Khi nghiên cứu toán học, đặc biệt là đối với những ai yêu thích môn Toán học, khái niệm Phương trình Diophantine tuyến tính (Linear Diophantine Equation) không còn xa lạ. Đây là phương trình bậc nhất với hai ẩn có dạng:

[ ax + by = c ]

Trong đó: a, b, c là các số nguyên cho trước.

Giải phương trình Diophantine tuyến tính không phải là một việc dễ dàng; nó yêu cầu người giải có nền tảng kiến thức vững chắc về toán học, cùng với một số kỹ năng lập trình như thuật toán Euclid và thuật toán Euclid mở rộng. Trong bài viết này, chúng ta sẽ cùng nhau khám phá cách giải phương trình này và nghiên cứu một số bài tập biến thể liên quan, như:

• Tìm một nghiệm của phương trình.
• Tìm tất cả các nghiệm của phương trình.
• Đếm số nghiệm của phương trình trong một khoảng ràng buộc.
• Tìm nghiệm sao cho giá trị của x + y đạt mức tối thiểu.

Trước khi tiếp tục, người đọc nên tìm hiểu về Giải thuật Euclid mở rộng nếu chưa quen thuộc.

II. Giải Thuật Cơ Bản Tìm Một Nghiệm Của Phương Trình

Phân Tích Toán Học

Trước tiên, chúng ta cần tìm ra nghiệm riêng của phương trình. Trong trường hợp a=0 và b=0, phương trình có thể có vô số nghiệm hoặc không có nghiệm, tùy thuộc vào giá trị của c. Do đó, sẽ không bàn sâu về trường hợp này vì nó khá đơn giản.

Khi a và b đều khác không (a≠0, b≠0), phương trình có thể chuyển đổi thành:

[ \begin{cases} ax \equiv c \ (\text{mod } b) \ by \equiv c \ (\text{mod } a) \end{cases} ]

Không mất tính tổng quát, giả sử b không bằng 0, và biến đổi sang phương trình (1). Nếu a và b là hai số nguyên tố cùng nhau, nghiệm có dạng:

[ \begin{cases} x_0 \equiv c \cdot a^{-1} \ (\text{mod } b) \ y_0 = \frac{c - ax_0}{b} \end{cases} ]

Với: ( a^{-1} ) là nghịch đảo modulo b.

Nếu a và b không nguyên tố cùng nhau, ta có g = GCD(a, b). Khi đó, cả a và b đều chia hết cho g, và phương trình chỉ có nghiệm nếu c cũng chia hết cho g. Nghiệm sẽ có dạng:

[ \frac{a}{g} \cdot x_0 \equiv \frac{c}{g} \ (\text{mod } \frac{b}{g}) ]

Với g là GCD(a, b), ta có thể quay lại dạng nghiệm như trước.

Ý Tưởng Giải Thuật

Chúng ta sẽ sử dụng giải thuật Euclid mở rộng để tìm nghiệm. Giả sử a và b là các số nguyên không âm, thuật toán cho phép ta tìm GCD của chúng và các số x_g, y_g thỏa mãn:

[ ax_g + by_g = g ]

Nếu c chia hết cho g, phương trình sẽ có nghiệm. Nhân cả hai vế với ( \frac{c}{g} ), ta có:

[ a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c ]

Vì thế, nghiệm riêng của phương trình Diophantine sẽ là:

[ \begin{cases} x_0 = x_g \cdot \frac{c}{g} \ y_0 = y_g \cdot \frac{c}{g} \end{cases} ]

Giải thuật vẫn hoàn toàn chính xác khi a hoặc b là số nguyên âm; chỉ cần điều chỉnh dấu của x_0 hoặc y_0 tương ứng.

Cài Đặt

int extended_euclid(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1;
    int d = extended_euclid(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);

    return d;
}

bool find_one_solution(int a, int b, int c, int &x0, int &y0, int g) {
    g = extended_euclid(abs(a), abs(b), x0, y0);

    if (c % g != 0)
        return false;

    x0 *= c / g;
    y0 *= c / g;

    if (a < 0)
        x0 = -x0;
    if (b < 0)
        y0 = -y0;

    return true;
}

void solve_diophantine_equation(int a, int b, int c) {
    if (a == 0 && b == 0) {
        if (c == 0)
            cout << "Phương trình có vô số nghiệm";
        else
            cout << "Phương trình không có nghiệm";
    }

    int x0, y0, g;
    bool has_solution = find_one_solution(a, b, c, x0, y0, g);

    if (has_solution)
        cout << x0 << ' ' << y0;
    else
        cout << "Phương trình không có nghiệm";
}

Đánh Giá

Độ phức tạp của giải thuật tương đương với độ phức tạp của thuật toán Euclid mở rộng, do đó độ phức tạp tổng quát là: O(log(max(a,b))).

III. Một Số Vấn Đề Mở Rộng

1. Tìm Tất Cả Các Nghiệm Của Phương Trình Diophantine

Ý Tưởng

Từ việc tìm ra nghiệm riêng (x_0, y_0), ta có thể tìm tất cả các nghiệm của phương trình. Đặt g = GCD(a, b) và nếu đã tìm ra nghiệm (x_0, y_0), ta có thể tìm ra mọi nghiệm của phương trình dưới dạng tổng quát:

[ \begin{cases} x = x_0 + k \cdot \frac{b}{g} \ y = y_0 - k \cdot \frac{a}{g} \end{cases} ]

2. Tìm Tất Cả Nghiệm Trong Một Khoảng Đoạn

Ý Tưởng

Ở đây, chúng ta sẽ tìm nghiệm của phương trình trên các đoạn mà ta mong muốn. Giống như đã phân tích, nếu không có ràng buộc bổ sung, ta có thể có nhiều nghiệm.

3. Tìm Nghiệm Nhỏ Nhất Cho x + y

Đôi khi, yêu cầu là tìm nghiệm thỏa mãn yêu cầu về tổng x + y đạt giá trị nhỏ nhất trong các đoạn đã cho. Cách tiếp cận sẽ giống như ý tưởng tìm nghiệm theo ràng buộc.

IV. Tài Liệu Tham Khảo

• CP Algorithms - Linear Diophantine Equation
• Competitive Programming 3 - Steven Halim & Felix Halim.
• Wolfram MathWorld - Diophantine Equation
  source: viblo