Định lý số dư Trung Quốc

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Định lý số dư Trung Quốc, hay bài toán Hàn Tín điểm binh, là một định lý nói về nghiệm của hệ phương trình đồng dư bậc nhất.

Lịch sử[sửa | sửa mã nguồn]

Định lý số dư Trung Quốc là tên người phương tây đặt cho định lý này. Người Trung Quốc gọi nó là bài toán Hàn Tín điểm binh. Hàn Tín là một danh tướng thời Hán Sở, từng được phong tước vương thời Hán Cao Tổ Lưu Bang đang dựng nghiệp. Sử ký Tư Mã Thiên viết rằng Hàn Tín là tướng trói gà không nổi, nhưng rất có tài quân sự. Tục truyền rằng khi Hàn Tín điểm quân số, ông cho quân lính xếp hàng 3, hàng 5, hàng 7 rồi báo cáo số dư. Từ đó ông tính chính xác quân số đến từng người.

Gần đây, định lý số dư Trung Quốc có nhiều ứng dụng trong các bài toán về số nguyên lớn áp dụng vào lý thuyết mật mã.

Nội dung[sửa | sửa mã nguồn]

Bản chất của bài toán Hàn Tín điểm binh là việc giải hệ phương trình đồng dư bậc nhất

 \begin{cases} x\equiv a_1 \pmod {m_1}\\x\equiv a_2 \pmod {m_2}\\..\\x\equiv a_k \pmod {m_k} \end{cases}

trong đó m_1,m_2,...,m_k đôi một nguyên tố cùng nhau. Trong bài toán Hàn Tín k=3m_1=3, m_2=5, m_3=7.

Định lý[sửa | sửa mã nguồn]

Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mođun
 M=m_1.m_2...m_k


x \equiv a_1.M_1.y_1+a_2.M_2.y_2+...+a_k.M_k.y_k \pmod M

trong đó

M_1=M/m_1,M_2=M/m_2,...,M_k=M/m_k
y_1=(M_1)^{-1}\pmod {m_1},  y_2=(M_2)^{-1}\pmod {m_2},..., y_k=(M_k)^{-1}\pmod {m_k}

Trong đó

(M_1)^{-1}\pmod {m_1} là nghịch đảo theo modulo của {m_1}

với 

y_1=(M_1)^{-1}\pmod {m_1}  <=> y_1M_1=1\pmod {m_1}

Ví dụ[sửa | sửa mã nguồn]

Giải hệ phương trình đồng dư

\begin{cases} x\equiv 2 \pmod 3\\x\equiv 3 \pmod 5\\x\equiv 5 \pmod 7 \end{cases}

ta có
M=3.5.7 = 105; M_1= 5.7 =35, M_2=3.7=21, M_3=3.5=15.
y_1=35^{-1}\pmod 3= 2^{-1}\pmod 3=2;
y_2=21^{-1}\pmod 5= 1^{-1}\pmod 5=1;
y_3=15^{-1}\pmod 7= 1^{-1}\pmod 7=1.
Từ đó
x\equiv 2.35.2+3.21.1+5.15.1\pmod {105}
x\equiv 140+63+75\pmod {105}\equiv 278 \pmod {105}
x\equiv 68\pmod {105}.
Như vậy x có dạng x = 68+k.105, k là số nguyên (hoặc số nguyên thích hợp nếu tìm nghiệm tự nhiên)

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]