crt – T's Lab

Định lý (Định lý phần dư Trung Hoa). Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ thỏa mãn $(n_i,n_j)=1$ với mọi chỉ số khác nhau $i$ và $j$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm duy nhất modulo $\prod n_i$ với mỗi $r$ số nguyên $a_1$ , $a_2$ , $\ldots$ , $a_r$ .

Chúng tôi giới thiệu hai chứng minh của định lí này.

Chứng minh thứ nhất. Phần duy nhất là đơn giản, sau đây ta chứng minh phần tồn tại. Với mỗi $i$ , tồn tại số nguyên $k_i$ để

$\displaystyle x_i:=k_i\prod _{j\not =i}n_j\equiv 1\pmod{n_i}.$

Ta thấy $x=\sum a_ix_i$ là một nghiệm của hệ. $\blacksquare$

Chứng minh thứ hai. Đặt $N=\prod n_i$ . Dễ thấy ánh xạ

$\displaystyle x \pmod N\mapsto (x\pmod{n_1}, x\pmod{n_2}, \ldots, x\pmod{n_r})$

là một song ánh từ tập các lớp $\pmod N$ đến bộ các lớp $\pmod{n_i}$ . $\blacksquare$

Hệ quả. Cho các số nguyên dương $r$ ; $n_1$ , $n_2$ , $\ldots$ , $n_r$ và các số nguyên $a_1,$ $a_2,$ $\ldots,$ $a_r$ . Khi đó hệ phương trình đồng dư

$\displaystyle x\equiv a_1\pmod{n_1},x\equiv a_2\pmod{n_2},\ldots,x\equiv a_r\pmod{n_r}$

có nghiệm khi và chỉ khi $(n_i,n_j)\mid a_i-a_j$ với mọi cách chọn hai chỉ số phân biệt $i$ và $j$ .

Chứng minh. Điều kiện cần là hiển nhiên, ta chứng minh $(n_i,n_j)\mid a_i-a_j$ với mọi $i < j$ là điều kiện đủ để hệ có nghiệm.

Nếu $\prod n_i=1$ thì khẳng định đúng, nếu không, gọi $p_1,p_2,\ldots,p_k$ là các ước nguyên tố của $\prod n_i$ . Với mỗi $i$ , gọi $j(i)$ là chỉ số thỏa mãn