2. Phương trình đồng dư tuyến tính

Cho \(n\) là số nguyên dương và \(a\), \(b\) là các số nguyên dương nhỏ hơn \(n\). Phương trình đồng dư tuyến tính modulo \(n\) có dạng

(2.4)\[a x \equiv b \pmod n\]

với \(x\) là ẩn.

Chú ý 2.4

Đặt \(d = \gcd(a, n)\). Khi đó, phương trình đồng dư có nghiệm khi và chỉ khi \(d \mid b\).

Nếu \(x_0\) là nghiệm thì phương trình có đúng \(d\) nghiệm không đồng dư theo modulo \(n\).

Việc chứng minh điều kiện đủ của nhận xét trên cho ta điều kiện để phương trình có nghiệm, trong khi chứng minh điều kiện cần sẽ cho ta cách tìm nghiệm đó.

Do \(d = \gcd(a, n)\), khi đó tồn tại các số nguyên \(a_1\) và \(n_1\) sao cho \(a = d a_1\) và \(n = d n_1\).

Điều kiện đủ. Giả sử phương trình có nghiệm \(x_0\), khi đó phương trình tương đương với

\[a x_0 - b = k n \Longleftrightarrow d a_1 x_0 - b = k n = k d n_1, \ k \in \mathbb{Z}.\]

Như vậy ta có

\[d \mid (d a_1 x_0 - k d n_1 = b),\]

hay \(d \mid b\).

Điều kiện cần. Nếu ta có \(d \mid b\) thì ta suy ra

\[a x \equiv b \pmod n \Longrightarrow \frac{a}{d} x \equiv \frac{b}{d} \pmod{\frac{n}{d}}.\]

Đặt \(b_1 = b / d\). Vì \(d = \gcd(a, n)\) nên \(\gcd(a_1, n_1) = 1\), Theo bổ đề Bezout thì tồn tại các số \(u, v \in \mathbb{Z}\) sao cho

\[a_1 u + n_1 v = 1 \Longrightarrow d a_1 u + d n_1 v = d \Longleftrightarrow a u + n v = d.\]

Nhân hai vế đẳng thức cuối với \(b_1\) ta có

\[a b_1 u + n b_1 v = d b_1 = b \Longrightarrow a (b_1 u) \equiv b \pmod n.\]

Như vậy \(x_0 = b_1 u\) là một nghiệm của phương trình đồng dư \(ax \equiv b \pmod n\).

Tiếp theo chúng ta chứng minh phương trình có \(d\) nghiệm không đồng dư modulo \(n\). Giả sử \(x_1\) là một nghiệm khác \(x_0\). Khi đó

\[a (x_1 - x_0) \equiv 0 \pmod n \Longrightarrow n \mid a(x_1 - x_0).\]

Do \(d = \gcd(a, n)\) nên ta suy ra \(n_1 \mid a_1 (x_1 - x_0)\), và do \(\gcd(a_1, n_1) = 1\) từ trên nên ta tiếp tục suy ra \(n_1 \mid (x_1 - x_0)\). Như vậy tồn tại \(k \in \mathbb{Z}\) để \(x_1 = x_0 + k n_1\), nghĩa là mọi nghiệm của phương trình đều có dạng \(x_0 + k n_1\) với \(k \in \mathbb{Z}\).

Ngoài ra, theo thuật chia Euclid, với hai số nguyên \(k\) và \(d\) luôn tồn tại hai số nguyên \(q\) và \(r\) để \(k = qd + r\) với \(0 \leqslant r < d\). Khi đó

\[x_1 = x_0 + k n_1 = x_0 + (qd + r) n_1 = x_0 + (d n_1) q + r n_1 = x_0 + r n_1 + n q,\]

nói cách khác nghiệm \(x_1\) đồng dư theo dạng

\[x_1 \equiv x_0 + r n_1 \pmod n.\]

Vì \(0 \leqslant r < d\) nên ta có họ các nghiệm không đồng dư của phương trình ban đầu là

\[x_0 + 0 \cdot n_1, x_0 + 1 \cdot n_1, \ldots, x_0 + (d-1) \cdot n_1.\]

Ví dụ 2.7

Xét phương trình \(9x \equiv 6 \bmod 12\). Vì \(3 = \gcd(9, 12)\) và \(3 \mid 6\) nên phương trình có nghiệm.

Chia các vế của phương trình cho \(3\) ta được \(3x \equiv 2 \bmod 4\). Như vậy, dùng thuật toán Euclid mở rộng, ta tính

\[x_0 \equiv 3^{-1} \cdot 2 \equiv 3 \cdot 2 \equiv 2 \bmod 4.\]

Các nghiệm của phương trình là

\[x_0 = 2 + 0 \cdot 4 = 2, x_1 = 2 + 1 \cdot 4 = 6, x_2 = 2 + 2 \cdot 4 = 10.\]