Nguyễn Đức Kiên - Trường Đại học Công nghệ - ĐHQGHN
Reviewer:
Nguyễn Minh Nhật - THPT chuyên Khoa học Tự nhiên, ĐHQGHN
Nguyễn Minh Hiển - Trường Đại học Công nghệ - ĐHQGHN
Lớp bài toán liên quan đến số học là một lớp bài toán thường hay xuất hiện trong các kỳ thi học sinh giỏi môn Tin học. Để giải quyết hiệu quả những bài tập này, cần phải nắm vững những kiến thức toán học có liên quan. Bài viết sau đây sẽ cung cấp một số thông tin cơ bản nhất về modulo.
Dưới đây là một số khái niệm cơ bản liên quan đến phép chia
Phép chia: Với hai số nguyên a và b với b=0, tồn tại duy nhất một số nguyên q và một số tự nhiên r sao cho a=bq+r với 0≤r<∣b∣. Khi đó ta viết: a:b=q (dư r) Trong phép toán trên:
a là số bị chia
b là số chia
q là thương
r là số dư
Phép lấy số dư: Nếu phép chia a cho b có số dư là r, ta có thể viết amodb=r
Phép chia hết: Nếu r=0, ta có phép chia hết. Khi đó:
a chia hết cho b hoặc a là bội của b (a⋮b)
b chia hết a hoặc b là ước của a (b∣a)
Ước chung lớn nhất (gcd(a,b) hoặc (a,b)): Số nguyên d lớn nhất thoả mãn d∣a và d∣b gọi là ước chung lớn nhất của a và b. Bạn đọc có thể tham khảo bài Thuật toán Euclid để biết thêm tính chất của ước chung lớn nhất.
Bội chung nhỏ nhất (lcm(a,b) hoặc [a,b]): Số nguyên dương m nhỏ nhất thoả mãn a∣m và b∣m
Trong ngôn ngữ C++, phép chia được biểu diễn bằng toán tử /, còn phép lấy dư được biểu diễn bởi toán tử %. Nếu hai toán hạng trong phép tính đều ở kiểu dữ liệu int, kết quả cũng sẽ là kết quả int, do đó a / b là phép lấy thương (hay phần nguyên) của phép chia a cho b, còn a % b là phép lấy phần dư.
Số học modulo hiện đại được nghiên cứu lần đầu bởi C.Gauss năm 1801. Hiện tượng đồng dư cũng thường xuất hiện trong đời sống, chẳng hạn trên chiếc đồng hồ, 15 giờ và 3 giờ cùng được biểu diễn bởi một vị trí kim giờ/phút.
Cho số nguyên m≥1. Nếu có hai số nguyên a,b thoả mãn: m∣(a−b) thì ta nói a và b đồng dư theo modulo m. Ký hiệu là a≡b(modm).
Nói cách khác, nếu amodm=bmodm thì a≡b(modm).
Trong ví dụ về đồng hồ nói trên, ta có 3≡15(mod12).
Cộng hoặc trừ theo vế các đồng dư thức cùng modullo:
∀i∈1..n,ai≡bi(modm)⇒i=1∑nai≡i=1∑nbi(modm)
Cộng hoặc trừ cả hai vế của đồng dư thức với một hằng số:
a≡b(modm)⇒a±c≡b±c(modm)
Nhân theo vế các đồng dư thức cùng modullo:
∀i∈1..n,ai≡bi(modm)⇒i=1∏nai≡i=1∏nbi(modm)
Nhân cả hai vế của đồng dư thức với một số nguyên:
a≡b(modm)⇒ca≡cb(modm)
Nếu c là số nguyên dương ta còn có:
a≡b(modm)⇒ca≡cb(modcm)
Nâng cả hai vế lên luỹ thừa với số mũ tự nhiên:
a≡b(modm)⇒an≡bn(modm)
Chia cả hai vế cho một số nguyên tố cùng nhau với modulo:
⎩⎨⎧a≡b(modm)d∣ad∣b(m,d)=1⇒da≡db(modm)
Chia cả hai vế và modulo cho một số:
a≡b(modm)⇒da≡db(moddm)
Lấy bội chung nhỏ nhất các modulo:
∀i∈1..n,a≡b(modmi)⇒a≡b(mod[m1,m2,...,mn])
Về mặt cài đặt, đồng dư thức không có nhiều ý nghĩa thiết thực, tuy nhiên nó có vai trò quan trọng trong việc xây dựng lời giải và là nền tảng cho các định lý tiếp sau đây.
Số dư của một phép chia tất nhiên sẽ đồng dư với số bị chia theo modulo là số chia. Vì vậy, mọi tính chất của đồng dư thức đều áp dụng được cho phép toán lấy số dư:
(a+b)modM=(amodM+bmodM)modM
(a×b)modM=((amodM)×(bmodM))modM
Khi tính hiệu modulo, sẽ xảy ra tình trạng a−b<0. Để khắc phục, ta cộng thêm một lần M vào kết quả để chắc chắn có một số dương (tất nhiên sau đó vẫn lấy mod M):
(a−b)modM=(amodM−bmodM+M)modM
Với phép luỹ thừa, ta sử dụng luỹ thừa nhị phân thông qua các phép nhân modulo để tính.
Một vấn đề thường gặp phải khi tính toán các bài có modulo là hiện tượng tràn số. Với M≈109, dễ thấy khi a,b≤109 thì a×b có thể vượt quá giới hạn của int. Vấn đề này có thể được giải quyết một cách đơn giản bằng cách dùng long long; tuy nhiên nếu vẫn muốn sử dụng int để tiết kiệm bộ nhớ, ta có thể sử dụng:
int ans = 1ll * a * b % M
Ngoài ra, ta có thể ép kiểu để a trở thành long long bằng cách dùng (long long)a, miễn sao phần tử đầu tiên của phép tính là một số kiểu long long.
Nhìn chung, nên cố gắng thêm % MOD và 1ll * vào mọi phép tính để tránh những sai lầm đáng tiếc.
Bài toán: Tính bamodM với a,b,M là các số nguyên dương và b∣a.
Khác với phép cộng, trừ và nhân, dễ thấy không thể có a≡b(modm)⇒ca≡cb(modm)) với mọi a,b nguyên. Chẳng hạn, 16≡1(mod5), nhưng đương nhiên không có 216≡21(mod5).
Để giải quyết bài toán này, chúng ta cần một hướng tiếp cận khác. Trong nhiều trường hợp, M sẽ là một số nguyên tố, khi đó ta có thể sử dụng phép nghịch đảo modulo để tính kết quả của phép chia.
Nghịch đảo modulo: Số tự nhiên γ được gọi là nghịch đảo modulo theo modulo m của một số tự nhiên a nếu aγ≡1(mod m). Ký hiệu là a−1(modm).
Ví dụ: 3≡7−1(mod10)
Nghịch đảo modulo m của số tự nhiên a chỉ tồn tại nếu (a,m)=1.
Ta có thể dùng nghịch đảo modulo để tính kết quả của phép chia modulo như sau:
bamodM=ab−1modM
Một cách làm phổ biến để tính nghịch đảo modulo là áp dụng định lý Euler (hoặc định lý Fermat nhỏ), sẽ được trình bày ở dưới đây.
Hàm phi Euler: Đây là khái niệm cốt lõi của định lý Euler.
Hàm phi Euler của số tự nhiên x, ký hiệu ϕ(x), là số lượng số tự nhiên nhỏ hơn hoặc bằng x mà nguyên tố cùng nhau với x
ϕ(x)=∣{k∈N∗,k≤x∣(x,k)=1}∣
Nếu N phân tích được thành thừa số nguyên tố dưới dạng N=p1α1p2α2...pmαm thì ta có thể tính ϕ(N) như sau:
ϕ(N)=Ni=1∏m(1−pi1)
Định lý Euler: Nếu a và m là các số tự nhiên thoả mãn (a,m)=1 thì ta có aϕ(m)≡1(modm)
Định lý Fermat nhỏ: Với p là số nguyên tố bất kỳ và n là số tự nhiên bất kỳ thoả mãn (n,p)=1, ta có np−1≡1(modp). Đây là trường hợp đặc biệt của định lý Euler đối với số nguyên tố, khi đó ϕ(p)=p−1.
Tính nghịch đảo modulo: Để tính nghịch đảo modulo x−1(modM) khi M là số nguyên tố, ta áp dụng định lý Fermat nhỏ. Do M là số nguyên tố, xM−1≡1(modM). Do (x,M)=1, chia cả hai vế của đồng dư thức trên cho x ta được:
x−1≡xM−2(modM)
Như vậy, xM−2 là nghịch đảo modulo M của x. Theo cách này, ta mất O(logM) thời gian để tìm một nghịch đảo modulo bằng phương pháp luỹ thừa nhị phân.
//Luỹ thừa nhị phân
int binPow(int x, int y, int mod) {
int ret = 0;
for (; y; y /= 2, x = 1ll * x * x % mod) {
if (y % 2) ret = 1ll * ret * x % mod;
}
return ret;
}
//Nghịch đảo modulo
int inv(int x, int mod) {
return binPow(x, mod - 2, mod);
}
//Phép chia modulo
int divMod(int a, int b, int mod) {
return 1ll * a * inv(b) % mod;
}
Chú ý: Kết quả của bamodM theo công thức trên vẫn đúng nếu ta thay b−1(modM) bằng (bmodM)−1(modM). Do vậy, ta có thể thực hiện modulo M trước khi áp dụng công thức mà không sợ ảnh hưởng đến kết quả.
Trường hợp (b,M)=1: Trong trường hợp M không phải là số nguyên tố, nếu đã biết (b,M)=1 ta vẫn có thể tính nghịch đảo modulo bằng cách áp dụng thuật toán Euclid mở rộng để giải phương trình Diophantus ax+My=1. Nghiệm x của phương trình trên chính là nghịch đảo modulo M của a.
Trường hợp (b,M)=1: Nghịch đảo modulo chỉ tồn tại nếu (b,M)=1, do vậy ta cần dùng một cách khác. Lúc này ta có thể sử dụng công thức:
bamodM=bamod(b×M)
Chứng minh
Giả sử a≡r(modb×M). Khi đó (a−r)⋮(b×M), mà a⋮b nên r⋮b. Chia hai vế của đồng dư thức và modulo cho b ta được:
ba≡br(modM)
Nếu ta chọn 0≤r<b×M thì 0≤br<M. Khi đó r là số dư trong phép chia a cho b×m, còn br là số dư trong phép chia ba cho m. Vậy:
bamodM=br=bamod(b×M)
//Vẫn là phép chia modulo
int divMod(int a, int b, int mod) {
return a % (1ll * b * mod) / b;
}
Một số lưu ý khi sử dụng công thức trên:
Công thức ở trên vẫn có thể áp dụng được khi M là một số nguyên tố, hoặc (b,M)=1. Điều kiện duy nhất cần được thoả mãn là b∣a.
Công thức này cho kết quả hoàn toàn khác nếu thay b ở vế phải thành bmodM. Chẳng hạn, (64:8)mod5=(64mod40):5 nhưng không bằng (64mod15):5. Điều này có nghĩa là bạn không thể áp dụng công thức với số chia đã bị modulo mà chỉ dùng được nếu số chia vẫn được giữ như ban đầu.
Việc áp dụng công thức này tiềm ẩn nguy cơ tràn số qua cả long long nếu M là một số rất lớn, do xuất hiện phép nhân b×M.
Thuật toán Euclid mở rộng dùng để tìm các bộ số nguyên x,y sao cho ax+by=(a,b), với a,b là các số nguyên. Áp dụng thuật toán này, ta có thể giải các phương trình Diophantus tuyến tính hai ẩn có dạng ax+by=c (hay ax≡c(modb)), với a,b,c là các số nguyên.
Bạn đọc có thể tham khảo chi tiết về thuật toán Euclid mở rộng tại bài viết này.
Định lý: Cho 2n số nguyên dương a1,a2,...,an và m1,m2,...,mn sao cho các số m1,m2,...,mm nguyên tố cùng nhau đôi một. Hệ phương trình đồng dư (hoặc thặng dư) ẩn x:
⎩⎨⎧x≡a1(modm1)x≡a2(modm2)...x≡an(modmn)
có họ nghiệm duy nhất là:
x≡i=1∑npipi−1ai(modM)
trong đó M=i=1∏nmi, pi=miM và pi−1 là nghịch đảo modulo mi của pi.
Chứng minh
Chứng minh sự tồn tại: Do m1,m2,..,mn là các số đôi một nguyên tố cùng nhau nên dễ thấy (pi,mi)=1, dẫn đến sự tồn tại của pi−1(modmi). Vì pipi−1≡1(modmi) nên
pipi−1ai≡ai(modmi)
Xét x=i=1∑npipi−1ai. Ta thấy với mọi i=j thì mi∣pj do pj là tích của tất cả các mi′ với i′ khác j. Vì vậy với mọi i ta có
x≡ai(modmi)
Vậy x là một nghiệm của hệ phương trình.
Chứng minh sự duy nhất: Giả sử phương trình có hai nghiệm là x và y. Với mọi i, ta đều có x≡y≡ai(modmi). Lấy bội chung nhỏ nhất của tất cả các đồng dư thức dạng trên ta được
x≡y(mod[m1,m2,...,mn])
Do (m1,m2,...,mn)=1 nên
x≡y(modi=1∏nmi)
hay x≡y(modM). Nghĩa là, nghiệm theo modulo M là duy nhất.
Rất nhiều bài toán đố vui hay dân gian dẫn đến việc phải giải hệ phương trình đồng dư và dẫn đến định lý này, chẳng hạn có bài Hàn Tín điểm binh nổi tiếng. Còn trong lập trình thi đấu, ta không thường xuyên gặp những bài toán với yêu cầu rõ ràng như vậy. Tuy nhiên, định lý này và các kết quả trung gian sử dụng để chứng minh định lý lại là nền tảng để giải rất nhiều bài toán số học, như những bài có tag chinese remainder theorem trên Codeforces.
Định lý thặng dư Trung Hoa cho phép ta nhanh chóng giải một hệ phương trình đồng dư với các modulo đôi một nguyên tố cùng nhau. Chỉ cần tính các pi=miM và pi−1, ta dễ dàng giải được hệ phương trình đồng dư.
Đôi khi, ta gặp phải các bài toán mà trong đó các modulo không nguyên tố cùng nhau với nhau. Trong trường hợp này, ta xét từng cặp phương trình một. Giả sử ta có hệ
{x≡a1(modm1)x≡a2(modm2)
Từ hệ này, ta có thể đặt x=m1y+a1=m2z+a2 và giải phương trình Diophantus tuyến tính sau bằng thuật toán Euclid mở rộng
m1y−m2z=a2−a1
Khi đã tìm được y và z, ta tính x∗=m1y+a1 hoặc m2z+a2. Nghiệm của hệ sẽ là