Nghiệm của các đồng dư thức và hệ thặng dư đầy đủ

Ký hiệu $f(x)$ là đa thức bậc $n$ với hệ số nguyên và $m$ là modulo cho trước. Tất cả các số $a$ mà $f(a) \equiv 0(\bmod m)$ được gọi là nghiệm của đồng dư thức

(6) $\quad f(x) \equiv 0(\bmod m)$ Từ Định lý 1 suy ra nếu $a$ là nghiệm của đồng dư thức (6) thì mọi số đồng dư với $a$ theo modulo $m$ cũng là nghiệm của (6). Do đó có thể coi lớp tất cả các số có cùng đồng dư là một nghiệm đơn của đồng dư thức. Nghiệm đơn này có thể được chọn bởi mọi số trong đó.

Mọi số nguyên là đồng dư theo modulo $m$ với một trong các số thuộc dãy

(7) $\quad 0,1,2, \ldots, m-1$.

Thật vậy, ký hiệu $a$ là số nguyên cho trước và $r=a-m\left[\frac{a}{m}\right]$. Số $r$ đồng dư với $a$ theo modulo $m$. Vì $t-1<[t] \leq t$ với mọi số thực $t$ nên ta có $\frac{a}{m}-1<\left[\frac{a}{m}\right] \leq \frac{a}{m}$, suy ra $0 \leq r<m$. Vì vậy $r$ thuộc dãy (7) và do đó mọi số tự nhiên $a$ là đồng dư theo modulo $m$ với ít nhất một trong các phần tử thuộc dãy (7). Mặt khác, các phần tử thuộc (7) là các đồng dư phân biệt modulo $m$ nên mọi số nguyên $a$ đồng dư với đúng một phần tử thuộc (7). Số này gọi là số dư của $a$ theo modulo $\mathrm{m}$.

Tất cả các số nguyên có cùng số dư $r$ modulo $m$ đều có dạng $m k+r$ với $k$ là số nguyên.

Để giải đồng dư thức (6) ( $f(x)$ là đa thức hệ số nguyên) ta chỉ cần tìm các số trong dãy (7) là nghiệm của đồng dư thức đó. Vậy (6) có thể được giải sau hữu hạn phép thử. Do đó về lý thuyết ta có thể tìm mọi nghiệm của $(6)(f(x)$ là đa thức hệ số nguyên) hoặc chứng minh $f(x)$ vô nghiệm.

Ví dụ

1. Giải đồng dư thức

$$(8) \quad x^{5}-3 x^{2}+2 \equiv 0(\bmod 7) .$$

Ta sẽ tìm xem trong các số $0,1,2,3,4,5,6$ thì số nào thỏa mãn (8). Lần lượt thế 0 và 1 vào $(8)$ ta thấy 1 là nghiệm và 0 không phải nghiệm của (8). Tương tự 2 không phải nghiệm. Ta có $3^{2} \equiv 2(\bmod 7)$ suy ra $3^{4} \equiv 4(\bmod 7)$ và $3^{5} \equiv 12 \equiv 5(\bmod 7)$. Do đó $3^{5}-3.3^{2}+2 \equiv 5-3.2+2 \equiv 1(\bmod 7)$ và vì vậy 3 không phải nghiệm. Với 4 ta có $4 k \equiv-3(\bmod 7)$ suy ra $4^{5} \equiv-3^{5} \equiv-5(\bmod 7)$ và do đó $4^{5}-3.4^{2}+2 \equiv-5-3.2+2 \equiv 3(\bmod 7)$ nên 4 không phải nghiệm của (8). Ta có $5 \equiv-2(\bmod 7)$ suy ra $5^{5} \equiv-2^{5} \equiv 3(\bmod 7)$ và $5^{5}-3.5^{2}+2 \equiv 3-3.4+2 \equiv 0(\bmod 7)$ do đó 5 là nghiệm. Ta có $6 \equiv-1(\bmod 7)$ suy ra $6^{5}-3 \cdot 6^{2}+2 \equiv-1-3+2 \equiv 5(\bmod 7)$ nên 6 không phải nghiệm. Vậy đồng dư thức (8) có hai nghiệm là 1 và 5 . Do đó các số nguyên $x$ thỏa mãn (8) đều có dạng $7 k+1$ hoặc $7 k+5$ với $k$ là số nguyên tùy ý.

2. Giải đồng dư thức

$$(9) \quad x^{2}+x \equiv 0(\bmod 2)$$

Ta chỉ cần kiểm tra xem (9) có đúng với 0 hoặc 1 hay không. Cả hai trường hợp đều thỏa mãn suy ra mọi số nguyên $x$ đều là nghiệm của $(9)$. Kết quả này cũng được suy ra từ tính chất $x^{2}$ và $x$ có cùng tính chẵn lẻ và do đó tổng của chúng luôn chẵn. Ta nói đồng dư thức đúng với mọi số nguyên.

Đây là một ví dụ cho thấy một đồng dư thức có thể luôn đúng cho dù các hệ số không phải bội số của modulo. Một ví dụ khác là đồng dư thức $x^{3}-x \equiv 0(\bmod 3)$. Thật vậy $x^{3}-x=(x-1) x(x-1)$ là tích của ba số nguyên liên tiếp nên trong đó có một số chia hết cho 3 và vì vậy tích của chúng chia hết cho 3 . Ta có $x^{3}-x \equiv 0(\bmod 3)$ với mọi số nguyên $x$.

Do (9) luôn đúng nên đồng dư thức $x^{2}+x+1 \equiv 0(\bmod 2)$ không có nghiệm. Tương tự đồng dư thức $x^{2} \equiv 3(\bmod 8)$ cũng không có nghiệm nguyên $x$ vì bình phương một số lẻ chia 8 dư 1 và bình phương một số chẵn chia 8 dư 0 hoặc 4.

Kí hiệu $m$ là modulo cho trước, $k$ là số tự nhiên cho trước $<m$ và $a_{1}, a_{2}, \ldots, a_{k}$ là các số nguyên không âm $<m$. Câu hỏi đặt ra là khi nào thì đồng dư thức $f(x) \equiv 0(\bmod m)(f(x)$ là đa thức hệ số nguyên) có tất cả các nghiệm là $a_{1}, a_{2}, \ldots, a_{k}$ (và các đồng dư của chúng modulo $m$).

Nếu $m$ là số nguyên tố thì rõ ràng hàm cần tìm là $f(x)=\left(x-a_{1}\right)\left(x-a_{2}\right) \ldots\left(x-a_{k}\right)$.

Nếu $m=4$ và $a_{1}, a_{2}, \ldots, a_{k}, k \leq 4$, là các số nguyên không âm cho trước $<4$ thì các nghiệm của đồng dư $\left(x-a_{1}\right)\left(x-a_{2}\right) \ldots\left(x-a_{k}\right) \equiv 0(\bmod 4)$ là các số $a_{1}, a_{2}, \ldots, a_{k}$ (và các đồng dư của chúng theo modulo 4). Tuy nhiên M.Chojnacka Pniewska đã chứng minh rằng không tồn tại đa thức $f(x)=a_{0} x^{n}+a_{1} x^{n-1}+\ldots+a_{n-1} x+a_{n}$ mà $f(x) \equiv 0(\bmod 6)$ thỏa mãn với 2 và 3 nhưng không thỏa mãn với mọi số nguyên $<6$ khác. Thật vậy, giả sử $f(x)$ có tính chất đó. Khi đó $f(2) \equiv f(3) \equiv 0(\bmod 6)$ suy ra $3 f(2)-3 f(3) \equiv 0(\bmod 6)$. Ta có $3 \cdot 2^{k} \equiv 2.3^{k} \equiv 0(\bmod 6)$ với mọi $k=1,2, \ldots$ nên $3 f(2) \equiv 3 a_{n}(\bmod 6)$ và $2 f(3) \equiv 2 a_{n}(\bmod 6)$. Do đó $3 f(2)-2 f(3) \equiv a_{n}(\bmod 6)$ suy ra $a_{n} \equiv 0(\bmod 6)$ nên $f(0) \equiv 0(\bmod 6)$. Ta đã chứng minh đồng dư thức $f(x) \equiv 0(\bmod 6)$ có nghiệm $x=0$, mâu thuẫn với giả thiết 2 và 3 là tất cả các nghiệm.

Có thể chứng minh rằng (Sierpinski) nếu $m$ là hợp số $\neq 4$ thì tồn tại hai số nguyên $a$ và $b$ không có cùng số dư khi chia cho $m$ và nếu $f(x)$ là đa thức hệ số nguyên thì đồng dư thức $f(a) \equiv f(b) \equiv 0(\bmod m)$ kéo theo đồng dư thức $f(0) \equiv 0(\bmod m)$. Từ đây suy ra nếu $m$ là hợp số $\neq 4$ thì tồn tại đa thức bậc hai $f(x)=x^{2}+a_{1} x+a_{2}$ với hệ số nguyên mà đồng dư thức $f(x) \equiv 0(\bmod m)$ có nhiều hơn hai nghiệm.

Đây là một tính huống khá giống nhau giữa lý thuyết các đồng dư thức và lý thuyết các phương trình Diophante tuyến tính một biến. Thật vậy, số nguyên $x$ thỏa mãn đồng dư thức (6) khi và chỉ khi tồn tại số nguyên $y$ thỏa mãn $f(x)=m y$. Vì vậy đồng dư thức $f(x) \equiv 0(\bmod m)$ tương đương với phương trình Diophante $f(x)-m y=0$.

Với những lập luận tương tự ta chứng minh được một đồng dư thức mà vế trái là một đa thức nhiều biến hệ số nguyên và vế phải là một số cho trước là giải được về lý thuyết. Chẳng hạn đối với đồng dư thức $f(x, y) \equiv 0(\bmod m)$ với $f(x)$ là đa thức với các biến $x, y$ thì chỉ cần tìm xem trong $m^{2}$ bộ số $x, y$ với $x$ và $y$ nhận mọi giá trị $0,1, \ldots, m-1$ thì bộ số nào thỏa mãn đồng dư thức đó. Các phép thử này có thể làm đon giản hơn dựa vào nhận xét nếu $a \equiv c(\bmod m)$ và $b \equiv d(\bmod m)$ thì $f(a, b) \equiv f(c, d)(\bmod m)$. Một ví dụ đơn giản là xét đồng dư thức $x^{4}+y^{4} \equiv 1(\bmod 5)$. Tất cả các nghiệm của phương trình này là $(x, y)=(0,1),(0,2)(0,3),(0,4),(1,0),(2,0),(3,0),(4,0)$. Vì vậy trong mọi nghiệm của nó có đúng một số chia hết cho 5 . Đồng dư thức $x^{3}+y^{3}+z^{3} \equiv 4(\bmod 9)$ vô nghiệm vì lập phương của một số nguyên thì đồng dư với $0,1,-1$ theo modulo 9 và do đó tổng của ba lập phương không thể đồng dư với 4.

Tài liệu tham khảo

1. Lý thuyết sơ cấp của các số - W. SIERPINSKI
2. cp-algorithms.com
3. Handbook Competitive Programming - Antti Laaksonen
4. Competitve programming 3 - Steven Halim, Felix Halim
5. Giải thuật và lập trình - Thầy Lê Minh Hoàng