Giáo trình Số học thuật toán - Chương 1: Thuật toán

ố nguyên d−ơng nguyên tố cùng nhau từng cặp. Khi đó hệ 
đồng d−: 
x1≡ a1(mod m1), 
x2≡ a2(mod m2), 
 15
... ... ... 
xr≡ ar(mod mr). 
Có nghiệm duy nhất modulo M=m1m2...mr. 
Chứng minh. Tr−ớc hết ta xây dựng một nghiệm của hệ. 
Giả sử Mk=M/mk= m1m2...mk-1mk+1...mr. Ta biết rằng (Mk,mk)=1 vì (mj,mk)=1 với mọi 
j≠ k. Nh− vậy, theo bài tập 2.18 ta có thể tìm một nghịch đảo yk của Mk modulo mk, 
tức là Mkyk ≡ 1 (mod mk). 
 Đặt 
x=a1M1y1+ a2M2y2 +...+ arMryr . 
Ta thấy rằng x≡ ak(mod mk) với mọi k vì mk |Mj với j≠ k nên Mj≡ 0 (mod mk) khi j≠ k. 
Nh− vậy, x chính là một nghiệm của hệ đang xét. 
Ta chứng tỏ rằng nghiệm vừa xây dựng là duy nhất modulo M. Giả sử x0, x1 là hai 
nghiệm của hệ. Khi đó, với mỗi k, x0≡ x1≡ ak (mod mk), cho nên mk | (x0-x1). Theo bài 
tập 2.17, M | (x0-x1). Định lí đ−ợc chứng minh. 
Định lí Trung Quốc về phần d− liên quan bài toán nổi tiếng “Hàn Tín điểm binh”. 
T−ơng truyền rằng, để kiểm tra quân số, Hàn Tín th−ờng ra lệnh cho quân sĩ xếp 
thành hàng 3, hàng 5, hàng 7 và thông báo cho ông các số d−. Khi biết các số d− và 
đã có sẵn thông tin gần đúng về số quân của mình, Hàn Tín dùng định lí trên đây để 
suy ra số quân chính xác. 
Định lí Trung Quốc về phần d− đ−ợc sử dụng trong máy tính để làm việc với những 
số lớn. Để đ−a một số nguyên lớn tuỳ ý vào máy tính và làm các phép tính số học với 
chúng, ta cần có những kĩ thuật đặc biệt. Theo định lí Trung quốc về phần d−, khi 
cho tr−ớc các modun nguyên tố cùng nhau m1,m2,...,mr, một số d−ơng n<M= 
m1m2...mr đ−ợc xác định duy nhất bởi các thặng d− d−ơng bé nhất của nó theo 
modulo mj với j=1,2,...,r. Giả sử rằng cỡ từ của máy chỉ là 100, nh−ng ta cần làm các 
phép tính số học với những số nguyên cỡ 106. Tr−ớc tiên ta tìm các số nguyên nhỏ 
hơn 100, nguyên tố cùng nhau từng cặp, sao cho tích của chúng v−ợt quá 106. Chẳng 
hạn, ta có thể lấy m1=99, m2=98, m3=97, m4=95. Ta chuyển các số nguyên bé hơn 10
6 
thành những bộ 4 số theo thặng d− d−ơng bé nhất modulo m1,m2,m3,m4 (để làm đ−ợc 
điều này, ta cũng phải làm việc với những số nguyên lớn! Tuy nhiên điều đó chỉ cần 
làm một lần với input, và một lần nữa với ouput). Nh− vậy, chẳng hạn để cộng các số 
nguyên, ta chỉ cần cộng các thặng d− d−ơng bé nhất của chúng modulo m1,m2,m3,m4. 
Sau đó lại dùng định lí Trung Quốc về phần d− để tìm bộ 4 số t−ơng ứng với tổng. 
Ví dụ. Ta muốn tính tổng x=123684, y=413456 với một máy tính cỡ từ là 100. Ta có: 
x≡ 33(mod 99), 8(mod 98), 9(mod 97), 89(mod 95) 
y≡ 32(mod 99), 92(mod 98), 42(mod 97), 16(mod 95) 
Nh− vậy, 
x+y≡ 65(mod 99), 2(mod 98), 51(mod 97), 10(mod 95) 
 16
Bây giời ta dùng định lí Trung Quốc về phần d− để tìm x+y modulo 
M=99.98.97.95=89403930. Ta có: M1=M/99=903070, M2=M/98=912288, 
M3=M/97=921690, M4=M/95=941094. Ta cần tìm ng−ợc của Mi(mod yi) với 
i=1,2,3,4, tức là giải hệ ph−ơng trình đồng d− sau đây (Bằng thuật chia Euclid): 
903070y1≡ 91y1≡ 1(mod 99) 
912285y2≡ 3y2≡ 1(mod 98) 
921690y3≡ 93y3≡ 1(mod 97) 
Ta tìm đ−ợc: y1≡ 37(mod 99), y2≡ 38(mod 98), y3≡ 24(mod 97), y4≡ 4(mod 95). 
Nh− vậy, 
x+y=65.903070.37+2.912285.33+51.921690.24+10.941094.4=3397886480 
 ≡ 537140(mod 89403930) 
Vì 0<x+y<89403930, ta suy ra x+y=537140. 
Rất có thể độc giả cho rằng, cách cộng hai số sử dụng định lí Trung Quốc về phần d− 
quá phức tạp so với cách cộng thông th−ờng. Tuy nhiên, cần chú ý rằng, trong ví dụ 
trên đây, ta làm việc với các số nhỏ. Khi các số cần cộng có độ lớn v−ợt xa cỡ từ của 
máy, các quy tắc cộng “thông th−ờng” không còn áp dụng đ−ợc nữa. 
Nói chung cỡ từ của máy tính là luỹ thừa rất lớn của 2, chẳng hạn 235. Nh− vậy, để sử 
dụng định lí Trung Quốc về phần d−, ta cần các số nhỏ hơn 235 nguyên tố cùng nhau 
từng cặp. Để tìm các số nguyên nh− vậy, thuận tiện nhất là dùng các số dạng 2m-1, 
trong đó m là số nguyên d−ơng. Các phép tính số học với những số có dạng nh− vậy 
t−ơng đối đơn giản dựa vào bổ đề sau. 
Bổ đề 2.8. Nếu a và b là các số nguyên d−ơng thì thặng d− d−ơng bé nhất modulo 2b-
1 của 2a-1 là 2r-1, trong đó r là thặng d− d−ơng bé nhất của a modulo b. 
Thật vậy, nếu a=bq+r, trong đó r là thặng d− d−ơng bé nhất của a modulo b, thì ta 
có 
(2a-1)=(2bq+r-1)=(2b-1)(2b(q-1)+r+...+2b+r+2r)+(2r-1). 
Hệ quả 2.9. Nếu a và b là các số nguyên d−ơng, thì −ớc chung lớn nhất của 2a-1 và 
2b-1 là 2(a,b)-1. 
Hệ quả 2.10. Các số nguyên 2a-1 và 2b-1 nguyên tố cùng nhau khi và chỉ khi a và b 
nguyên tố cùng nhau. 
Chúng tôi dành việc chứng minh hai bổ đề này cho độc giả. 
Ta có thể sử dụng hệ quả trên đây để tìm các số nhỏ hơn 235, nguyên tố cùng nhau 
từng cặp, sao cho tích của chúng lớn hơn một số đã cho. Giả sử ta cần làm các phép 
tính số học với những số nguyên có cỡ 2184. Ta đặt: m1=2
35-1, m2=2
34-1, m3=2
33-1, 
m4=2
31-1, m5=2
29-1, m6=2
23-1. Vì số mũ của 2 trong các số trên nguyên tố với nhau 
từng cặp, nên theo hệ quả trên, các số đã chọn cũng nguyên tố với nhsu từng cặp. Ta 
có tích m1 m2 m3 m4 m5 m6>2
184. Bây giờ ta có thể làm các phép tính số học với 
những số cỡ đến 2184. 
 17
Trong các máy tính hiện đại, việc thực hiện nhiều phép tính đ−ợc tiến hành đồng 
thời. Vì thế việc sử dụng định lí Trung Quốc về phần d− nh− trên lại càng tiện lợi: 
thay cho việc làm các phép tính với các số nguyên lớn, ta làm nhiều phép tính đồng 
thời với những số nguyên bé hơn. Điều đó giảm đáng kể thời gian tính toán. 
 18
Thuật toán giải ph−ơng trình đồng d− bằng định lí Trung Quốc 
Từ chứng minh định lí Trung Quốc về phần d−, ta có thuật toán sau đây để giải hệ 
ph−ơng trình đồng d− x ≡ xi (mod mi), trong đó mi, 1≤ i≤k là các số nguyên tố với 
nhau từng cặp, xi là các số nguyên cho tr−ớc. Trong thuật toán trình bày sau đây, 
chúng ta đã tìm ra cách để tránh phải làm việc với các số lớn nh− Mi và aiMi. 
Thuật toán. 
1. (Xuất phát). Đặt j←2, C1←1. Hơn nữa ta sắp xếp lại 
các số mi theo thứ tự tăng dần. 
2. (Tính toán sơ bộ). Đặt p←m1m2...mj-1(mod mj). Tính 
(u,v,d) sao cho up+vmj=d=UCLN(p,mj) bằng thuật toán 
Euclid mở rộng. 
Ed. Nếu d>0, in ra thông báo: các mi không nguyên tố cùng 
nhau từng cặp. Nếu ng−ợc lại, đặt Cj←u, j←j+1 và 
chuyển sang b−ớc 3 nếu j≤k. 
3. (Tính các hằng số phụ). Đặt y1←x1 mod m1, và mỗi 
j=2,...,k tính: 
yj←(xj-(y1+m1(y2+m2(y3+...+mj-2yj-1)...))Cjmod mj. 
4. (Kết thúc). In ra 
x← y1+m1(y2+m2(y3+...+mk-1yk)...), và kết thúc thuật toán. 
Đ5. Một số đồng d− đặc biệt. 
Định lí Wilson. p là số nguyên tố khi và chỉ khi (p-1)! ≡ -1 (mod p). 
Chứng minh. Tr−ớc tiên, giả sử p là số nguyên tố. Khi p=2, ta có 
(p-1)! ≡ 1≡ -1(mod 2). Bây giờ giả sử p là số nguyên tố lớn hơn 2. Theo bài tập 2.18, 
với mỗi số nguyên a với 1≤ a≤ p-1, tồn tại nghịch đảo a , 1≤ a ≤ p-1, với 
aa ≡ 1(mod p). Theo bài tập 2.13, trong số các số nguyên d−ơng nhỏ hơn p, chỉ có 1 
và p-1 là nghịch đảo với chính nó. Nh− vậy ta có thể nhóm các số nguyên từ 2 đến 
p-2 thành (p-3)/2 cặp số nguyên, tích của mỗi cặp đồng d− với 1 modulo p. Nh− vậy 
ta có: 
2.3.....(p-3)(p-2)≡ 1 (mod p) 
Nhân hai vế với 1 và p-1 ta đ−ợc: 
(p-1)! ≡ 1.2.3...(p-2)(p-1) ≡ 1(p-1) ≡ -1(mod p) 
Ng−ợc lại giả sử p thoả mãn đồng d− phát biểu trong định lí và a là một −ớc số của 
p, a<p. Khi đó, a | (p-1)!. Nh−ng theo giả thiết, p | (p-1)!+1, từ đó suy ra a=1, vì là 
−ớc chung của p và (p-1)!. Vậy p là số nguyên tố, định lí đ−ợc chứng minh. 
 19
Định lí Wilson có thể đ−ợc dùng để kiểm tra một số có phải là số nguyên tố hay 
không. Tuy nhiên , dễ thấy rằng, thuật toán dựa theo định lí Wilson khó có thể sử 
dụng với những số nguyên lớn, bởi vì số các phép tính bit đòi hỏi quá cao. 
Để đơn giản, ta gọi công việc xem xét một số đã cho có phải là số nguyên tố hay 
không là kiểm tra nguyên tố. Định lí sau đây có nhiều ứng dụng trong kiểm tra 
nguyên tố. 
Định lí Fermat bé. Nếu p là số nguyên tố và a là số không chia hết cho p thì 
ap-1≡ 1(mod p). 
Chứng minh. Xét p-1 số nguyên a, 2a,..., (p-1)a. Các số đó đều không chia hết cho p 
và không có hai số nào đồng d− modulo p. Nh− vậy, các thặng d− d−ơng bé nhất của 
chúng phải là 1, 2,... p-1, xếp theo thứ tự nào đó. Từ đó ta có: 
a.2a.....(p-1) ≡ 1...(p-1)≡ (p-1)!(mod p) 
tức là 
ap-1(p-1)!≡ 1(mod p) 
Vì ((p-1)!,p)=1 nên ta có ap-1≡ 1(mod p). 
Hệ quả 2.11. Nếu p là số nguyên tố và a là số nguyên d−ơng thì ap≡ a(mod p). 
Hệ quả 2.12. Nếu p là số nguyên tố và a là số nguyên không chia hết cho p thì ap-2 là 
nghịch đảo của a modulo p. 
Hệ quả 2.13. Nếu a và b là các số nguyên d−ơng, p nguyên tố, p|a thì các nghiệm 
của đồng d− thức tuyến tính ax≡ b(mod p) là các số nguyên x sao cho 
x≡ ap-2b(mod p). 
Đ6. Số giả nguyên tố. 
Theo định lí Fermat, nếu n là số nguyên tố và b là số nguyên tuỳ ý, thì bn≡ b(mod n). 
Do đó nếu tồn tại số b sao cho bn /≡ b(mod n) thì n phải là hợp số. Trong nhiều ứng 
dụng , chúng ta lại cần đến các thuật toán để chỉ ra một số n là số nguyên tố. Trong 
tr−ờng hợp này, ta không thể dùng định lí Fermat bé, vì định lí ng−ợc của nó không 
đúng. Tuy nhiên, nếu một số nguyên thoả mãn các giả thiết của định lí Fermat bé thì 
“có nhiều khả năng” nó là một số nguyên tố! Ta có định nghĩa sau đây. 
Định nghĩa 2.14. Giả sử b là một số nguyên d−ơng. Nếu n là hợp số nguyên d−ơng 
và bn ≡ b(mod n) thì n đ−ợc gọi là số giả nguyên tố cơ sở b. 
Trong tr−ờng hợp (n,b)=1, ta th−ờng dùng định nghĩa t−ơng đ−ơng: bn-1≡ b(mod n). 
Ví dụ. Số nguyên 561=3.11.17 là số giả nguyên tố cơ sở 2. Thật vậy, áp dụng định lí 
Fermat bé, ta có 2560=(22)280 ≡ 1(mod 3), 2560=(210)56 ≡ 1(mod 11), 
2560=(216)35 ≡ 1(mod 17). Từ đó suy ra (bài tập 2.12) 2560 ≡ 1(mod 561). 
 20
Nói chung các số giả nguyên tố ít hơn nhiều so với các số nguyên tố. Chẳng hạn, có 
tất cả 4550525112 số nguyên tố bé hơn 1010, nh−ng chỉ có 14884 số giả nguyên tố cơ 
sở 2 trong khoảng đó. Sự kiện này giải thích cách nói ở trên: Các số thoả mãn định lí 
Fermat bé có nhiều khả năng là số nguyên tố. Tuy nhiên đối với mọi cơ sở tuỳ ý, số 
các số giả nguyên tố là vô hạn. Chẳng hạn, ta chứng minh điều đó đối với cơ sở 2. 
Định lí 2.15.