Định Lý Số Dư Trung Hoa – Chinese Remainder Theorem

Điển tích Trung Quốc kể rằng ngày xưa danh tướng Hàn Tín có khả năng tính chính xác số binh lính của mình bằng cách: cho binh lính lần lượt xếp thành hàng 3, hàng 5, hàng 7, rồi lấy số binh lính dư ra ở mỗi cách xếp hàng để tính ra được số lính. Cụ thể, binh lính xếp hàng 3 thì dư 2 người, xếp hàng 5 thì dư 3, xếp hàng 7 thì dư 5. Ông liền tính ngay ra được binh lính có tổng cộng 68 người. Đây là bài toán Hàn Tín điểm binh.

Một điển tích khác nằm trong truyện Anh Hùng Xạ Điêu của Kim Dung, đoạn Hoàng Dung và Quách Tĩnh gặp Thần toán tử Anh Cô tại Đầm tối, lúc rời đi Hoàng Dung có ra 3 đề toán cho Anh Cô, và bảo rằng Anh Cô trong vòng nửa năm nhất định không giải ra được. Trong đó bài số 3 gọi là bài Quỷ Cốc Toán như sau: Có một số không biết là bao nhiêu, chia cho ba thì thừa hai, chia cho năm thì thừa ba, chia cho bảy thì thừa hai, hỏi là bao nhiêu?

Một cách tổng quát, ta có bài toán sau: Tìm số x sao cho:

X = a1 (mod m1)

X = a2 (mod m2)

...

X = ak (mod mk)

Đây là một bài toán về số học module mà có thể giải dễ dàng bằng định lý phần dư Trung Hoa (Chinese Remainder Theorem – CRT).

Điều kiện cho bài toán này là m1, m2, …,  mk đôi một nguyên tố cùng nhau. Để tìm x ta tính như sau:

M = m1 x m2 x ... x mk

M1 = M / m1

M2 = M / m2

...

Mk = M / mk

Sau đó tính:

y1 = (M1)-1 (mod m1)

y2 = (M2)-1 (mod m2)

...

yk = (Mk)-1 (mod mk)

Trong đó (Mk)-1 (mod mk) là module  nghịch đảo của Mk theo mod mk. Đó là số yk sao cho:

yk x Mk = 1 (mod mk)

Khi đó hệ sẽ có bộ nghiệm là:

X = a1 x M1 x y1 + ... + ak x Mk x yk + t.M

Với t ∈ Z.

Ví dụ trong bài toán Hàn Tín điểm binh. Ta có hệ pt đồng dư:

X = 2 (mod 3)

X = 3 (mod 5)

X = 5 (mod 7)

Ta có 3, 5, 7 đôi một nguyên tố cùng nhau. Tính:

M = 3 x 5 x 7 = 105

M1 = 105 / 3 = 35

M2 = 105 / 5 = 21

M3 = 105 / 7 = 15

Tìm yk với yk x Mk = 1 (mod mk). Ta có:

2 x 35 = 1 (mod 3) nên y1 = 2

1 x 21 = 1 (mod 5) nên y2 = 1

1 x 15 = 1 (mod 7) nên y3 = 1

Vậy nghiệm của hệ là:

X = 2x35x2 + 3x21x1 + 5x15x1 + 105t = 278 + 105t = 68 + 105h.

Tùy thuộc vào ước lượng khoảng của x mà chọn h. Trong trường hợp này,  chọn h = 0 thì X = 68.

Bài Quỷ Cốc toán xin dành cho độc giả giải.

Sourcecode Chinese Remainder Theorem

Chia sẻ:

• Twitter
• Facebook

Thích Đang tải...

Có liên quan