Số Học Đồng Dư (Phần 2): Phương Trình Đồng Dư Tuyến Tính

Trong bài viết này, chúng ta sẽ cùng nhau tìm hiểu một chủ đề quan trọng trong số học đồng dư, đó là phương trình đồng dư tuyến tính. Đây là một dạng phương trình phổ biến, thường không được đề cập nhiều trong chương trình Toán cấp THCS và THPT nhưng lại rất hữu ích trong nhiều lĩnh vực, đặc biệt là trong lập trình và giải quyết các bài toán cho các cuộc thi về tin học.

Dạng Phương Trình Và Cách Thức Giải

Phương trình đồng dư tuyến tính có dạng:

$$ a \cdot x \equiv b \ (\text{mod } n) $$

Trong phương trình này, $a$, $b$, và $n$ là các số nguyên dương và $x$ là nghiệm cần tìm. Nhiệm vụ của chúng ta là tìm tất cả các nghiệm $x$ thuộc đoạn $[0, n-1]$.

Vấn đề Nghiệm

Khi phương trình có nghiệm $x_0$, sẽ có vô số nghiệm $x$ theo công thức:
$$ x = x_0 + k \cdot n \quad (k \text{ là số nguyên}) $$
Đặc biệt, chúng ta chỉ quan tâm đến các nghiệm trong đoạn $[0, n-1]$.

Trường Hợp Đơn Giản - GCD(a, n) = 1

Nếu $a$ và $n$ là hai số nguyên tố cùng nhau, tức là $ ext{GCD}(a,n) = 1$, ta có thể giải phương trình bằng cách tìm nghịch đảo modulo của $a$. Giải thuật Euclid mở rộng sẽ giúp tìm ra nghịch đảo này:
$$ x \equiv b \cdot a^{-1} \ (\text{mod } n) $$
Nghiệm này sẽ là duy nhất.

Trường Hợp Tổng Quát - GCD(a, n) ≠ 1

Trong trường hợp $a$ và $n$ không nguyên tố cùng nhau, ta xét $ ext{GCD}(a,n) = g$.

1. Trường hợp 1: Nếu $b$ không chia hết cho $g$, phương trình sẽ không có nghiệm. Điều này bởi vì bên trái của phương trình luôn chia hết cho $g$, trong khi bên phải không chia hết cho $g$.
2. Trường hợp 2: Nếu $b$ chia hết cho $g$, ta chia cả hai vế của phương trình cho $g$, nhận được phương trình mới mà $a_1$, $b_1$, và $n_1$ là các số nguyên tố cùng nhau. Nghiệm sẽ được tìm theo dạng sau:
   $$ x_1 \equiv b_1 \cdot a_1^{-1} \ (\text{mod } n_1) $$

Tìm Tất Cả Nghiệm

Sau khi tìm được nghiệm nhỏ nhất $x_1$, ta có thể tính tất cả các nghiệm còn lại bằng công thức:
$$x_i \equiv (x_1 + i \cdot n_1) \ (\text{mod } n) \quad \forall i: 0 \leq i < g$$

Cài Đặt

Khi xây dựng giải thuật, có thể sử dụng ngôn ngữ lập trình C++ như dưới đây:

#include <bits/stdc++.h>  
using namespace std;  
// Chương trình thực hiện giải thuật Euclid mở rộng  
void extended_euclid(int a, int b, int &x, int &y, int &g) {  
    if (b == 0) {  
        x = 1;  
        y = 0;  
        g = a;  
    } else {  
        extended_euclid(b, a % b, x, y, g);  
        int t = x;  
        x = y;  
        y = t - (a / b) * y;  
    }  
}  
main() {  
    int a, b, n;  
    cin >> a >> b >> n;  
    int x, y, g;  
    extended_euclid(a, n, x, y, g);  
    // ...  
    return 0;  
}```  

Tham khảo thêm các tài liệu chi tiết về giải thuật Euclid mở rộng và các bài toán liên quan tại các trang web toán học và lập trình.

# Kết Luận 
Phương trình đồng dư tuyến tính là một công cụ quan trọng trong số học đồng dư, có nhiều ứng dụng trong thực tế và cuộc sống hàng ngày. Qua bài viết, hy vọng bạn đã nắm vững kiến thức cơ bản để giải quyết loại phương trình này.
 source: viblo