Định Lý Số Dư Trung Quốc – Wikipedia Tiếng Việt

Bước tới nội dung

Nội dung

chuyển sang thanh bên ẩn

• Đầu
• 1 Lịch sử
• 2 Nội dung Hiện/ẩn mục Nội dung
  • 2.1 Định lý
  • 2.2 Ví dụ
• 3 Tham khảo
• 4 Liên kết ngoài

• Bài viết
• Thảo luận

Tiếng Việt

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Công cụ Công cụ chuyển sang thanh bên ẩn Tác vụ

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Chung

• Các liên kết đến đây
• Thay đổi liên quan
• Trang đặc biệt
• Liên kết thường trực
• Thông tin trang
• Trích dẫn trang này
• Lấy URL ngắn gọn
• Tải mã QR

In và xuất

• Tạo một quyển sách
• Tải dưới dạng PDF
• Bản để in ra

Tại dự án khác

• Khoản mục Wikidata

Giao diện chuyển sang thanh bên ẩn Bách khoa toàn thư mở Wikipedia

Đị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ử

[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: 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ơ[1]:

“	Tam nhân đồng hành thất thập suy Ngũ thụ mai hoa chấp nhất chi Thất nhân đồng hành thu bán nguyệt Trừ bách trừ ngũ định vi kỳ	”
— Hàn Tín, Điểm binh pháp

• 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

[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

{ x ≡ a 1 ( mod m 1 ) x ≡ a 2 ( mod m 2 ) . . x ≡ a k ( mod m k ) {\displaystyle {\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 {\displaystyle 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 {\displaystyle k=3} và m 1 = 3 , m 2 = 5 , m 3 = 7 {\displaystyle m_{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 mô-đun M = m 1 ⋅ m 2 ⋅   . . .   ⋅ m k {\displaystyle M=m_{1}\cdot m_{2}\cdot \ ...\ \cdot m_{k}}

là

x ≡ a 1 ⋅ M 1 ⋅ y 1 + a 2 ⋅ M 2 ⋅ y 2 + . . . + a k ⋅ M k ⋅ y k ( mod M ) {\displaystyle x\equiv a_{1}\cdot M_{1}\cdot y_{1}+a_{2}\cdot M_{2}\cdot y_{2}+...+a_{k}\cdot M_{k}\cdot y_{k}{\pmod {M}}}

trong đó

M 1 = M m 1 ,   M 2 = M m 2 ,   . . . ,   M k = M m k {\displaystyle M_{1}={\frac {M}{m_{1}}},\ M_{2}={\frac {M}{m_{2}}},\ ...,\ M_{k}={\frac {M}{m_{k}}}} y 1 ≡ ( M 1 ) − 1 ( mod m 1 ) ,   y 2 ≡ ( M 2 ) − 1 ( mod m 2 ) ,   . . . ,   y k ≡ ( M k ) − 1 ( mod m k ) {\displaystyle y_{1}\equiv (M_{1})^{-1}{\pmod {m_{1}}},\ y_{2}\equiv (M_{2})^{-1}{\pmod {m_{2}}},\ ...,\ y_{k}\equiv (M_{k})^{-1}{\pmod {m_{k}}}}

Trong đó

( M 1 ) − 1 ( mod m 1 ) {\displaystyle (M_{1})^{-1}{\pmod {m_{1}}}} là nghịch đảo theo mô-đun của m 1 {\displaystyle {m_{1}}} với y 1 ≡ ( M 1 ) − 1 ( mod m 1 ) ⇔ y 1 M 1 ≡ 1 ( mod m 1 ) {\displaystyle y_{1}\equiv (M_{1})^{-1}{\pmod {m_{1}}}\Leftrightarrow y_{1}M_{1}\equiv 1{\pmod {m_{1}}}}

Ví dụ

[sửa | sửa mã nguồn]

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

{ x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 5 ( mod 7 ) {\displaystyle {\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 {\displaystyle M=3\cdot 5\cdot 7=105;M_{1}=5\cdot 7=35,M_{2}=3\cdot 7=21,M_{3}=3\cdot 5=15} . y 1 = 35 − 1 ( mod 3 ) = 2 − 1 ( mod 3 ) = 2 {\displaystyle y_{1}=35^{-1}{\pmod {3}}=2^{-1}{\pmod {3}}=2} ; y 2 = 21 − 1 ( mod 5 ) = 1 − 1 ( mod 5 ) = 1 {\displaystyle y_{2}=21^{-1}{\pmod {5}}=1^{-1}{\pmod {5}}=1} ; y 3 = 15 − 1 ( mod 7 ) = 1 − 1 ( mod 7 ) = 1 {\displaystyle y_{3}=15^{-1}{\pmod {7}}=1^{-1}{\pmod {7}}=1} . Từ đó x ≡ 2 ⋅ 35 ⋅ 2 + 3 ⋅ 21 ⋅ 1 + 5 ⋅ 15 ⋅ 1 ( mod 105 ) {\displaystyle x\equiv 2\cdot 35\cdot 2+3\cdot 21\cdot 1+5\cdot 15\cdot 1{\pmod {105}}} x ≡ 140 + 63 + 75 ( mod 105 ) ≡ 278 ( mod 105 ) {\displaystyle x\equiv 140+63+75{\pmod {105}}\equiv 278{\pmod {105}}} x ≡ 68 ( mod 105 ) {\displaystyle x\equiv 68{\pmod {105}}} . Như vậy x có dạng x = 68 + k ⋅ 105 {\displaystyle x=68+k\cdot 105} , k là số nguyên (hoặc số tự nhiên thích hợp nếu tìm nghiệm tự nhiên).

Tham khảo

[sửa | sửa mã nguồn]

1. ^ “Tạp chí Pi”. pi.edu.vn. Truy cập ngày 20 tháng 4 năm 2022.

Liên kết ngoài

[sửa | sửa mã nguồn] Lấy từ “https://vi.wikipedia.org/w/index.php?title=Định_lý_số_dư_Trung_Quốc&oldid=71449727” Thể loại:

• Số học
• Định lý toán học
• Toán học Trung Quốc
• Số học Modulo

Thể loại ẩn:

• Bài viết sử dụng pull quote có nguồn