Định lý 7.1. Với $m$ là bội chung nhỏ nhất của $m_1$ và $m_2$. Điều kiện để các đồng dư đồng thời sau \[x\equiv a_1\pmod{m_1},\] \[x\equiv a_2\pmod{m_2},\]  có nghiệm là

\[\gcd\left( m_1,\,m_2\right)\mid a_1-a_2.\]

Nếu $(1)$ cố định, lúc đó nghiệm của $(1)$ là duy nhất mod $m$.

Chứng minh. Đặt $\gcd\left(m_1,\,m_2\right)=d$. Nếu hai đồng dư đồng thời đó có một nghiệm, lúc đó \[x\equiv a_1,\,x\equiv a_2\pmod d\] và ta có \[d\mid a_1-a_2.\] Nếu $d\mid a_1-a_2$, lúc đó nghiệm $x$ để $x\equiv a_1\pmod m_1$ được cho bởi $x=a_1+m_1y$. Thay vào đồng dư thức thứ hai có $a_1+m_1y\equiv a_2\pmod m_2$. Từ Định lý 6.1 đồng dư thức mod $\dfrac{m_2}{d}$ có duy nhất một nghiệm. Từ đó những đồng dư đồng thời mod $m$ này có duy nhất một nghiệm $x$.

Định lý 7.2. Nếu $\gcd\left(m_i,\,m_j\right)=1$ $(1\le i<j\le n)$, lúc đó những đồng đồng thời \[x\equiv a_i\pmod m_i,\,\quad1\le i\le n\] có duy nhất một nghiệm mod $m_1m_2\ldots m_n$.

Chứng minh. Ứng dụng phép quy nạp toán học từ Định lý 7.1

$\square$

Giờ ta sẽ bàn luận đến phương pháp cổ cho vấn đề tìm số thoả mãn $\S 1$. Lời giải của vấn đề này được viết vào năm 1593 dưới dạng một bài hát
như sau:

“Three people walking together, ’tis rare that one be seventy,
Five cherry blossoms trees, twenty one branches bring flowers,
Seven disciples reunite for the haft moon,
Take away (multiple of) one hundred and five and you shall know.”

Ta nhớ lại vấn đề để giải các đồng dư tương đương $x\equiv 2\pmod 3,\, x\equiv 3 \pmod 5,\, x\equiv 2 \pmod 7 $. Ý của bài thơ này được hiểu như sau gấp $70$ số dư của $x$ khi chia cho $3$ gấp $21$ số dư của $x$ khi chia $5$ gấp $15$ lần số dư của $x$ khi chia $7$ cộng ba kết quả lại cùng nhau, và lúc đó trừ đi một bội phù hợp của $105$ và bạn sẽ có nghiệm bé nhất cần tìm. Với ví dụ của ta , ta có \[2.70+3.21+2.15=233\] và trừ đi hai lần $105$ ta có nghiệm cần tìm đó là $23$.

Làm thế nào để giải thích được phương pháp tìm nghiệm cổ này và trong trường hợp đặc biệt $70,\,21,\,15$ ở đâu ra? Câu trả lời như sau: $70$ là bội của $5$ và $7$ và có số dư là $1$ khi chia $3$, $21$ là bội của $3$ và $7$ và có số dư là $1$ khi chia $5$, $15$ là bội của $3$ và $5$ và có số dư là $1$ khi chia $7$. Nó dẫn đến rằng $70a+21b+15c$ phải có số dư là $a,\,b,\,c$ khi chia các số tương ứng $3,\,5,\,7$

Trong đó nghiên cứu rộng hơn là làm thế nào họ tìm được các số $70,\,21,\,15$. Họ phải giải \[x\equiv 0\pmod m_1 ,\,\quad x\equiv 0\pmod m_2,\,\quad x\equiv 1\pmod m_3\] trong đó $m_1,\,m_2,\,m_3$ đôi một nguyên tố cùng nhau. Làm cách nào họ tìm được $x=m_1m_2y$ trong đó $y$ thoả $m_1m_2y\equiv 1\pmod m_3?$ câu trả lời là họ dùng thuật toán Euclidean phiên bản của riêng họ để giải phương trình bất định $m_1m_2y-m_3z=1$.\\

Các bài tập sau được lấy từ các bài toán cổ của trung quốc bài $2,\,3,\,4$ được viết vào năm 1257.

Bài tập 1. Thay $3,\,5,\,7$ bằng $3,\,7,\,11$ avf xác định ba số tương đương với $70,\,21,\,15$

Bài tập 2. Chia $7,\,8,\,9$ dư lần lượt $1,\,2,\,3$ đó là số nào?

Bài tập 3.  Chia $11$ dư $3$, $12$ dư $2$, $13$ dư $1$ đó là số nào?

Bài tập 4. Chia $7$ dư $3$, $5$ dư $2$, $2$ dư $1$ đó là số nào?

Bài tập 5. Số nào chia hết cho $5$, dư $10$ khi chia cho $715$, dư $140$ khi chia $247$, dư $245$ khi chia $391$, dư $109$ khi chia cho $187$?

[googlepdf url=”http://www.ebooks.mathscope.org/Google%20Drive/AMM/American%20Mathematical%20Monthly-AMM%20(1894%20%20-%201980)%20%20%5bCOMPLETE%5d/1974%20%5bCOMPLETE%5d/American%20Mathematical%20Monthly%20-%201974-09.pdf” download=”Download” width=”100%” height=”600″]