Bài viết trình bày về định lý thặng dư Trung Hoa là tên người phương Tây đặt thêm, người Trung Quốc gọi nó là bài toán “Hàn Tín điểm binh”. Bản chất của bài toán Hàn Tín điểm binh đấy là việc giải hệ phương trình đồng dư bậc nhất. Vận dụng tư tưởng của định lý thặng dư Trung Hoa, chúng ta có thể xây dựng một phương pháp hiệu quả nhất trong việc giải hệ phương trình đồng dư tuyến tính. Mời các bạn cùng tham khảo! | Hội thảo khoa học Hưng Yên 25-26 02 2017 ĐỊNH LÝ THẶNG DƯ TRUNG HOA VÀ MỘT SỐ ỨNG DỤNG Nguyễn Duy Liên THPT Chuyên Vĩnh Phúc 1 Mở đầu Định lý thặng dư Trung Hoa là tên người phương Tây đặt thêm 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 về quân sự tục kể 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ư mỗi hàng từ đó ông tính chính xác quân số đến từng người. Cách điểm quân số đã được ông thể hiện qua bài thơ sau Tam nhân đồng hành thất thập hy. Ngũ thụ mai hoa trấp nhất chi Thất tử đoàn viên chính bán nguyệt Trừ bách linh ngũ tiện đắc chi. Dịch. Ba người cùng đi ít bảy chục Năm cỗ mai hoa hăm mốt cành Bảy gã xum vầy vừa nửa tháng Trừ trăm linh năm biết số thành Người dịch Trình Đại Vỹ đời nhà Minh . Bản chất của bài toán Hàn Tín điểm binh đấy là việc giải hệ phương trình đồng dư bậc nhất x a1 mod m1 x a mod m 2 2 . x ak mod mk Trong đó m1 m2 . . . mk là các số nguyên dương đôi một nguyên tố cùng nhau với bài toán của Hàn Tín thì k 3 m1 3 m2 5 m3 7. 55 Hội thảo khoa học Hưng Yên 25-26 02 2017 Định lý 1 Định lý Thặng dư Trung Hoa . Cho ksố nguyên dương đôi một nguyên tố cùng nhau m1 m2 . . . mk và a1 a2 . . . ak là ksố nguyên tùy ý khi đó hệ phương trình đồng dư tuyến tính. x a1 mod m1 x a2 mod m2 . x ak mod mk có nghiệm duy nhất mô đun m1 m2 . . . mk Chứng minh định lý. 1. Chứng minh sự duy nhất Giả sử hệ có hai nghiệm x y dẫn đến x y mod mi i 1 k. Vì m1 m2 . . . mk đôi một nguyên tố cùng nhau nên x y mod m1 m2 . . . mk .Tức là y và x cùng thuộc một lớp thặng dư m1 m2 . . . mk . 2. Chứng minh sự tồn tại Ta muốn viết các nghiệm như là một tổ hợp tuyến tính của các số a1 a2 . . . ak .Chẳng hạn x A1 a1 A2 a2 A k a k Với các Ai phải tìm thỏa mãn A j 0 mod mi j 6 i và Ai 1 mod mi . Đặt N1 m2 m3 . . . mk N2 m1 m3 . . . mk . . . Ni
