Phương trình đồng dư
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (738.98 KB, 2 trang )
Định lý số dư Trung Quốc
Bách khoa toàn thư mở Wikipedia
Đị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ử
Đị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
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
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 mođun
M = m
1
.m
2
...m
k
là
trong đó
M
1
= M / m
1
,M
2
= M / m
2
,...,M
k
= 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
)
Ví dụ
Giải hệ phương trình đồng dư
Mục lục
1 Lịch sử
2 Nội dung
2.1 Định lý
2.2 Ví dụ
3 Liên kết ngoài
Page 1 of 2Định lý số dư Trung Quốc – Wikipedia tiếng Việt
7/15/2010 />
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
(mod 3) = 2
− 1
(mod 3) = 2;
y
2
= 21
− 1
(mod 5) = 1
− 1
(mod 5) = 1;
y
3
= 15
− 1
(mod 7) = 1
− 1
(mod 7) = 1.
Từ đó
.
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)
Liên kết ngoài
Bổ sung cách giải bài toán "Hàn Tín điểm binh"
Lấy từ “
Thể loại: Số học | Định lý toán học
Trang này được sửa đổi lần cuối lúc 06:33, ngày 25 tháng 6 năm 2010.
Văn bản được phát hành theo Giấy phép Creative Commons Ghi công/Chia sẻ tương tự; có thể áp dụng điều khoản bổ sung. Xem Điều khoản Sử dụng để biết thêm chi tiết.
Wikipedia® là thương hiệu đã đăng ký của Wikimedia Foundation, Inc., một tổ chức phi lợi nhuận.
Quy định quyền riêng tư
Giới thiệu Wikipedia
Lời phủ nhận
Page 2 of 2Định lý số dư Trung Quốc – Wikipedia tiếng Việt
7/15/2010 />
