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

thumb|Hướng sắp xếp ban đầu của Hàn Tín:
Định lý số dư Trung Hoa (Định lý thặng dư Trung Hoa), 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ử

Đị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: lấy số dư (khi chia) cho 3 nhân với 70, cộng số dư cho 5 nhân với 21, cộng số dư cho 7 nhân với 15, rồi cộng hoặc trừ một bội số của 105. Muốn cho dễ nhớ ông đặt thành thơ:

• Bản dịch 1 của Hoàng Xuân Hãn:

“Ba người cùng đi ít bảy chục

Năm cỗi mai hoa hăm mốt cành

Thất tử đoàn viên chính bán nguyệt

Trừ trăm linh năm biết số thành”

*Bản dịch 2 của Hoàng Xuân Hãn:

“Ba người cùng đi, ít bảy chục

Năm người cùng hàng, nhân hăm mốt

Bảy người cùng hàng, nhân mười lăm

Trừ trăm linh năm thì tính suốt”

• Bản dịch khác (chưa rõ tác giả)

“Ba người cùng đội bảy mươi rành

Năm khóm hoa mai, hăm mốt cành

Bảy gã vườn đào chơi nửa tháng

Cộng hoặc trừ trăm linh năm tính nhẩm nhanh”

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

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

$\backslash begin\{cases\}\; x\backslash equiv\; a\_1\; \backslash pmod\; \{m\_1\}\backslash \backslash x\backslash equiv\; a\_2\; \backslash pmod\; \{m\_2\}\backslash \backslash ..\backslash \backslash x\backslash equiv\; a\_k\; \backslash pmod\; \{m\_k\}\; \backslash 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=3$ và $m\_1=3,\; m\_2=5,\; m\_3=7$.

Định lý

:Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mô-đun

$M=m\_1\; \backslash cdot\; m\_2\; \backslash cdot\; \backslash \; ...\; \backslash \; \backslash cdot\; m\_k$ _là_
$x\; \backslash equiv\; a\_1\; \backslash cdot\; M\_1\; \backslash cdot\; y\_1+a\_2\; \backslash cdot\; M\_2\; \backslash cdot\; y\_2+...+a\_k\; \backslash cdot\; M\_k\; \backslash cdot\; y\_k\; \backslash pmod\; M$ _trong đó_ $M\_1=\backslash frac\{M\}\{m\_1\}\; ,\backslash \; M\_2=\backslash frac\{M\}\{m\_2\}\; ,\backslash \; ...,\backslash \; M\_k=\backslash frac\{M\}\{m\_k\}$
$y\_1\backslash equiv(M\_1)^\{-1\}\backslash pmod\; \{m\_1\},\backslash \; y\_2\backslash equiv(M\_2)^\{-1\}\backslash pmod\; \{m\_2\},\backslash \; ...,\backslash \; y\_k\backslash equiv(M\_k)^\{-1\}\backslash pmod\; \{m\_k\}$ :_Trong đó _ $(M\_1)^\{-1\}\backslash pmod\; \{m\_1\}$ _là nghịch đảo theo mô-đun của _$\{m\_1\}$ với $y\_1\backslash equiv(M\_1)^\{-1\}\backslash pmod\; \{m\_1\}\; \backslash Leftrightarrow\; y\_1M\_1\backslash equiv1\backslash pmod\; \{m\_1\}$

Ví dụ

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

$\backslash begin\{cases\}\; x\backslash equiv\; 2\; \backslash pmod\; 3\backslash \backslash x\backslash equiv\; 3\; \backslash pmod\; 5\backslash \backslash x\backslash equiv\; 5\; \backslash pmod\; 7\; \backslash end\{cases\}$ ta có
$M=3\backslash cdot5\backslash cdot7\; =\; 105;\; M\_1=\; 5\backslash cdot7\; =35,\; M\_2=3\backslash cdot7=21,\; M\_3=3\backslash cdot5=15$.
$y\_1=35^\{-1\}\backslash pmod\; 3=\; 2^\{-1\}\backslash pmod\; 3=2$;
$y\_2=21^\{-1\}\backslash pmod\; 5=\; 1^\{-1\}\backslash pmod\; 5=1$;
$y\_3=15^\{-1\}\backslash pmod\; 7=\; 1^\{-1\}\backslash pmod\; 7=1$.
Từ đó
$x\backslash equiv\; 2\backslash cdot35\backslash cdot2+3\backslash cdot21\backslash cdot1+5\backslash cdot15\backslash cdot1\backslash pmod\; \{105\}$
$x\backslash equiv\; 140+63+75\backslash pmod\; \{105\}\backslash equiv\; 278\; \backslash pmod\; \{105\}$
$x\backslash equiv\; 68\backslash pmod\; \{105\}$.
Như vậy x có dạng $x\; =\; 68+k\backslash cdot105$, k là số nguyên (hoặc số tự nhiên thích hợp nếu tìm nghiệm tự nhiên).