🔙 Quay lại trang tải sách pdf ebook Giáo trình lý thuyết số
Ebooks
Nhóm Zalo
TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT
🖞 🖮 🖟
GIAÙO TRÌNH
LYÙ THUYEÁT SOÁ VUÕ VAÊN THOÂNG
MUÏC LUÏC
1 SOÁ NGUYEÂN 3 1.1 Vaønh soá nguyeân . ........................ 3 1.2 Caùc tính chaát cô baûn cuûa Z ................... 4 1.3 Pheùp chia trong Z ........................ 6 1.4 Bieåu dieãn soá nguyeân ....................... 7
2 ÖÔÙC CHUNG LÔÙN NHAÁT.
SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ. 13 2.1 Öôùc chung lôùn nhaát . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Thuaät toaùn Euclid . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Ñònh lyù cô baûn cuûa soá hoïc . . . . . . . . . . . . . . . . . . . 17 2.4 Phöông trình Diophantus tuyeán tính . . . . . . . . . . . . . . . 19
3 ÑOÀNG DÖ 25 3.1 Khaùi nieäm ñoàng dö . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Caùc ñoàng dö tuyeán tính . . . . . . . . . . . . . . . . . . . . . 28 3.3 Ñònh lyù phaàn dö Trung hoa . . . . . . . . . . . . . . . . . . . 30 3.4 Heä caùc ñoàng dö tuyeán tính . . . . . . . . . . . . . . . . . . . . 31 3.5 Ñònh lyù Wilson vaø ñònh lyù Euler . . . . . . . . . . . . . . . . 34
4 CAÙC HAØM SOÁ HOÏC 43 4.1 Nhaän xeùt chung . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Haøm Euler ϕ(n). .............. . . . . . . . . . . . 46 4.3 Haøm toång caùc öôùc σ(n) vaø soá caùc öôùc τ (n). . . . . . . . . . . 48 4.4 Haøm Mo¨bius µ(n). . . . . . . . . . . . . . . . . . . . . . . . . 51
1
2 MUÏC LUÏC
5 CAÊN NGUYEÂN THUÛY 57 5.1 Baäc cuûa soá nguyeân vaø caên nguyeân thuyû . . . . . . . . . . . . 57 5.2 Caên nguyeân thuyû cuûa soá nguyeân toá . . . . . . . . . . . . . . . 61 5.3 Caùc soá coù caên nguyeân thuyû . . . . . . . . . . . . . . . . . . . 64 5.4 Chæ soá soá hoïc . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6 THAËNG DÖ BÌNH PHÖÔNG 75 6.1 Thaëêng dö bình phöông . . . . . . . . . . . . . . . . . . . . . . 75 6.2 Luaät thuaän nghòch bình phöông . . . . . . . . . . . . . . . . . 80 6.3 Kyù hieäu Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.4 Soá giaû nguyeân toá Euler . . . . . . . . . . . . . . . . . . . . . 87
7 SOÁ b- PHAÂN. PHAÂN SOÁ LIEÂN TUÏC 97 7.1 Soá b-phaân . ................. . . . . . . . . . . . 97 7.2 Phaân soá lieân tuïc höõu haïn . . . . . . . . . . . . . . . . . . . . 102 7.3 Phaân soá lieân tuïc voâ haïn . . . . . . . . . . . . . . . . . . . . . 108 7.4 Vaøi öùng duïng cuûa phaân soá lieân tuïc . . . . . . . . . . . . . . . 118
8 MOÄT VAØI PHÖÔNG TRÌNH DIOPHANTUS PHI TUYEÁN 125 8.1 Caùc boä ba Pythagoras . . . . . . . . . . . . . . . . . . . . . . 125 8.2 Toång cuûa hai soá chính phöông . . . . . . . . . . . . . . . . . . 126 8.3 Toång cuûa boán soá chính phöông . . . . . . . . . . . . . . . . . 128 8.4 Phöông trình Pell . . . . . . . . . . . . . . . . . . . . . . . . . 131
1
SOÁ NGUYEÂN
1.1 Vaønh soá nguyeân
Vaønh soá nguyeân Z laø môû roäng nhoû nhaát cuûa taäp soá töï nhieân N cuøng vôùi caùc pheùp toaùn coäng vaø nhaân sao cho phöông trình a+x = b luoân luoân coù nghieäm. Nghieäm duy nhaát x cuûa phöông trình a + x = b ñöôïc kyù hieäu laø b − a.
Ñònh lyù 1.1. Coù vaønh Z vôùi caùc pheùp toaùn coäng (kyù hieäu: + ), nhaân ( · ) vaø aùnh xaï f : N −→ Z sao cho:
1. f vöøa laø ñôn caáu nöûa nhoùm coäng vöøa laø ñôn caáu nöûa nhoùm nhaân. 2. Caùc phaàn töû cuûa Z ñeàu coù daïng f(a) − f(b) vôùi a, b ∈ N.
Chöùng minh. Quan heä hai ngoâi treân tích Descartes N × N xaùc ñònh bôûi: (a, b) (c, d) neáuu a + d = b + c laø quan heä töông ñöông.
Ta kyù hieäu taäp thöông N × N/ laø Z vaø goïi noù laø vaønh (?!) soá nguyeân. Nhö vaäy, moãi soá nguyeân laø moät lôùp töông ñöông vaø neáu noù chöùa ñaïi dieän (m, n) ta seõ taïm kyù hieäu noù laø (m, n).
Pheùp coäng vaø nhaân treân Z ñöôïc ñònh nghóa nhö sau:
(a, b) + (c, d) = (a + c, b + d).
(a, b) · (c, d) = (ac + bd, ad + bc).
Xem nhö baøi taäp, yeâu caàu ñoïc giaû töï kieåm tra tính ñuùng ñaén cuûa ñònh nghóa caùc pheùp toaùn neâu treân vaø chöùng toû raèng (Z, +, ·) laø moät vaønh giao hoaùn vôùi phaàn töû trung hoaø cuûa pheùp coäng vaø cuûa pheùp nhaân töông öùng laø
3
4 1. SOÁ NGUYEÂN
0 = (0, 0) , 1 = (1, 0).
AÙnh xaï f : N −→ Z xaùc ñònh bôûi: f(n) = (n, 0).
1. Deã daøng thaáy raèng f laø ñôn aùnh vaø:
f(a + b) = (a + b, 0) = (a, 0) + (b, 0) = f(a) + f(b)
f(a · b) = (ab, 0) = (a, 0) · (b, 0) = f(a) · f(b)
2. Giaû söû x = (a, b) ∈ Z. Khi ñoù:
x = (a, 0) + (0, b) = (a, 0) − (b, 0) = f(a) − f(b).
Nhaän xeùt:
1) Ta ñoàng nhaát moãi soá töï nhieân n vôùi aûnh f(n) ∈ Z; do ñoù N ⊂ Z.
2) Neáu a, b ∈ N,a > b thì soá nguyeân x = (a, b) = (a − b, 0) = f(a − b); do coù söï ñoàng nhaát neân x chính laø soá töï nhieân n = a − b vaø ta goïi noù laø soá nguyeân döông, ta vieát x = n.
Neáu a, b ∈ N,a < b thì soá nguyeân x = (a, b) = −(b − a, 0) = −f(b − a); nhö vaäy x chính laø soá ñoái cuûa soá töï nhieân n = b−a vaø ta goïi noù laø soá nguyeân aâm, ta vieát: x = −n.
Soá nguyeân x = (n, n) chính laø soá 0.
1.2 Caùc tính chaát cô baûn cuûa Z
Vaønh R ñöôïc goïi laø moät mieàn nguyeân neáuu vôùi moïi x, y ∈ R : x = 0, y = 0 keùo theo xy = 0.
Ñònh lyù 1.2. Z laø mieàn nguyeân, ñeám ñöôïc, chöùa N nhö laø nöûa nhoùm con coäng vaø nöûa nhoùm con nhaân. Moïi vaønh cöïc tieåu chöùa N nhö laø nöûa nhoùm con coäng vaø nöûa nhoùm con nhaân ñeàu ñaúng caáu vaønh vôùi Z.
1.2. CAÙC TÍNH CHAÁT CÔ BAÛN CUÛA Z 5
Chöùng minh. Ta ñaõ bieát vaønh soá nguyeân Z goàm caùc soá töï nhieân n vaø caùc soá ñoái −n; töø ñaây deã daøng suy ra raèng Z laø mieàn nguyeân, ñeám ñöôïc, cöïc tieåu chöùa N nhö laø nöûa nhoùm con coäng vaø nöûa nhoùm con nhaân.
Giaû söû X laø moät vaønh cöïc tieåu coù aùnh xaï g : N −→ X vöøa laø ñôn caáu nöûa nhoùm coäng vöøa laø ñôn caáu nöûa nhoùm nhaân. Vaäy thì X chæ goàm caùc phaàn töû g(n) vaø −g(n), n ∈ N. Deã daøng thaáy raèng aùnh xaï ϕ : Z −→ X, +n −→ +g(n) laø moät ñaúng caáu vaønh.
Vaønh giao hoaùn R cuøng vôùi moät quan heä thöù töï toaøn phaàn ≤ ñöôïc goïi laø vaønh ñöôïc saép thöù töï neáuu vôùi moïi x, y ∈ R ñeàu thoûa :
1. ∀z ∈ R (x ≤ y ⇒ x + z ≤ y + z)
2. 0 ≤ x, 0 ≤ y ⇒ 0 ≤ xy
Treân Z ta ñöa ra quan heä 2-ngoâi ≤ nhö sau: x ≤ y neáuu y − x ∈ N. Deã thaáy ñaây laø quan heä thöù töï treân Z vaø laø môû roäng cuûa quan heä thöù töï treân N.
Ñònh lyù 1.3. Z, ≤ laø moät vaønh ñöôïc saép thöù töï Archimed. Chöùng minh. Xem nhö baøi taäp cho ñoïc giaû Trò tuyeät ñoái cuûa soá nguyeân x, kyù hieäu laø |x|, ñöôïc ñònh nghóa:
|x| =
x neáu x ≥ 0 −x neáu x ≤ 0
Caùc tính chaát veà trò tuyeät ñoái xem nhö ñaõ roõ.
Ñònh lyù 1.4. Giaû söû M laø taäp khoâng roãng caùc soá nguyeân. Khi ñoù: 1. Neáu M bò chaën treân thì M chöùa soá lôùn nhaát.
2. Neáu M bò chaën döôùi thì M chöùa soá nhoû nhaát.
Chöùng minh. Chuùng toâi chæ chöùng minh cho tröôøng hôïp taäp M laø bò chaën treân.
Ñaët A = M ∩ N. Neáu A = ∅ phaàn töû lôùn nhaát b cuûa A seõ laø phaàn töû lôùn nhaát cuûa M. Ngöôïc laïi, thì soá −b seõ laø phaàn lôùn nhaát cuûa M vôùi b = min {−x : x ∈ M }.
Ñoïc giaû töï chöùng minh cho tröôøng hôïp taäp M bò chaën döôùi.
6 1. SOÁ NGUYEÂN 1.3 Pheùp chia trong Z
Chuùng ta noùi raèng soá nguyeân a chia heát cho soá nguyeân b = 0, hay a laø boäi cuûa b, kyù hieäu a .: b, neáuu coù soá nguyeân c ñeå a = bc. Trong tröôøng hôïp naøy ta cuõng noùi laø b chia chia heát a, hay b laø öôùc (thöøa soá) cuøa a, kyù hieäu b | a. Ngöôïc laïi, ta noùi raèng a khoâng chia heát cho b, hay b khoâng chia heát a, kyù hieäu b a.
Ví duï 1.3.1. 6 | 12 ; −5 | 20 ; 7 | − 49 ; −8 | − 16 ; 15 | 0; 8 12 ; − 3 8; 4 −9 ; −12 −18.
Deã daøng chöùng minh ñöôïc ñònh lyù sau:
Ñònh lyù 1.5. Giaû söû a, b laø caùc soá nguyeân. Khi ñoù:
1. Neáu b | a vaø a > 0,b> 0 thì 1 ≤ b ≤ a.
2. Neáu b | a vaø c | b, thì c | a.
3. Neáu b | a vaø c = 0 thì bc | ac.
4. Neáu c | a vaø c | b, thì c | (ma + nb) vôùi caùc soá nguyeân m, n baát kyø.
Ñònh lyù 1.6. Giaû söû a, b laø caùc soá nguyeân, b = 0. Khi ñoù toàn taïi duy nhaát caùc soá nguyeân q, r thoûa: a = bq + r vaø 0 ≤ r < |b|.
Chöùng minh. Taäp caùc soá nguyeân M = {bx : x ∈ Z ; bx ≤ a } laø khoâng roãng vaø bò chaën treân, theo ñònh lyù 1.4, M coù soá lôùn nhaát laø bq. Ta coù bq ≤ a vaø a < bq + |b|; suy ra 0 ≤ r = a − bq < |b|.
Giaû söû ta coù caùc bieåu dieãn: a = bq1 + r1 = bq2 + r2; 0 ≤ r1, r2 < |b|. Theá thì: |b|·|q1 − q2| = |r1 − r2| < |b|; suy ra q1 = q2 vaø do ñoù r1 = r2.
Khi a = bq + r, 0 ≤ r < |b| ta noùi q laø thöông vaø r phaàn dö cuûa pheùp chia a cho b. Hieån nhieân b | a khi vaø chæ khi r = 0.
Ví duï 1.3.2. Pheùp chia 133 cho 21 coù thöông laø 6 vaø phaàn dö laø 7. Pheùp chia −50 cho 8 coù thöông laø −7 vaø phaàn dö laø 6. Pheùp chia 50 cho −8 coù thöông laø −6 vaø phaàn dö laø 2. Pheùp chia −133 cho −21 coù thöông laø 7 vaø phaàn dö laø 14.
1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 7
Soá nguyeân 1 coù ñuùng moät öôùc döông. Moãi soá nguyeân lôùn hôn 1 ñeàu coù ít nhaát hai öôùc döông vì noù chia heát cho 1 vaø chính noù.
Soá nguyeân lôùn hôn 1 maø noù coù ñuùng hai öôùc döông, ñöôïc goïi laø soá nguyeân toá.
Soá nguyeân lôùn hôn 1 vaø khoâng laø soá nguyeân toá, ñöôïc goïi laø hôïp soá.
1.4 Bieåu dieãn soá nguyeân
Chuùng ta ñaõ quen vôùi vieäc bieåu dieãn caùc soá nguyeân trong heä ñeám thaäp phaân (heä ñeám cô soá möôøi). Baây giôø chuùng ta seõ chæ ra raèng moãi soá nguyeân b > 1 ñeàu coù theå ñöôïc söû duïng laøm cô soá cho vieäc bieåu dieãn caùc soá nguyeân. Vaø vì moãi soá nguyeân aâm laø soá ñoái cuûa soá nguyeân döông neân ñònh lyù sau ñaây laø caên baûn.
Ñònh lyù 1.7. Giaû söû b > 1 laø moät soá nguyeân. Theá thì, moïi soá nguyeân döông n ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng
n = akbk + ak−1bk−1 + ··· + a1b + a0
trong ñoù k laø soá nguyeân khoâng aâm, caùc aj laø soá nguyeân vôùi 0 ≤ aj ≤ b − 1 vaø heä soá ñaàu tieân ak = 0.
Chöùng minh. Töø ñònh lyù 1.6 ta coù:
n = bq0 + a0, 0 ≤ a0 ≤ b − 1.
Neáu q0 = 0, tieáp tuïc chia q0 cho b ta ñöôïc:
q0 = bq1 + a1, 0 ≤ a1 ≤ b − 1.
Tieáp tuïc quaù trình naøy ñeán luùc ñaït ñöôïc:
q1 = bq2 + a2, 0 ≤ a2 ≤ b − 1,
q2 = bq3 + a3, 0 ≤ a3 ≤ b − 1,
...
8 1. SOÁ NGUYEÂN
qk−2 = bqk−1 + ak−1, 0 ≤ ak−1 ≤ b − 1,
qk−1 = b.0 + ak, 0 ≤ ak ≤ b − 1.
Deã daøng suy ra:
n = akbk + ak−1bk−1 + ··· + a1b + a0
vôùi ø 0 ≤ aj ≤ b − 1, ak = qk−1 = 0.
Ta seõ chöùng minh tính duy nhaát cuûa bieåu dieãn baèng qui naïp theo soá nguyeân döông n.
Tröôøng hôïp n = 1 ta chæ coù bieåu dieãn duy nhaát vôùi k = 0, vaø a0 = 1. Giaû söû ta coù
n = akbk +ak−1bk−1 +···+a1b+a0 = cmbm +cm−1bm−1 +···+c1b+c0. (∗)
Do ñònh lyù 1.6: phaàn dö cuûa pheùp chia n cho b laø duy nhaát, neân a0 = c0. Do a0 = c0 neân töø (*) ta suy ra:
n1 = akbk−1 + ak−1bk−2 + ··· + a1 = cmbm−1 + cm−1bm−2 + ··· + c1.
Deã chöùng toû ñöôïc raèng n1 < n, vaäy theo giaû thieát qui naïp ta coù: m = k vaø a1 = c1, ··· , ak = ck.
Heä quaû 1.7.1. Moïi soá nguyeân döông ñeàu laø toång caùc luõy thöøa khaùc nhau cuûa 2. Chöùng minh. Theo ñònh lyù 1.7 vôùi b = 2, ta coù
n = ak2k + ak−12k−1 + ··· + a12 + a0,
vôùi k laø soá töï nhieân, caùc aj baèng 0 hoaëc 1, ak = 0.
Nhaän xeùt:
1) Soá nguyeân döông n = akbk + ak−1bk−1 + ··· + a1b + a0 trong ñònh lyù 1.7 thöôøng ñöôïc vieát laø (akak−1 ··· a1a0)b.
2) Vieäc ñoåi soá nguyeân döông (akak−1 ··· a1a0)q trong heä ñeám cô soá q sang cô soá b ñöôïc thöïc hieän hoaøn toaøn töông töï nhö thuaät toaùn tìm bieåu dieãn cuûa soá nguyeân döông trong ñònh lyù 1.7 chæ löu yù laø khi chia cho b (trong heä q−phaân) thì b ñaõ ñöôïc vieát trong heä q−phaân, sau ñoù caùc soá dö phaûi ñöôïc ñoåi sang heä b−phaân ñeå bieåu dieãn soá trong heä b−phaân.
1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 9
Ví duï 1.4.1. Chuùng ta caàn ñoåi soá thaäp phaân 610 sang heä nhò phaân. Vì trong heä thaäp phaân nhò vaãn ñöôïc vieát laø 2 neân ta thöïc hieän lieân tieáp caùc pheùp chia cho 2 trong heä thaäp phaân:
106 = 2 · 53 + 0,
53 = 2 · 26 + 1,
26 = 2 · 13 + 0,
13 = 2 · 6+1,
6=2 · 3+0,
3=2 · 1+1,
1=2 · 0+1.
Thuaät chia döøng vì thöông ñaõ baèng 0. Caùc soá dö vieát trong heä nhò phaân töông öùng laø: c0 = 0, c1 = 1, c2 = 0, c3 = 1, c4 = 0, c5 = 1, c6 = 1; vaäy soá ñaõ cho coù bieåu dieãn trong heä nhò phaân laø 1101010.
Ví duï 1.4.2. Chuùng ta caàn ñoåi soá thaäp phaân 2003 sang heä thaäp luïc phaân. Vì soá thaäp luïc trong heä thaäp phaân ñöôïc vieát laø 16 neân ta thöïc hieän lieân tieáp caùc pheùp chia cho 16 trong heä thaäp phaân:
2003 = 16 · 125 + 3,
125 = 16 · 7 + 13,
7 = 16 · 0+7.
Thuaät chia döøng vì thöông ñaõ baèng 0. Caùc soá dö vieát trong heä thaäp luïc phaân töông öùng laø: c0 = 3, c1 = D, c2 = 7; vaäy soá ñaõ cho coù bieåu dieãn trong heä thaäp luïc phaân laø 7D3.
BAØI TAÄP CHÖÔNG I
10 1. SOÁ NGUYEÂN
1. Chöùng minh tính ñuùng ñaén cuûa ñònh nghóa pheùp coäng, pheùp nhaân treân Z vaø (Z, +, ·) laø moät vaønh giao hoaùn.
2. Chöùng minh raèng Z laø mieàn nguyeân, ñeám ñöôïc, cöïc tieåu chöùa N nhö laø nöûa nhoùm con coäng vaø nöûa nhoùm con nhaân.
3. Chöùng minh raèng Z, ≤ laø moät vaønh ñöôïc saép thöù töï Archimed. 4. Chöùng minh ñònh lyù1.5
5. Xaùc ñònh thöông vaø phaàn dö trong pheùp chia cho 7 vaø cho −7 cuûa caùc soá:
a) 9 b) 99 c) 999 d) 9999 e) 99999
6. Xaùc ñònh thöông vaø phaàn dö trong pheùp chia cho 17 vaø cho −17 cuûa caùc soá:
a) − 8 b) − 88 c) − 888 d) − 8888 e) − 88888
7. Chöùng minh raèng neáu a, b, c, d laø caùc soá nguyeân vôùi a vaø c khaùc 0 sao cho a | b vaø c | d thì ac | bd.
8. Giaû söû a, b, c laø caùc soá nguyeân vaø c = 0. Chöùng minh raèng a | b khi vaø chæ khi ac | bc.
9. Chöùng minh raèng neáu a, b laø caùc soá nguyeân vaø a | b thì an | bn vôùi moïi soá soá töï nhieân n.
10. Haõy ñoåi caùc soá thaäp phaân 1955, −1973 sang heä sang heä thaäp luïc phaân, heä töù phaân, heä nhò phaân, heä baùt phaân.
11. Haõy ñoåi soá thaäp luïc phaân ABCDEF sang heä heä nhò phaân, heä töù phaân vaø heä baùt phaân.
12. Haõy phaùt bieåu vieäc chuyeån ñoåi soá töø heä ñeám cô soá r sang heä ñeám cô soá rn vaø ngöôïc laïi ? khi r, n > 1 laø caùc soá nguyeân döông.
13. Chöùng minh raèng neáu b < −1 laø moät soá nguyeân thì moïi soá nguyeân n = 0 ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng
n = akbk + ak−1bk−1 + ··· + a1b + a0
trong ñoù k laø soá nguyeân khoâng aâm, caùc aj laø soá nguyeân vôùi 0 ≤ aj ≤ |b| − 1 vaø heä soá ñaàu tieân ak = 0.
Haõy bieåu dieãn caùc soá thaäp phaân −7, −17, 61 trong heä cô soá −2.
1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 11
14. Chöùng minh raèng moïi soá nguyeân n = 0 ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng
n = ak3k + ak−13k−1 + ··· + a13 + a0
trong ñoù k laø soá nguyeân khoâng aâm, caùc aj baèng −1, 0, hoaëc 1 vaø heä soá ak = 0.(Khai trieån thaêng baèng caùnh eùn)
Haõy khai trieån thaêng baèng caùnh eùn caùc soá thaäp phaân: 13, 40, 121. 15. Chöùng minh raèng coù voâ soá soá nguyeân toá.
16. Chöùng minh raèng vôùi moïi soá nguyeân döông n ñeàu toàn taïi n soá töï nhieân lieân tieáp laø hôïp soá.
17. Chöùng minh raèng neáu a, n laø caùc soá nguyeân döông sao cho an − 1 laø soá nguyeân toá thì a = 2 vaø n laø soá nguyeân toá.
18. Chöùng minh raèng neáu n laø hôïp soá thì noù coù öôùc nguyeân toá khoâng vöôït quaù √n.
19. Chöùng minh raèng neáu öôùc nguyeân toá nhoû nhaát p cuûa soá nguyeân döông n vöôït quaù √3 n thì n/p laø soá nguyeân toá hoaëc baèng 1.
12 1. SOÁ NGUYEÂN
2
ÖÔÙC CHUNG LÔÙN NHAÁT. SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
2.1 Öôùc chung lôùn nhaát
Neáu a, b laø caùc soá nguyeân khoâng ñoàng thôøi baèng khoâng, thì taäp caùc öôùc chung cuûa a vaø b laø höõu haïn vaø chöùa caùc soá +1 vaø −1. Chuùng ta seõ quan taâm ñeán soá nguyeân lôùn nhaát naèm trong caùc öôùc chung naøy.
Öôùc chung lôùn nhaát cuûa hai soá nguyeân khoâng ñoàng thôøi baèng khoâng a vaø b laø soá nguyeân lôùn nhaát chia heát ñoàng thôøi caû a vaø b.
Öôùc chung lôùn nhaát cuûa hai soá nguyeân a vaø b ñöôïc kyù hieäu laø (a, b).
Khaùi nieäm öôùc chung lôùn nhaát cuûa cuûa caùc soá nguyeân khoâng ñoàng thôøi baèng khoâng a1, a2, ··· , an ñöôïc hieåu hoaøn toaøn töông töï nhö khaùi nieäm öôùc chung lôùn nhaát cuûa cuûa caùc soá nguyeân. Ñoù chính laø soá nguyeân lôùn nhaát chia heát ñoàng thôøi taát caû caùc aj , 1 ≤ j ≤ n. Öôùc chung lôùn nhaát cuûa cuûa caùc soá nguyeân a1, a2, ··· , an ñöôïc kyù hieäu laø (a1, a2, ··· , an).
Ví duï 2.1.1. Öôùc chung cuûa 24 vaø 84 laø ±1, ±2, ±3, ±4, ±6, ±12. Do ñoù (24, 84) = 12. Töông töï, ta coù (100, 5) = 5, (0, 44) = 44, (−17, 25) = 1, (17, −289) = 17, (−6, −15) = 3.
(24, −84, 100) = 4, (15, 0, 20, −17) = 1, (10, 20, 30, 40, 55) = 5. 13
14 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
Chuùng ta cuõng quan taâm ñeán caùc caëp soá nguyeân maø chuùng khoâng coù öôùc chung lôùn hôn 1. Caùc caëp soá nguyeân nhö vaäy ñöôïc goïi laø nguyeân toá cuøng nhau.
Hieån nhieân laø (a, b)=(b, a) vaø (a, b)=(|a|, |b|).
Ñònh lyù 2.1. Neáu a, b, c laø caùc soá nguyeân vaø (a, b) = d thì: 1. (a/d, b/d)=1
2. (a + cb, b)=(a, b)
Chöùng minh. Giaû söû e laø caùc soá nguyeân döông sao cho e | (a/d) vaø e | (b/d). Theá thì coù soá nguyeân k,l ñeå a/d = ke vaø b/d = le, cuõng vaäy a = dek, b = del. Vaäy de laø öôùc chung cuûa a vaø b; töø ñoù de ≤ d; suy ra e = 1.
Neáu u laø moät öôùc chung cuûa a vaø b, thì do ñònh lyù 1.5 ta coù u | (a + cb); vaäy u laø öôùc chung cuûa a + cb vaø b. Ngöôïc laïi, neáu u laø moät öôùc chung cuûa a + cb vaø b, thì cuõng do ñònh lyù 1.5 ta coù u | (a + cb) − cb = a; vaäy u laø öôùc chung cuûa a vaø b.
Neáu a, b laø caùc soá nguyeân, ta noùi soá nguyeân daïng ma + nb laø toå hôïp tuyeán tính cuûa a vaø b, trong ñoù m, n laø caùc soá nguyeân.
Moät taäp M = ∅ caùc soá nguyeân ñöôïc goïi laø moät module neáuu noù coù tính chaát: neáu m, n ∈ M thì m − n ∈ M.
Töø ñònh nghóa cuûa module suy ra raèng, neáu m, n ∈ M, thì 0 = m − m ∈ M, −n = 0 − n ∈ M, m + n = m − (−n) ∈ M.
Noùi moät caùch khaùc, neáu a, b ∈ M thì caùc toå hôïp tuyeán tính cuûa a vaø b cuõng thuoäc M. Module M = {0} ñöôïc goïi laø module taàm thöôøng.
Ñònh lyù 2.2. Moãi module khoâng taàm thöôøng M chính laø taäp taát caû caùc boäi cuûa moät soá nguyeân döông naøo ñoù.
Chöùng minh. Vì M khoâng taàm thöôøng neân noù chöùa soá döông. Giaû söû d laø soá döông nhoû nhaát cuûa M. Theá thì M chöùa taát caû caùc boäi cuûa d.
Baây giôø giaû söû m ∈ M. Töø ñònh lyù 1.6, ta coù m = dk + c, 0 ≤ c < d. Do m, dk ∈ M neân c = m − dk ∈ M. Vì d laø soá döông nhoû nhaát cuûa M neân c = 0, hay m laø boäi cuûa d.
2.2. THUAÄT TOAÙN EUCLID 15
Ñònh lyù 2.3. Giaû söû a, b laø caùc soá nguyeân khoâng ñoàng thôøi baèng 0 vaø d = (a, b). Khi ñoù module M = {ax + by : x, y ∈ Z } chính laø taäp taát caû caùc boäi cuûa d.
Chöùng minh. Deã daøng thaáy raèng M laø moät module khoâng taàm thöôøng.
Töø ñònh lyù 2.2 ta coù M chính laø taäp taát caû caùc boäi cuûa moät soá nguyeân döông e naøo ñoù. Do e chia heát moïi phaàn töû cuûa M neân e | a vaø e | b. Suy ra e ≤ d. Maët khaùc, do d | (ax + by) vôùi moïi x, y ∈ Z neân d chia heát moïi phaàn töû cuûa M, ñaëc bieät, d | e. Vaäy d ≤ e.
Heä quaû 2.3.1. Giaû söû d = (a, b) laø öôùc chung lôùn nhaát cuûa hai soá nguyeân a vaø b. Khi ñoù:
1. d laø soá nguyeân döông nhoû nhaát laø toå hôïp tuyeán tính cuûa a vaø b. 2. Moãi öôùc chung cuûa a vaø b ñeàu laø öôùc cuûa d.
Chöùng minh. 1. Heä quaû tröïc tieáp töø ñònh lyù treân.
2. Theo 1, coù x0, y0 ∈ Z ñeå ax0 + by0 = d. Giaû söû c laø öôùc cuûa a vaø cuûa b, hieån nhieân: c | ax0 + by0 = d.
Ñònh lyù 2.4. Neáùu a1, a2, ··· , an, an+1 laø caùc soá nguyeân khaùc khoâng, n ≥ 2, thì (a1, a2 ··· , an, an+1)=(a1, a2, ··· , an−1,(an, an+1)).
Chöùng minh. Moãi öôùc chung c cuûa caùc soá a1, a2, ··· , an, an+1 hieån nhieân laø öôùc chung cuûa an vaø an+1, do ñoù c laø öôùc cuûa (an, an+1). Vaäy c laø öôùc chung cuûa caùc soá a1, a2, ··· , an−1,(an, an+1).
Ngöôïc laïi, hieån nhieân moãi öôùc chung c cuûa a1, a2, ··· , an−1,(an, an+1) ñeàu laø öôùc cuûa caùc soá a1, a2, ··· , an−1, an, an+1.
2.2 Thuaät toaùn Euclid
Ñònh lyù 2.5. Giaû söû r0 = a vaø r1 = b laø caùc soá nguyeân vôùi a ≥ b > 0. Neáu thuaät toaùn chia ñöôïc thöïc hieän lieân tieáp rj = rj+1qj+1 +rj+2, 0 < rj+2 < rj+1 vôùi j = 0, 1, 2, ..., n−2 vaø rn+1 = 0, thì (a, b) = rn, laø soá dö khaùc 0 cuoái cuøng.
16 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
Chöùng minh. Töø ñònh lyù 2.1 ta coù nhaän xeùt laø: neáu c = dq + r thì (c, d) = (c − qd, d)=(r, d)=(d, r).
Theo thuaät toaùn Euclid:
r0 = r1q1 + r2 0 < r2 < r1
r1 = r2q2 + r3 0 < r3 < r2
...
rj−2 = rj−1qj−1 + rj 0 < rj < rj−1
...
rn−2 = rn−1qn−1 + rn 0 < rn < rn−1
rn−1 = rnqn + 0 .
Töø nhaän xeùt treân, ta coù: (a, b)=(r0, r1)=(r1, r2) = ··· = (rn−2, rn−1) = (rn−1, rn)=(rn, rn+1)=(rn, 0) = rn.
Ví duï 2.2.1. Duøng thuaät toaùn Euclid ñeå tìm (610, −1955). Vì (610, −1955) = (610, 1955) neân ta tìm (610, 1955). Ta coù:
1955 = 610 · 3 + 125
610 = 125 · 4 + 110
125 = 110 · 1 + 15
110 = 15 · 7+5
15 = 5 · 3+0.
Vaäy (610, 1955) = 5, suy ra (610, −1955) = 5.
Ví duï 2.2.2. Duøng thuaät toaùn Euclid ñeå tìm (1955, 2003). Ta coù:
2003 = 1955 · 1 + 48
1955 = 48 · 40 + 35
48 = 35 · 1 + 13
35 = 13 · 2+9
13 = 9 · 1+4
9=4 · 2+1
4=1 · 4+0.
Vaäy (1955, 2003) = 1, hay 1955 vaø 2003 laø caùc soá nguyeân toá cuøng nhau.
2.3. ÑÒNH LYÙ CÔ BAÛN CUÛA SOÁ HOÏC 17 2.3 Ñònh lyù cô baûn cuûa soá hoïc
Ñònh lyù 2.6. Ñònh lyù cô baûn cuûa soá hoïc. Moïi soá nguyeân lôùn hôn 1 ñeàu vieát ñöôïc moät caùch duy nhaát thaønh tích cuûa caùc thöøa soá nguyeân toá theo thöù töï khoâng giaûm.
Tröôùc khi chöùng minh ñònh lyù cô baûn, chuùng ta chöâng minh hai boå ñeà sau ñaây.
Boå ñeàù 2.6.1. Neáu a, b, c laø caùc soá nguyeân döông sao cho (a, b)=1 vaø a | bc thì a | c.
Chöùng minh. Vì (a, b)=1 neân theo ñònh lyù 2.3, coù caùc soá nguyeân x, y sao cho ax+by = 1. Nhaân hai veá cuûa ñaúng thöùc naøy vôùi c ta ñöôïc acx+bcy = c. Theo giaû thieát a | bc ta suy ra a | acx + bcy = c.
Boå ñeàù 2.6.2. Neáu p laø öôùc nguyeân toá cuûa tích a1a2 ··· ak, ôû ñaây a1, a2, ··· , ak laø caùc soá nguyeân, thì coù i, 1 ≤ i ≤ k ñeå p | ai.
Chöùng minh. Chuùng ta chöùng minh baèng qui naïp theo k. Tröôøng hôïp k = 1 laø taàm thöôøng. Giaû söû p laø öôùc nguyeân toá cuûa tích a1a2 ··· akak+1 . Neáu p ak+1 ta suy ra (p, ak+1) = 1; vaäy theo boå ñeà 2.6.1 ta coù p | a1a2 ··· ak.
Chöùng minh. Tröôùc heát ta chöùng minh baèng qui naïp theo n raèng moïi soá nguyeân lôùn hôn 1 ñeàu vieát ñöôïc thaønh tích cuûa caùc thöøa soá nguyeân toá. Tröôøng hôïp n = 2 laø taàm thöôøng. Soá nguyeân n+1 > 2 neáu laø soá nguyeân toá thì khoâng coù gì phaûi chöùng minh. Ngöôïc laïi, ta coù n +1= ab, vôùi 1 < a, b < n + 1; theo giaû thieát qui naïp thì a, b ñeàu laø tích cuûa caùc soá nguyeân toá.
Baây giôø ta chöùng minh tính duy nhaát cuûa bieåu dieãn. Giaû söû laø n = p1p2 ··· pr = q1q2 ··· qs
vôùi p1 ≤ p2 ≤···≤ pr, q1 ≤ q2 ≤···≤ qs laø caùc soá nguyeân toá. Töø boå ñeà 2.6.2 ta deã daøng suy ra raèng r = s vaø p1 = q1, ··· , pr = qs.
Chuù yù:
1. Moïi soá nguyeân n > 1 ñeàu coù bieåu dieãn duy nhaát
1 ... pαk
n = pα1
k , vôùi 1 ≤ k, 0 < α1, ··· , αk.
18 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
2. Neáu daõy taát caû soá nguyeân toá ñöôïc saép theo thöù töï taêng daàn: p1 = 2 < p2 = 3 < p3 = 5 < p4 = 7 < p5 = 11 < ···
thì moïi soá nguyeân döông ñeàu vieát ñöôïc moät caùch duy nhaát duôùi daïng +∞
n = k=0
pαk k ,
trong ñoù αk ≥ 0 vaø baèng 0 vôùi haàu heát, tröø moät soá höõu haïn caùc giaù trò cuûa k.
Boäi chung nhoû nhaát cuûa hai soá nguyeân a = 0 vaø b = 0, kyù hieäu laø [a, b], ñöôïc hieåu laø soá nguyeân döông nhoû nhaát chia heát cho caû a vaø b.
Deã daøng thaáy raèng [a, b]=[b, a] vaø [a, b]=[|a|, |b|].
Boäi chung nhoû nhaát cuûa caùc soá nguyeân khaùc khoâng a1, a2, ..., ak, kyù hieäu [a1, a2, ..., ak], laø soá nguyeân döông nhoû nhaát chia heát cho taát caû caùc soá aj , 1 ≤ j ≤ k.
Ñònh lyù 2.7. Neáu caùc soá nguyeân döông a, b coù söï phaân tích ra thöøa soá nguyeân
toá
thì
+∞
+∞
a = k=0
+∞
k vaø b =
pαk
k=0
+∞
pβk k
(a, b) = k=0
k , [a, b] =
pmin{αk,βk}
k=0
pmax{αk,βk}
k vaø (a, b) · [a, b] = ab.
Chöùng minh. Deã daøng thaáy raèng
+∞
c = k=0
+∞
k laø öôùc cuûa d =
pγk
k=0
pθk
k khi vaø chæ khi vôùi moïi k : γk ≤ θk.
Töø ñaây deã daøng suy ra
+∞
(a, b) =
k=0
+∞
k , [a, b] =
pmin{αk,βk}
k=0
pmax{αk,βk} k .
2.4. PHÖÔNG TRÌNH DIOPHANTUS TUYEÁN TÍNH 19 Ta coù
+∞
(a, b) · [a, b] = k=0
+∞
k =
pmin{αk,βk}+max{αk,βk} k=0
pαk+βk
k = ab.
Ví duï 2.3.1. Öôùc chung lôùn nhaát cuûa 2100 = 22 · 3 · 52 · 7, 40 = 23 · 5 baèng 22 · 5 = 20. Boäi chung nhoû nhaát cuûa 2100 vaø 40 baèng 23 · 3 · 52 · 7 = 4200.
2.4 Phöông trình Diophantus tuyeán tính
Caùc phöông trình maø chuùng ta chæ xeùt chuùng trong taäp soá nguyeân thöôøng ñöôïc goïi laø phöông trình Diophantus.
Phöông trình Diophantus tuyeán tính laø phöông trình coù daïng a1x1 + a2x2 + ··· + anxn = c
trong ñoù a1, a2, ··· , an = c laø caùc soá nguyeân.
Ñònh lyù 2.8. Giaû söû a, b laø caùc soá nguyeân khaùc khoâng vaø d = (a, b). Khi ñoù: 1. Neáu d c thì phöông trình ax + by = c khoâng coù nghieäm nguyeân.
2. neáu d | c thì phöông trình ax + by = c coù nghieäm nguyeân. Hôn theá nöõa, phöông trình coù caùc nghieäm nguyeân laø
x = x0 + (b/d)m, y = y0 − (a/d)m, m ∈ Z
vôùi x = x0, y = y0 laø moät nghieäm rieâng.
Chöùng minh. 1. Giaû söû x, y laø caùc soá nguyeân sao cho ax + by = c. Do d | a vaø d | b neân d | ax + by = c, voâ lyù vôùi giaû thieát d c.
2. Theo heä quaû 2.3.1 thì coù caùc soá nguyeân s, t ñeå
as + bt = d.
20 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
Vì d | c neân coù soá nguyeân e sao cho c = de. Suy ra
c = de = (as + bt)e = a(se) + b(te).
Vaäy phöông trình ax + by = c coù nghieäm.
Deã daøng thaáy raèng
x = x0 + (b/d)m, y = y0 − (a/d)m, m ∈ Z
thoaû phöông trình ax + by = c.
Giaû söû ax + by = c vaø ax0 + by0 = c. Khi ñoù ta coù
a(x − x0) + b(y − y0)=0,
suy ra
a(x − x0) = b(y0 − y),
hay
(a/d)(x − x0)=(b/d)(y0 − y).
Theo ñònh lyù 2.1 thì (a/d, b/d)=1. Söû duïng boå ñeà 2.6.1 ta suy ra (a/d) | (y0−y).Vaäy coù soá nguyeân m ñeå y0−y = (a/d)m, hay y = y0−(a/d)m. Thay vaøo heä thöùc a(x − x0) = b(y0 − y), ta ñöôïc x = x0 + (b/d)m.
Ví duï 2.4.1. Phöông trình 15x − 6y = 20 khoâng coù nghieäm nguyeân vì (15, −6) = 3 20.
Phöông trình 15x − 6y = −9 coù nghieäm nguyeân vì (15, −6) = 3 −9; hôn nöõa, vì x0 = −1, y0 = −1 laø moät nghieäm rieâng neân phöông trình 15x − 6y = −9 coù nghieäm laø x = −1 − 2m, y = −1 − 5m, m ∈ Z.
Ñònh lyù 2.9. Giaû söû a1, a2, ··· , an laø caùc soá nguyeân khaùc khoâng, n ≥ 2 vaø d = (a1, a2, ··· , an). Khi ñoù:
1. Neáu d c thì phöông trình a1x1 +a2x2 +···+anxn = c khoâng coù nghieäm nguyeân.
2.4. PHÖÔNG TRÌNH DIOPHANTUS TUYEÁN TÍNH 21
2. neáu d | c thì phöông trình a1x1+a2x2+···+anxn = c coù nghieäm nguyeân; hôn theá nöõa, phöông trình coù voâ soá nghieäm nguyeân phaân bieät.
Chöùng minh. 1. Giaû söû coù caùc soá nguyeân x1, x2, ··· , xn sao cho a1x1 + a2x2 + ··· + anxn = c.
Do d | aj vôùi moïi j, 1 ≤ j ≤ n, ta suy ra d | a1x1+a2x2+···+anxn = c; ñieàu naøy voâ lyù vôiù giaû thieát d c
2. Ta seõ chöùng minh baèng qui naïp.
Vôùi n = 2 thì ñaây chính laø ñònh lyù 2.8.
Xeùt phöông trình
a1x1 + a2x2 + ··· + anxn + an+1xn+1 = c.
Theo ñònh lyù 2.4, ta coù
d = (a1, a2, ··· , an−1, an, an+1)=(a1, a2, ··· , an−1,(an, an+1)). Do d | c neân theo giaû thieát qui naïp: phöông trình
a1x1 + a2x2 + ··· + an−1xn−1 + (an, an+1)y = c
coù nghieäm.
Maët khaùc, töø ñònh lyù 2.8 ta thaáy: vôùi moãi soá nguyeân y, phöông trình anxn + an+1xn+1 = (an, an+1)y ñeàu coù voâ soá nghieäm.
BAØI TAÄP CHÖÔNG II
1. Giaû söû a laø soá nguyeân döông. Haõy tìm (a, a + 1), (a, a + 2), (a, a + 3).
22 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
2. Chöùng toû raèng neáu (a, b)=1 thì (a + b, a − b) baèng 1 hoaëc 2.
3. Chöùng toû raèng caùc soá 6k − 1, 6k + 1, 6k + 2, 6k + 3, 6k + 5 laø ñoâi moät nguyeân toá cuøng nhau, vôùi moïi soá nguyeân k.
4. Chöùng toû raèng neáu (a, b)=1 vaø c | a + b thì (c, a)=(c, b)=1.
5. Chöùng toû raèng neáu (a, b)=(a, c)=1 thì (a, bc)=1. Toång quaùt hôn, neáu (a1, b)=(a2, b) = ··· = (an, b)=1 thì (a1a2 ··· an, b)=1.
6. Chöùng toû raèng neáu a1, a2, ..., an laø caùc soá nguyeân khoâng ñoàng thôøi baèng khoâng vaø c laø soá nguyeân khaùc khoâng, thì (ca1, ca2, ··· , can) = |c| · (a1, a2, ··· , an).
7. Chöùng minh raèng neáu a, b, c, d laø caùc soá nguyeân b > 0,d > 0,(a, b) = (c, d)=1 vaø a/b + c/d laø soá nguyeân thì b = d.
8. Giaû söû a, b laø caùc soá nguyeân döông. Chöùng minh raèng
(a, b) =
a neáu a = b
2(a/2, b/2) neáu a, b cuøng chaün (a/2, b) neáu a chaün vaø b leû
(a − b, b) neáu a, b cuøng leû vaø a > b.
AÙp duïng ñeå tìm (2106, 8318).
9. Giaû söû a, m, n laø caùc soá nguyeân döông vaø a > 1. Chöùng minh raèng (am − 1, an − 1) = a(m,n) − 1.
10. Chöùng toû raèng neáu m, n laø caùc soá nguyeân döông thì (fm, fn) = f(m,n), trong ñoù fk laø soá Fibonacci thöù k.
11. Phaân tích caùc soá 111111, 4849845 ra thöøa soá nguyeân toá.
Giaû söû p laø soá nguyeân toá vaø n laø soá nguyeân döông. Neáu pα | n, nhöng pα+1 n, ta noùi pα chia heát ñuùng n, kyù hieäu pα n.
12. Chöùng minh raèng neáu pa m vaø pb n thì pa+b mn. 13. Chöùng minh raèng neáu pa m vaø pb n, vôùi a = b thì pmin{a,b} m + n.
14. Giaû söû a, b, c laø caùc soá nguyeân. Chöùng toû raèng [a, b] | c khi vaø chæ khi a | c vaø b | c.
2.4. PHÖÔNG TRÌNH DIOPHANTUS TUYEÁN TÍNH 23
15. Chöùng minh raèng neáu p laø soá nguyeân toá, a, n laø soá nguyeân vaø p | an, n> 0, thì p | a.
16. a) Chöùng minh raèng neáu a, b laø caùc soá nguyeân döông vôùi (a, b)=1 thì (an, bn)=1 vôùi moïi soá töï nhieân n.
b) Chöùng minh raèng neáu an | bn vôùi soá nguyeân döông n thì a | b.
17. a) Giaû söû a | c, b | c. Chöùng minh raèng [a, b] | c.
b) Giaû söû aj | c, 1 ≤ j ≤ k. Chöùng minh raèng [a1, a2, ..., ak] | c.
18. Chöùng minh raèng neáu a, b, c laø caùc soá nguyeân döông thì [a, b, a] = [a, [b, c]], ([a, b], c) = [(a, c),(b, c)], [(a, b), c] = ([a, c], [b, c]).
19. Chöùng minh raèng neáu a, b, c laø caùc soá nguyeân döông thì [a, b, c] = abc(a, b, c)
(a, b)(a, c)(b, c).
20. Chöùng minh raèng neáu a, b, c laø caùc soá nguyeân döông thì (a, b, c)[ab, ac, bc] = abc, [a, b, c](ab, ac, bc) = abc.
21. Chöùng minh raèng neáu a, b, c laø caùc soá nguyeân döông thì ([a, b], [a, c], [b, c]) = [(a, b),(a, c),(b, c)].
22. Chöùng minh raèng coù voâ soá soá nguyeân toá daïng 4k − 1, k ∈ Z. 23. Giaûi phöông trình Diophantus:
a) 12x + 15y = 50 b) 3x + 4y = 7
c) 30x + 47y = −11 d) 102x + 1001y = 1
24. Tìm taát caû caùc nghieäm nguyeân cuûa phöông trình:
a) 2x + 3y + 4z = 5; b) 7x + 21y + 35z = 8; c) 101x + 102y + 103z = 1 25. Giaûi heä phöông trình Diophantus:
x + y + z = 100
a)
x + 8y + 50z = 156 b)
x + y + z = 100 x + 6y + 21z = 121
26. Tìm taát caû caùc nghieäm cuûa phöông trình Diophantus 1x+1y = 114.
24 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.
3
ÑOÀNG DÖ
3.1 Khaùi nieäm ñoàng dö
Giaû söû m laø soá nguyeân döông vaø a, b laø caùc soá nguyeân. Chuùng ta seõ noùi a ñoàng dö vôùi b modulo m neáuu m | (a − b).
Neáu a ñoàng dö vôùi b modulo m, ta vieát a ≡ b (mod m). Ngöôïc laïi, ta noùi a khoâng ñoàng dö vôùi b modulo m, kyù hieäu a ≡ b (mod m).
Ví duï 3.1.1. 22 ≡ 4 (mod 9) vì 9 | (22 − 4) = 18; −24 ≡ 3 (mod 9) vì 9 | (−24 − 3) = −27; 13 ≡ 5 (mod 9) vì 9 (13 − 5) = 8; 24 ≡ −5 (mod 9) vì 9 24 − (−5) = 29.
Deã daøng thaáy raèng, a ≡ b (mod m) khi vaø chæ khi coù soá nguyeân k sao cho a = b + km.
Ñònh lyù 3.1. Ñoàng dö modulo m laø quan heä töông döông treân Z, töùc laø coù caùc tính chaát:
1. Phaûn xaï: a ≡ a (mod m);
2. Ñoái xöùng: a ≡ b (mod m) ⇒ b ≡ a (mod m);
3. Baéc caàu: a ≡ b (mod m), b ≡ c (mod m) ⇒ a ≡ c (mod m). Chöùng minh. Ñaây laø baøi taäp deã, daønh cho ñoïc giaû.
25
26 3. ÑOÀNG DÖ
Quan heä ñoàng dö modulo m chia Z thaønh caùc lôùp töông ñöông. Taäp caùc lôùp töông ñöông modulo m, thöôøng ñöôïc kyù hieäu laø Z/mZ, goàm caùc lôùp töông ñöông ñoâi moät khoâng giao nhau.
Hieån nhieân laø caùc soá nguyeân 0, 1, ..., m − 1 thuoäc veà caùc lôùp ñoàng dö khaùc nhau modulo m. Vì raèng moãi soá nguyeân n ñeàu vieát ñöôïc n = mq+r, 0 ≤ r ≤ m − 1, neân soá n naøy ñoàng dö vôùi moät trong caùc soá 0, 1, ..., m − 1. Vaäy coù ñuùng m lôùp töông ñöông modulo m.
Ví duï 3.1.2. Z/4Z goàm boán lôùp töông ñöông ñoâi moät khoâng giao nhau: ···≡−8 ≡ −4 ≡ 0 ≡ 4 ≡ 8 ≡··· (mod 4)
···≡−7 ≡ −3 ≡ 1 ≡ 5 ≡ 9 ≡··· (mod 4)
···≡−6 ≡ −2 ≡ 2 ≡ 6 ≡ 10 ≡··· (mod 4)
···≡−5 ≡ −1 ≡ 3 ≡ 7 ≡ 11 ≡··· (mod 4).
Ñònh lyù 3.2. Giaû söû a, b, c, m laø caùc soá nguyeân, m > 0 vaø a ≡ b (mod m). Khi ñoù:
1. a + c ≡ b + c (mod m)
2. a − c ≡ b − c (mod m)
3. ac ≡ bc (mod m)
Chöùng minh. Deã, ñoïc giaû töï chöùng minh, xem nhö baøi taäp.
Chuù yù laø: Töø heä thöùc ac ≡ bc (mod m), noùi chung khoâng theå suy ra a ≡ b (mod m); chaúng haïn 6·2 ≡ 1·2 (mod 10), nhöng 6 ≡ 1 (mod 10). Tuy nhieân ta cuõng coù ñònh lyù sau.
Ñònh lyù 3.3. Neáu ac ≡ bc (mod m), d = (c, m) thì a ≡ b (mod m/d). Ñaëc bieät, neáu ac ≡ bc (mod m), (c, m)=1 thì a ≡ b (mod m).
Chöùng minh. Töø ac ≡ bc (mod m), ta suy ra m | (ac − bc) = c(a − b). Vaäy coù soá nguyeân k ñeå c(a − b) = km. Suy ra (c/d)(a − b) = k(m/d), hay (m/d) | (c/d)(a − b). Vì (m/d, c/d)=1 neân (m/d) | (a − b), hay a ≡ b (mod m/d).
3.1. KHAÙI NIEÄM ÑOÀNG DÖ 27 Ñònh lyù 3.4. Neáu a ≡ b (mod m) vaø c ≡ d (mod m) thì:
1. a + c ≡ b + d (mod m)
2. a − c ≡ b − d (mod m)
3. ac ≡ bd (mod m)
Chöùng minh. Töø ñònh lyù 3.2 ta coù
1. a + c ≡ b + c (mod m) ≡ b + d (mod m)
2. a − c ≡ b − c (mod m) ≡ b − d (mod m)
3. ac ≡ bc (mod m) ≡ bd (mod m)
Töø ñònh lyù treân, ta coù theå ñònh nghóa pheùp coäng vaø pheùp nhaân treân Z/mZ nhö sau.
Giaû söû A vaø B laø caùc lôùp ñoàng dö modulo m, töông öùng chöùa caùc phaàn töû a vaø b. Khi ñoù A + B vaø A · B ñöôïc hieåu laø caùc lôùp ñoàng dö modulo m, töông öùng chöùa caùc phaàn töû a + b vaø ab.
Deã daøng thaáy raèng (Z/mZ, +, ·) laø moät vaønh giao hoaùn. Phaàn töû 0 cuûa nhoùm naøy chính laø lôùp goàm caùc boäi cuûa m. Phaàn töû ñoái cuûa lôùp chöùa a chính laø lôùp chöùa −a.
Ñònh lyù 3.5. Neáu m1, m2, ..., mk laø caùc soá nguyeân döông vaø a ≡ b (mod m1), a ≡ b (mod m2), ..., a ≡ b (mod mk) thì a ≡ b (mod [m1, m2, ..., mk]).
Chöùng minh. Ta coù mj | (a − b), 1 ≤ j ≤ k. Töø baøi taäp 17, ta coù [m1, m2, ..., mk] | (a − b), hay a ≡ b (mod [m1, m2, ..., mk]).
28 3. ÑOÀNG DÖ 3.2 Caùc ñoàng dö tuyeán tính
Trong muïc naøy chuùng ta chæ xeùt caùc ñoàng dö tuyeán tính moät bieán. Ñoù laø caùc ñoàng dö daïng
ax ≡ b (mod m)
trong ñoù x ñöôïc hieåu laø soá nguyeân.
Tröôùc heát ta coù nhaän xeùt raèng, neáu x = x0 laø nghieäm cuûa ñoàng dö ax ≡ b (mod m) vaø x1 ≡ x0 (mod m) thì ax1 ≡ ax0 ≡ b (mod m), hay x − 1 cuõng laø moät nghieäm. Nhö vaäy, neáu moät phaàn töû cuûa lôùp ñoàng dö modulo m laø nghieäm thì taát caû caùc phaàn töû cuûa lôùp naøy cuõng laø nghieäm. Töø ñaây, vaán ñeà ñöôïc ñaët ra laø: coù bao nhieâu lôùp ñoàng dö modulo m laø nghieäm.
Ñònh lyù 3.6. Giaû söû a, b, m laø caùc soá nguyeân, m > 0 vaø d = (a, m). Khi ñoù: 1. Neáu d b thì ax ≡ b (mod m) khoâng coù nghieäm
2. Neáu d | b thì ax ≡ b (mod m) coù ñuùng d nghieäm khoâng ñoàng dö nhau modulo m. Ñaëc bieät, neáu (a, m)=1 thì ax ≡ b (mod m) coù duy nhaát nghieäm modulo m.
Chöùng minh. Ñoàng dö ax ≡ b (mod m) laø töông ñöông vôùi phöông trình Diophantus tuyeán tính hai bieán ax − my = b. Soá nguyeân x laø nghieäm cuûa phöông trình ax ≡ b (mod m), khi vaø chæ khi, coù soá soá nguyeân y vôùi ax − my = b. Töø ñònh lyù 2.8 ta coù:
1. Neáu d b thì ax ≡ b (mod m) khoâng coù nghieäm.
2. Neáu d | b thì ax − my = b coù caùc nghieäm laø
x = x0 + (m/d)t, y = y0 + (a/d)t
trong ñoù x0, y0 laø moät nghieäm rieâng.
Vaäy x = x0+(m/d)t laø taát caû caùc nghieäm cuûa ñoàng dö ax ≡ b (mod m).
Baây giôø chuùng ta xaùc ñònh soá caùc nghieäm x khoâng ñoàng dö nhau modulo m. Ta thaáy:
x1 = x0 + (m/d)t1 ≡ x2 = x0 + (m/d)t2 (mod m)
3.2. CAÙC ÑOÀNG DÖ TUYEÁN TÍNH 29
khi vaø chæ khi
(m/d)t1 ≡ (m/d)t2 (mod m)
Vì (m/d, m) = m/d vaø dònh lyù 3.3 neân heä thöùc treân töông ñöông vôùi t1 ≡ t2 (mod d).
Do coù ñuùng d lôùp ñoàng dö modulo d neân ax ≡ b (mod m) coù ñuùng d nghieäm khoâng ñoàng dö nhau modulo m. Coù theå laáy d nghieäm khoâng ñoàng dö nhau modulo m laøx = x0 + (m/d)tj , 0 ≤ j ≤ d − 1.
Ta ñaõ bieát, ñoàng dö ax ≡ 1 (mod m) coù nghieäm khi vaø chæ khi (a, m) | 1. Trong tröôøng hôïp naøy nghieäm laø duy nhaát modulo m vaø noù ñöôïc goïi laø nghòch cuûa a modulo m.
Ví duï 3.2.1. Nghòch ñaûo cuûa 3 modulo 10 baèng 7, vaø ngöôïc laïi, nghòch ñaûo cuûa 7 modulo 10 baèng 3, vì 3 · 7=7 · 3 ≡ 1 (mod 10). Nghòch ñaûo cuûa 1 vaø cuûa 9 modulo 10 baèng chính noù vì 1 · 1 ≡ 1 (mod 10) vaø 9 · 9 ≡ 1 (mod 10). Caùc soá 0, 2, 4, 5, 6, 8 khoâng coù nghòch ñaûo modulo 10.
Giaû söû a laø nghòch ñaûo cuûa a modulo m. Khi ñoù deã daøng thaáy raèng ñoàng dö ax ≡ b (mod m) coù nghieäm duy nhaát modulo m, ñoù laø x ≡ ab (mod m).
Ví duï 3.2.2. Chuùng ta caàn xaùc ñònh taát caû caùc nghieäm cuûa ñoàng dö 7x ≡ 4 (mod 12). Vì (7, 12) = 1 neân phöông trình coù duy nhaát nghieäm modulo 12. Chuùng ta chæ caàn xaùc ñònh moät nghieäm cuûa phöông trình Diophantus 7x + 12y = 4. AÙp duïng thuaät toaùn Euclid, ta coù:
12 = 7 · 1+5,
7=5 · 1+2,
5=2 · 2+1,
2=1 · 1.
Suy ra
1=5 − 2 · 2
30 3. ÑOÀNG DÖ
= 5 − (7 − 5 · 1) · 2
= 5 · 3 − 2 · 7
= (12 − 7 · 1) · 3 − 2 · 7
= 12 · 3 − 5 · 7.
Hay: 1 = 12 · 3 − 7 · 5. Suy ra nghòch ñaûo cuûa 7 modulo 12 baèng −5.
Vaäy x ≡ −5 · 4 = −20 ≡ 4 (mod 12) laø nghieäm duy nhaát cuûa 7x ≡ 4 (mod 12).
3.3 Ñònh lyù phaàn dö Trung hoa
Ñònh lyù 3.7. Ñònh lyù phaàn dö Trung hoa. Giaû söû m1, m2, ..., mk laø caùc soá nguyeân döông ñoâi moät nguyeân toá cuøng nhau. Khi ñoù heä caùc ñoàng dö
x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)
coù duy nhaát nghieäm modulo M = m1m2...mk.
Chöùng minh. Ñaët Mj = M/mj , 1 ≤ j ≤ k. Khi ñoù, do (Mj , mj )=1 neân coù soá nguyeân yj thoaû ñoàng dö Mjyj ≡ 1 (mod mj ). Ñaët
x = a1M1y1 + a2M2y2 + ··· + akMkyk.
Do mj | Mi, vôùi moïi i = j, neân: x ≡ ajMjyj ≡ aj (mod mj ), 1 ≤ j ≤ k.
Baây giôø giaû söû x1, x2 laø caùc nghieäm cuûa heä. Theá thì vôùi moïi j, 0 ≤ j ≤ k, ta ñeàu coù x1 ≡ x2 (mod mj ). Suy ra, vôùi moïi j, 0 ≤ j ≤ k, mj | (x1−x2). Vì caùc soá m1, m2, ..., mk ñoâi moät nguyeân toá cuøng nhau neân M = m1, m2, ..., mk | (x1 − x2); hay x1 ≡ x2 (mod M).
3.4. HEÄ CAÙC ÑOÀNG DÖ TUYEÁN TÍNH 31
Ví duï 3.3.1. Giaûi heä
x ≡ 1 (mod 3) x ≡ 2 (mod 5) x ≡ 3 (mod 7)
Do caùc soá 3, 5, 7 laø ñoâi moät nguyeân toá cuøng nhau, neân ta ñaët M1 = 5 · 7 = 35, M2 = 3 · 7 = 21, M3 = 3 · 5 = 15. Giaûi caùc ñoàng dö
35y1 ≡ 1 (mod 3)
21y2 ≡ 1 (mod 5)
15y3 ≡ 1 (mod 7)
ta ñöôïc y1 = 2, y2 = 1, y3 = 1. Vaäy heä ban ñaàu coù coù duy nhaát nghieäm x = 1 · 35 · 2+2 · 21 · 1+3 · 15 · 1 ≡ 52 (mod M = 3 · 5 · 7 = 105).
3.4 Heä caùc ñoàng dö tuyeán tính
Trong muïc naøy chuùng ta chæ xeùt heä caùc ñoàng dö tuyeán tính daïng
a11x1 + a12x2 + ··· + a1nxn ≡ b1 (mod m) a21x1 + a22x2 + ··· + a2nxn ≡ b2 (mod m) ...
an1x1 + an2x2 + ··· + annxn ≡ bn (mod m)
Heä treân coù theå vieát moät caùch ngaén goïn laø AX ≡ B (mod m), neáu duøng kyù
hieäu ma traän: A =
a11 a12 ··· a1n
a21 a22 ··· a2n ...
an1 an2 ··· ann
, X =
x1
x2...
xn
, B =
b1
b2...
bn
.
Tröôùc heát, chuùng ta ñöa ra quan heä ñoàng dö modulo m treân caùc ma traän soá nguyeân.
Ma traän A = (aij )n×n ñöôïc goïi laø ñoàng dö vôùi ma traän B = (bij )n×n modulo m, kyù hieäu A ≡ B (mod m), neáuu vôùi moïi i, j : 1 ≤ i, j ≤ n, ta ñeàu coù aij ≡ bij (mod m). Ñoïc giaû töï chöùng minh raèng ñaây laø quan heä töông ñöông.
32 3. ÑOÀNG DÖ
Ñònh lyù 3.8. Giaû söû A = (aij ), B = (bij ), C = (cij ), D = (dij ) laø caùc ma traän nguyeân, caáp n × n, A ≡ B (mod m) vaø C ≡ D (mod m). Khi ñoù:
1. A + C ≡ B + D (mod m)
2. A − C ≡ B − D (mod m)
3. AC ≡ BD (mod m)
Chöùng minh. Töông töï nhö trong chöùng minh ñònh lyù 3.4, ta chæ caàn chöùng minh A + C ≡ B + C (mod m) vaø AC ≡ BC (mod m).
1. Töø ñònh lyù 3.2, ta coù aij + cij ≡ bij + cij (mod m). Vaäy A + C ≡ B + C (mod m).
2. Theo ñònh lyù 3.2 thì aikckj ≡ bikckj (mod m). AÙp duïng ñònh lyù 3.4, ta
coùn k=1
n
aikckj ≡ k=1
bikckj (mod m);
suy ra AC ≡ BC (mod m).
Giaû söû ma traän A laø ma traän nguyeân caáp n × n. Ma traän nguyeân B ñöôïc goïi laø nghòch ñaûo cuûa A modulo m, kyù hieäu A, neáuu AB ≡ BA ≡ I = (δij)n×n (mod m). Ñoïc giaû coù theå töï chöùng minh raèng: neáu B ≡ A (mod m) thì B laø nghòch ñaûo cuûa A; ngöôïc laïi, neáu B1, B2 ñeàu laø caùc nghòch ñaûo cuûa A thì B1 ≡ B2 (mod m).
Ñoái vôùi ma traän A caáp n×n, chuùng ta kyù hieäu adjA laø ma traän caáp n×n, vôùi phaàn töû cij laø tích cuûa (−1)i+j vôùi ñònh thöùc cuûa ma traän nhaän ñöôïc töø A baèng caùch boû ñi phaàn töû doøng j coät i.
Ñònh lyù 3.9. Giaû söû A laø ma traän nguyeân caáp n×n, (det A, m)=1, vaø ∆ laø nghòch ñaûo modulo m cuûa ∆ = det A. Theá thì A = ∆(adjA), laø nghòch ñaûo cuûa A modulo m.
Chöùng minh. Ta coù
A · adjA = adjA · A = (det A)I = ∆I.
3.4. HEÄ CAÙC ÑOÀNG DÖ TUYEÁN TÍNH 33
Suy ra
AA = AA = ∆(adjA)A = ∆∆I ≡ I (mod m).
Ví duï 3.4.1. Giaû söû coù ma traän: A = 7 = det A modulo 13, neân ta coù
3 4 2 5
. Vì 2 laø nghòch ñaûo cuûa
A = 2
5 −4 −2 3
=
10 −8 −4 6
≡
10 5 9 6
(mod 13).
Ñònh lyù 3.10. Giaû söû A laø ma traän nguyeân caáp n × n, (det A, m)=1. Khi ñoù heä phöông trình ñoàng dö AX ≡ B (mod m) coù duy nhaát nghieäm X ≡ AB (mod m).
Chöùng minh. X ≡ AB (mod m) laø nghieäm cuûa heä vì AX ≡ A(AB) = (AA)B ≡ B (mod m).
Ngöôïc laïi, neáu X laø moät nghieäm cuûa heä AX ≡ B (mod m) thì baèng caùch nhaân traùi caùc veá vôùi A, ta ñöôïc
A(AX) ≡ AB (mod m); vaäy X ≡ (AA)X = A(AX) ≡ AB (mod m).
Ví duï 3.4.2. Xeùt heä ba ñoàng dö
2x1 + 5x2 + 6x3 ≡ 3 (mod 7) 2x1 + x3 ≡ 4 (mod 7)
x1 + 2x2 + 3x3 ≡ 1 (mod 7)
Ta coù det A = −5, (det A, 7) = 1. Nghòch ñaûo cuûa det A modulo 7 baèng 4.
Nghòch ñaûo cuûa A = Vaäy heä coù nghieäm laø
256 201 123
laø A = 4
−2 −3 5 −5 0 10 4 1 −10
(mod 7).
x1 x2 x3
≡ 4
−2 −3 5 −5 0 10 4 1 −10
·
3 4 1
=
−52 −20 24
≡
4 1 3
(mod 7).
34 3. ÑOÀNG DÖ 3.5 Ñònh lyù Wilson vaø ñònh lyù Euler
Ñònh lyù 3.11. Ñònh lyù Wilson. Neáu p laø soá nguyeân toá thì (p − 1)! ≡ −1 (mod p).
Chöùng minh. Ñònh lyù laø ñuùng trong tröôøng hôïp p = 2, 3. Ta xeùt tröôøng hôïp p > 3.
Ñoái vôùi moãi soá nguyeân a, 2 ≤ a ≤ p − 2, do (a, p)=1 neân töø ñònh lyù 3.6 suy ra a coù nghòch ñaûo duy nhaát a modulo m : 1 ≤ a ≤ p − 1. Maët khaùc, a = a; vì neáu khoâng thì a2 ≡ 1 (mod p), suy ra (a − 1)(a + 1) | p, vaø ñieàu naøy khoâng theå xaûy ra vôùi 2 ≤ a ≤ p − 2. Vaäy thì, baèng caùch nhoùm töøng caëp a vaøa ta döôïc
2 · 3 · (p − 3)(p − 2) ≡ 1 (mod p).
Nhaân caùc veá vôùi (p − 1) ta coù
(p − 1)! ≡ 1 · (p − 1) ≡ −1 (mod p).
Ñònh lyù Wilson neâu leân ñaëc tröng cuûa soá nguyeân toá vì ñaûo laïi cuûa noù vaãn ñuùng.
Ñònh lyù 3.12. Neáu soá nguyeân n > 1 maø (n − 1)! ≡ −1 (mod n) thì n laø soá nguyeân toá.
Chöùng minh. Giaû söû n laø hôïp soá; ta coù n = ab vôùi 1 < a, b < n. Ta coù a | (n − 1)! vì 1 < a < n. Maët khaùc, vì a | n vaø n | (n − 1)! + 1, ta suy ra a | (n − 1)! + 1 − (n − 1)! = 1, vaø ñieàu naøy khoâng theå xaûy ra vôùi a > 1.
Giaû söû m laø soá nguyeân döông vaø a = bm + r, 0 ≤ r ≤ m − 1, ta seõ noùi raèng r laø thaëng dö khoâng aâm nhoû nhaát cuûa a modulo m, kyù hieäu: a mod m = r. Ví duï, 17 mod 5 = 2; −8 mod 7=6.
Taäp caùc soá nguyeân ñöôïc goïi laø heä thaëng dö ñaày ñuû modulo m neáuu moïi soá nguyeân ñeàu ñoàng dö modulo m vôùi ñuùng moät soá nguyeân cuûa heä.
Deã daøng thaáy raèng: moät heä caùc soá nguyeân laø thaëng dö ñaày ñuû modulo m khi vaø chæ khi heä naøy coù ñuùng m soá ñoâi moät khoâng ñoàng dö vôùi nhau modulo m.
3.5. ÑÒNH LYÙ WILSON VAØ ÑÒNH LYÙ EULER 35
Ví duï 3.5.1. Neáu m laø soá nguyeân döông thì:
1. Heä 0, 1, ..., m − 1 laø moät heä thaëng dö ñaày ñuû modulo m; chuùng ta seõ goïi heä naøy laø heä thaëng dö khoâng aâm nhoû nhaát modulo m.
2. Neáu m laø soá leû thì heä
−m − 1
2 , −m − 3
2 , ..., −1, 0, 1, ..., m − 1
2
cuõng laø heä thaëng dö ñaày ñuû modulo m; heä naøy ñöôïc goïi laø heä thaëng dö tuyeät ñoái nhoû nhaát modulo m.
Ñònh lyù 3.13. Neáu caùc soá r1, r2, ..., rm laø moät heä thaëng dö ñaày ñuû modulo m vaø a nguyeân toá cuøng nhau vôùi m thì heä
ar1 + b, ar2 + b, ··· , arm + b
cuõng laø moät heä thaëng dö ñaày ñuû modulo m.
Chöùng minh. Chuùng ta chæ caân chöùng minh raèng, neáu 1 ≤ i 0. Chöùng minh raèng neáu a ≡ b (mod c) thì (a, c)=(b, c).
2. Giaû söû a, b, k, m laø caùc soá nguyeân, k,m > 0, (a, m)=1. Chöùng minh raèng neáu ak ≡ bk (mod m) vaø ak+1 ≡ bk+1 (mod m) thì a ≡ b (mod m)
3. Chöùng minh raèng neáu p nguyeân toá vaø k nguyeân döông thì nghieäm duy nhaát cuûa ñoàng dö x2 ≡ x (mod pk) laø x ≡ 0 hoaëc x ≡ 1 (mod pk).
4. Giaû söû m1, m2, ..., mk laø caùc soá nguyeân döông ñoâi moät nguyeân toá cuøng nhau, M = m1m2 ··· mk vaø Mj = M/mj . Chöùng minh raèng
M1a1 + M2a2 + ··· + Mkak
chaïy treân heä thaëng dö ñaày ñuû modulo M khi a1, a2, ..., ak töông öùng chaïy treân heä thaëng dö ñaày ñuû modulo m1, m2, ··· , mk.
5. Chöùng minh raèng vôùi moãi soá nguyeân döông m ñeàu coù voâ soá soá Fibonacci fn laø boäi cuûa m.
6. Giaûi caùc ñoàng dö sau
a) 19x ≡ 30 (mod 40) b) 103x ≡ 444 (mod 999) c) 980x ≡ 1500 (mod 1600) d) 3x ≡ 2 (mod 7) e) 6x ≡ 3 (mod 9) f) 17x ≡ 14 (mod 21) g) 15x ≡ 9 (mod 25) h) 128x ≡ 833 (mod 1001)
7. Giaûi caùc ñoàng dö hai bieán sau
a) 2x + 3y ≡ 1 (mod 7) b) 2x + 4y ≡ 6 (mod 8) c) 6x + 3y ≡ 0 (mod 9) d) 10x + 5y ≡ 9 (mod 15)
8. Giaû söû p laø nguyeân toá leû vaø k nguyeân döông. Chöùng minh raèng ñoàng dö x2 ≡ 1 (mod pk) coù ñuùng hai nghieäm khoâng ñoàng dö nhau modulo pk, ñoù laø x ≡ ±1 (mod pk).
9. Chöùng minh raèng ñoàng dö x2 ≡ 1 (mod 2k) coù ñuùng boán nghieäm khoâng ñoàng dö nhau modulo 2k, ñoù laø x ≡ ±1 (mod pk) hoaëc x ≡ ±(1 + 2k−1 (mod pk) khi k > 2. Chöùng toû raèng khi k = 1 thì chæ coù moät nghieäm vaø khi k = 2 thì coù ñuùng hai nghieäm khoâng ñoàng dö nhau.
3.5. ÑÒNH LYÙ WILSON VAØ ÑÒNH LYÙ EULER 39
10. Giaû söû p laø nguyeân toá leû vaø a nguyeân döông khoâng chia heát cho p. Chöùng minh raèng ñoàng dö x2 ≡ a (mod p) khoâng coù nghieäm hoaëc coù ñuùng hai nghieäm khoâng ñoàng dö nhau modulo p.
11. Giaûi caùc heä ñoàng dö sau
x ≡ 4 (mod 11)
a)
x ≡ 3 (mod 17) b)
x ≡ 1 (mod 2) x ≡ 2 (mod 3) x ≡ 3 (mod 5)
12. Chöùng minh raèng heä ñoàng dö
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
coù nghieäm khi vaø chæ khi (m1, m2) | (a1 − a2); trong tröông hôïp coù nghieäm thì nghieäm laø duy nhaát modulo [m1, m2].
Haõy phaùt trieån cho baøi toaùn toång quaùt
13. Giaûi caùc heä ñoàng dö sau
x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)
x + 3y ≡ 1 (mod 5)
a)
3x + 4y ≡ 2 (mod 5) b) 2x + 3y ≡ 5 (mod 7)
c)
x + 5y ≡ 6 (mod 7) d)
4x + y ≡ 2 (mod 5) 2x + 3y ≡ 1 (mod 5) 4x + y ≡ 5 (mod 7) x + 2y ≡ 4 (mod 7)
40 3. ÑOÀNG DÖ 14. Giaûi caùc heä ñoàng dö sau
a) b) c)
2x + 3y + z ≡ 3 (mod 5) x + 2y + 3z ≡ 1 (mod 5) 2x + z ≡ 1 (mod 5)
3x + y + 3z ≡ 1 (mod 7) x + 2y + 4z ≡ 2 (mod 7) 4x + 3y + 2z ≡ 3 (mod 7)
2x + y + z ≡ 3 (mod 11) x + 2y + z ≡ 1 (mod 11) x + y + 2z ≡ 2 (mod 11)
15. Baèng caùch söû duïng ñònh lyù Wilson haõy chöùng toû raèng neáu p laø soá nguyeân toá vaø p ≡ 1 (mod 4) thì ñoàng dö x2 ≡ −1 (mod p) coù hai nghieäm khoâng ñoàng dö nhau laø x ≡ ±((p − 1)/2)! (mod p).
16. Chöùng minh raèng neáu p laø soá nguyeân toá vaø a laø soá nguyeân thì p | (ap + (p − 1)! a).
17. Chöùng minh raèng neáu p nguyeân toá vaø 0 2 vaø c1, c2, ··· , cϕ(m) laø heä thaëng dö thu goïn modulo m thì c1 + c2 + ··· + cϕ(m) ≡ 0 (mod m).
26. Chöùng toû raèng
x ≡ a1Mϕ(m1)
1 + a2Mϕ(m2)
2 + ··· + akMϕ(mk)
k (mod M)
laø nghieäm duy nhaát cuûa heä ñoàng dö
x ≡ a1 (mod m1) x ≡ a2 (mod m2) ... x ≡ ak (mod mk)
trong ñoù caùc mj ñoâi moät nguyeân toá cuøng nhau, M = m1m2 ··· mk, Mj = M/mj , 1 ≤ j ≤ k.
42 3. ÑOÀNG DÖ
4
CAÙC HAØM SOÁ HOÏC
4.1 Nhaän xeùt chung
Haøm soá hoïc laø haøm nhaän giaù trò thöïc hoaëc phöùc vaø xaùc ñònh treân taäp soá nguyeân döông.
Haøm soá hoïc f khoâng ñoàng nhaát baèng 0, ñöôïc goïi laø coù tính nhaân neáuu f(mn) = f(m)f(n), vôùi (m, n)=1. Haøm soá hoïc f khoâng ñoàng nhaát baèng 0, ñöôïc goïi laø coù tính nhaân ñaày ñuû neáuu f(mn) = f(m)f(n), vôùi moïi soá nguyeân döông m, n.
Hieån nhieân, haøm coù tính nhaân ñaày ñuû laø haøm coù tính nhaân. Haøm f coù tính nhaân thì f(1) = 1.
Ví duï 4.1.1. Haøm ñoàng nhaát baèng moät, f(n)=1 vôùi moïi n, coù tính nhaân ñaày ñuû, vì f(mn)=1= f(m)f(n). Haøm ñoàng nhaát, f(n) = n vôùi moïi n, cuõng coù tính nhaân ñaày ñuû, vì f(mn) = mn = f(m)f(n).
Coù nhieàu haøm soá hoïc laø khoâng chính qui. Bôûi theá ngöôøi ta thöôøng khoâng xeùt haøm soá hoïc f maø xeùt haøm toång cuûa noù, ñoù laø
F(N) =
N
f(n).
n=1
Sau ñaây laø moät soá tính chaát cuûa haøm soá hoïc coù tính nhaân. 43
44 4. CAÙC HAØM SOÁ HOÏC
Ñònh lyù 4.1. Giaû söû f laø haøm coù tính nhaân vaø n = pα1
2 ··· pαk
luõy thöøa nguyeân toá cuûa soá nguyeân döông n thì
1 pα2
k laø khai trieån
f(n) = f(pα1
2 )··· f(pαk
1 )f(pα2
k ).
Chöùng minh. Vì i = j thì pi vaø pj laø caùc soá nguyeân toá khaùc nhau, ta suy ra 2 ··· pαk−1
(pα1
1 pα2
k−1 , pαk
k )=1, töø ñoù
2 ··· pαk−1
2 ··· pαk−1
f(pα1
1 pα2
k−1 pαk
k ) = f(pα1
1 pα2
k−1 )f(pαk
k ).
Ñònh lyù 4.2. Neáu f coù tính nhaân thì haøm g(n) =
d|n
cuõng coù tính nhaân.
f(d)
Chöùng minh. Haøm g khoâng ñoàng nhaát baèng khoâng, vì
g(1) =
d|1
r vaø n = qβ1
f(1) = 1.
Giaû söû m = pα1
1 pα2
2 ··· pαr
1 qβ2
2 ··· qβs
s laø khai trieån luõy thöøa nguyeân
toá töông öùng cuûa caùc soá nguyeân döông m vaø n. Neáu (m, n)=1 thì pi vaø qj laø caùc soá nguyeân toá khaùc nhau. Töø ñaây ta suy ra, moãi öôùc d cuûa
r qβ1
mn = pα1
1 pα2
2 ··· pαr
1 qβ2
2 ··· qβs
s
ñöôïc vieát moät caùch duy nhaát thaønh tích cuûa caùc öôùc nguyeân toá cuøng nhau d1 cuûa m vaø d2 cuûa n. Vaäy
g(mn) = d|mn
f(d) =
d1 | m
d2 | n
f(d1d2).
Vì f coù tính nhaân vaø (d1, d2)=1 neân f(d1d2) = f(d1)f(d2), suy ra
g(mn) =
d1 | m
d2 | n
f(d1)f(d2) = d1 | m
f(d1)
d2 | n
f(d2) = g(m)g(n).
4.1. NHAÄN XEÙT CHUNG 45
Ñònh lyù 4.3. Neáu haøm soá hoïc f coù tính nhaân vaø
f(pm) → 0 khi pm → ∞
trong ñoù p laø soá nguyeân toá vaø m laø soá nguyeân döông, thì
f(n) → 0 khi n → ∞.
Chöùng minh. Vì f(pm) → 0 khi pm → ∞ neân ta coù nhaän xeùt raèng f thoûa caùc ñieàu kieän sau:
1. Coù haèng soá döông A sao cho vôùi moïi m vaø p ta ñeàu coù |f(pm)| < A.
2. Coù haèng soá döông B sao cho
|f(pm)| < 1 neáu pm > B.
3. Vôùi moïi ε > 0 ñeàu coù soá N(ε), chæ phuï thuoäc vaøo ε, sao cho |f(pm)| < ε neáu pm > N(ε).
Giaû söû
n = pα1
2 ··· pαk
1 pα2
k
laø khai trieån luõy thöøa nguyeân toá cuûa soá nguyeân döông n > 1. Theá thì
f(n) = f(pα1
2 )··· f(pαk
1 )f(pα2
k ).
Vì chæ coù höõu haïn caùc soá daïng pα maø pα ≤ N(ε), neân ta suy ra raèng chæ coù höõu haïn caùc soá nguyeân maø taát caû caùc luõy thöøa nguyeân toá cuûa noù ñeàu khoâng vöôït quaù N(ε). Ñaët P(ε) laø caän treân cho caùc soá nguyeân nhö vaäy.
Neáu n>P(ε), thì trong khai trieån thaønh luõy thöøa nguyeân toá cuûa n phaûi coù ít nhaát moät thöøa soá pαi maø pαi > N(ε). Goïi C laø soá caùc luõy thöøa nguyeân toá pα maø pα ≤ B. Theá thì töø nhaän xeùt treân ta suy ra
|f(n)| < ACε.
46 4. CAÙC HAØM SOÁ HOÏC 4.2 Haøm Euler ϕ(n).
Phi-haøm Euler, kyù hieäu ϕ, ñöôïc xaùc ñònh bôûi: ϕ(n) laø soá caùc soá nguyeân döông khoâng vöôït quaù n vaø nguyeân toá cuøng nhau vôùi n.
Ñònh lyù 4.4. Phi-haøm Euler coù tính nhaân.
Boå ñeàù 4.4.1. Giaû söû m, n laø caùc soá nguyeân döông nguyeân toá cuøng nhau; {ai : 1 ≤ i ≤ m } vaø {bj : 1 ≤ j ≤ n } töông öùng laø caùc heä thaëng dö ñaày ñuû modulo m vaø n. Khi ñoù ta coù {ain + bjm : 1 ≤ i ≤ m, 1 ≤ j ≤ n } laø heä thaëng dö ñaày ñuû modulo mn.
Chöùng minh. Taäp {ain + bjm : 1 ≤ i ≤ m, 1 ≤ j ≤ n } coù caû thaûy mn soá nguyeân. Ta chæ coøn phaûi chöùng minh raèng caùc soá naøy ñoâi moät khoâng ñoàng dö nhau modulo mn.
Giaû söû ai1 n + bj1m ≡ ai2 n + bj2m (mod mn). Theá thì ai1 n + bj1m ≡ ai2 n+bj2m (mod m). Suy ra m | (ai1−ai2 )n. Do(m, n)=1 neân m | (ai1−ai2 ), hay ai1 ≡ ai2 (mod m). Vì {ai : 1 ≤ i ≤ m } laø heä thaëng dö ñaày ñuû neân i1 = i2. Töông töï, ta coù j1 = j2.
Chöùng minh. Baây giôø chuùng ta chöùng minh ñònh lyù.
Vì (m, n)=1 neân ϕ(mn) laø soá caùc phaàn töû cuûa heä {ain + bjm : 1 ≤ i ≤ m, 1 ≤ j ≤ n }, thoaû (ain+bjm, mn)=1. Nhöng (ain+bjm, mn)=1 töông ñöông vôùi
(ain + bjm, m)=1 (ain + bjm, n)=1 ⇔
(ain, m)=1 (bjm, n)=1 ⇔
(ai, m)=1 (bj , n)=1
Vì coù ϕ(m) caùc ai thoaû (ai, m)=1 vaø ϕ(n) caùc bj thoaû (bj , n)=1 neân coù caû thaûy ϕ(m)ϕ(n) caùc ain + bjm thoaû (ain + bjm, mn)=1.
Ñònh lyù 4.5. Neáu p nguyeân toá vaø α nguyeân döông thì ϕ(pα) = pα(1 − 1/p).
Chöùng minh. Caùc soá nguyeân döông khoâng vöôït quaù pα vaø khoâng nguyeân toá cuøng nhau vôùi pα chính laø caùc soá nguyeân döông khoâng vöôït quaù pα vaø chia heát cho p. Ñoù chính laø caùc soá kp maø 1 ≤ k ≤ pα−1. Coù caû thaûy pα−1 soá nhö vaäy, do ñoù ϕ(pα) = pα − pα−1 = pα(1 − 1/p).
Töø caùc ñòng lyù 4.1, 4.4,4.5 ta coù ngay ñònh lyù sau ñaây ñeå tính ϕ(n).
4.2. HAØM EULER ϕ(N). 47
Ñònh lyù 4.6. Neáu n = pα1
2 ··· pαk
nguyeân döông n thì
1 pα2
k laø khai trieån luõy thöøa nguyeân toá cuûa soá
ϕ(n) = n(1 − 1p1)(1 − 1p2)···(1 − 1pk).
Ví duï 4.2.1.
ϕ(100) = ϕ(2252) = 100(1 − 12)(1 − 15) = 40
vaø
ϕ(720) = ϕ(24325) = 720(1 − 12)(1 − 13)(1 − 15) = 192.
Töø ñònh lyù treân ta thaáy, neáu n = pm vôùi p > 1/ε laø soá nguyeân toá vaø
m ≥ 1, thì
n>ϕ(n) = n(1 − 1p) > n(1 − ε).
Töø ñaây ta nhaän ñöôïc ñònh lyù sau
Ñònh lyù 4.7.
limn→∞ϕ(n)
n= 1.
Tuy nhieân ta cuõng ñaùnh giaù ñöôïc caáp ñoä cuûa haøm ϕ.
Ñònh lyù 4.8. Vôùi baát kyø δ > 0 ta ñeàu coù
limn→∞ϕ(n)
n1−δ = ∞.
Chöùng minh. Vì haøm
f(n) = n1−δ
ϕ(n)
coù tính nhaân vaø do ñònh lyù 4.3 neân ta chæ caàn chöùng toû raèng f(pm) → 0 khi pm → ∞.
Thaät vaäy, ta coù
0 < f(pm) = pm(1−δ)
ϕ(pm) = pm−mδ
pm(1 − 1/p) = p−mδ
1 − 1/p ≤ 2(pm)−δ → 0 khi pm → ∞.
48 4. CAÙC HAØM SOÁ HOÏC
Ñònh lyù 4.9. Neáu n laø soá nguyeân döông thì
d|n
ϕ(d) = n.
Chöùng minh. Chuùng ta phaân caùc soá nguyeân m töø 1 ñeán n thaønh caùc lôùp Cd. Soá nguyeân m, 1 ≤ m ≤ n, thuoäc lôùp Cd neáuu (m, n) = d. Theá thì m ∈ Cd khi vaø chæ khi (m/d, n/d)=1. Nhö vaäy, moãi lôùp Cd coù ñuùng ϕ(n/d) soá. Vaäy
n =
d|n
ϕ(n/d) = d|n
ϕ(d).
4.3 Haøm toång caùc öôùc σ(n) vaø soá caùc öôùc τ (n).
Haøm toång caùc öôùc, kyù hieäu bôûi σ, ñöôïc xaùc ñònh bôûi: σ(n) laø toång taát caû caùc öôùc döông cuûa soá nguyeân döông n.
Haøm soá caùc öôùc, kyù hieäu bôûi τ, ñöôïc xaùc ñònh bôûi: τ (n) laø soá caùc öôùc döông cuûa soá nguyeân döông n.
Ví duï 4.3.1. σ(2) = 3, σ(3) = 4, σ(4) = 7, σ(5) = 6, σ(6) = 12, σ(7) = 8; τ (2) = 2, τ (3) = 2, τ (4) = 3, τ (5) = 2, τ (6) = 4, τ (7) = 2, τ (8) = 4.
Ñònh lyù 4.10. Caùc haøm σ vaø τ laø coù tính nhaân.
Chöùng minh. Caùc haøm f1(n) = n vaø haøm f2(n)=1 laø coù tính nhaân. Theo ñòng lyù 4.2, ta suy ra caùc haøm
σ(n) = d|n
d =
d|n
f1(d) ; τ (n) = d|n
1 =
d|n
f2(d)
laø coù tính nhaân.
Ñònh lyù 4.11. Neáu n = pα1
2 ··· pαk
nguyeân döông n thì
1 pα2
k laø khai trieån luõy thöøa nguyeân toá cuûa soá
σ(n) = k i=1
pi − 1 ; τ (n) = k
pαi+1
i − 1
i=1
(αi + 1).
4.3. HAØM TOÅNG CAÙC ÖÔÙC σ(N) VAØ SOÁ CAÙC ÖÔÙC τ (N). 49
Chöùng minh. 1. Vì pα chæ coù (α + 1) öôùc döông laø pi, 0 ≤ i ≤ α, neân σ(pα)=1+ p + ··· + pα = pα+1 − 1
p − 1 .
Vaäy
σ(n) = k i=1
i ) = k
σ(pαi
i=1
pαi+1 − 1 pi − 1 .
2. Vì pα chæ coù (α + 1) öôùc döông laø pi, 0 ≤ i ≤ α, neân τ (pα)=(α + 1). Vaäy
(αi + 1).
Ví duï 4.3.2.
τ (n) = k i=1
i ) = k
τ (pαi
i=1
σ(1955) = σ(5 · 17 · 23) = 52 − 1
5 − 1 ·172 − 1
17 − 1 ·232 − 1
23 − 1 = 2592
τ (1955) = τ (5 · 17 · 23) = (1 + 1)(1 + 1)(1 + 1) = 8
Töø ñònh lyù 4.11 ta thaáy τ (n) coù theå lôùn tuyø yù. Tuy nhieân ta coù Ñònh lyù 4.12. Vôùi baát kyø δ > 0 ta ñeàu coù
limn→∞τ (n)
nδ = 0.
Chöùng minh. Vì haøm
f(n) = τ (n)
nδ
coù tính nhaân vaø do ñònh lyù 4.3 neân ta chæ caàn chöùng toû raèng f(pm) → 0 khi pm → ∞.
Thaät vaäy, ta coù
0 < f(pm) = m + 1
pmδ ≤2m
log p·log pm
log 2·log pm
pmδ = 2
pmδ ≤2
pmδ → 0 khi pm → ∞.
50 4. CAÙC HAØM SOÁ HOÏC
Nhieàu vaán ñeà coù lieân quan ñeán haøm σ, chaúng haïn vaán ñeà veà soá hoaøn haûo. Ngöôøi coå Hylaïp goïi soá hoaøn haûo laø caùc soá maø σ(n)=2n.
Ví duï 4.3.3. Caùc soá 6 vaø 12 laø caùc soá hoaøn haûo, vì
σ(6) = 1 + 2 + 3 + 6 = 12,
σ(28) = 1 + 2 + 4 + 7 + 17 + 28 = 56.
Ñònh lyù 4.13. Soá nguyeân döông chaün n laø soá hoaøn haûo khi vaø chæ khi n = 2m(2m+1 − 1), trong ñoù m laø soá nguyeân döông vaø 2m+1 − 1 laø soá nguyeân toá.
Chöùng minh. ⇒ . Giaû söû n = 2mN laø soá hoaøn haûo chaün, m ≥ 1 vaø N laø soá leû. Do
σ(n) = σ(2mN) = σ(2m)σ(N) = (2m+1 − 1)σ(N),
vaø n = 2mN laø soá hoaøn haûo neân
(2m+1 − 1)σ(N)=2m+1N.
Vì (2m+1 − 1, 2m+1)=1, ta suy ra 2m+1 − 1 | N. Ñaët N = (2m+1 − 1)N , thì N < N, σ(N)=2m+1N . Nhöng N + N = 2m+1N = σ(N), vaø vì N,N ñeàu laø öôùc cuûaN neân N khoâng coøn öôùc naøo khaùc; vaäy N laø soá nguyeân toá vaø N = 1. Do ñoù N = (2m+1 − 1) laø soá nguyeân toá.
⇐ . Giaû söû n = 2m(2m+1 − 1), trong ñoù m laø soá nguyeân döông vaø p = 2m+1 − 1 laø soá nguyeân toá. Theá thì
σ(n) = σ(2m)σ(p) = (2m+1 − 1)(p + 1) = (2m+1 − 1)2m+1 = 2n. Vaäy n laø soá hoaøn haûo.
Nhö vaäy, vieäc tìm caùc soá hoaøn haûo chaün gaén lieàn vôùi vieäc tìm caùc soá nguyeân toá daïng 2m−1. Caùc soá nguyeân toá nhö vaäy ñöôïc goïi laø soá nguyeân toá Mersenne.
4.4. HAØM MO¨BIUS µ(N). 51 4.4 Haøm Mo¨bius µ(n).
Haøm Mo¨bius, kyù hieäu µ, ñöôïc xaùc ñònh bôûi:
i) µ(1) = 1;
ii) µ(n)=(−1)k, neáu n laø tích cuûa k soá nguyeân toá khaùc nhau; iii) µ(n)=0, neáu n coù öôùc chính phöông khaùc 1.
Töø ñònh nghóa ta coù ngay ñònh lyù sau ñaây
Ñònh lyù 4.14. Haøm Mo¨bius µ coù tính nhaân.
Ñònh lyù 4.15.
d|n
µ(d) =
1, neáu n = 1, 0, neáu n > 1.
Chöùng minh. Giaû söû n = pα1
1 pα2
2 ··· pαm
m laø khai trieån luõy thöøa nguyeân toá cuûa
soá nguyeân döông n > 1. Öôùc d cuûa n maø µ(d) = 0 coù daïng 1, p1, ..., pm, pipj (i 1 vaø d| nn
µ(d)=1,
µ(d) = f(n).
d|n
⇐ .
µ(d)g(nd) = d |n
f(d )
d| nd
µ(d) =
d =n
f(d )
d| nn
Vì
ta suy ra
f(n) = d|n
µ(nd)g(d),
d|n
f(d) = d|n
f(nd) = d|n
d | nd
µ( ndd )g(d ) = dd |n
µ( ndd )g(d ).
Theo ñònh lyù 4.15 thì
d| nd
neân ta suy ra
µ(d)=0 neáu nd > 1 vaø d| nn
µ(d)=1,
d|n
f(d) =
dd |n
µ( ndd )g(d ) = d |n
g(d )
d| nd
µ( ndd) =
d =n
g(d )
d| nn
µ(d) = g(n).
4.4. HAØM MO¨BIUS µ(N). 53 Ví duï 4.4.1. Xeùt moät trong caùc aùp duïng cuûa ñònh lyù treân. Ta ñaõ bieát haøm
ϕ(d) = n.
Theo dònh lyù 4.16, ta coù
g(n) = d|n
ϕ(n) = d|n
µ(d)g(nd) = d|n
µ(d)nd = n d|n
µ(d)
d .
Ñoái vôùi soá thöïc x, ta kyù hieäu
ñeå chæ
[x]
, vaø toång ñöôïc hieåu laø baèng 0
n≤x
neáu noù khoâng chöùa soá haïng naøo.
n=1
Ñònh lyù 4.17. Bieán ñoåi ngöôïc Mo¨bius thöù hai. Giaû söû f laø haøm bieán soá thöïc
xaùc ñònh vôùi x ≥ 1, vaø
g(x) =
n≤x
f(xn).
Khi ñoù, vôùi x ≥ 1 vaø ngöôïc laïi.
f(x) =
n≤x
µ(n)g(xn)
Chöùng minh. ⇒ . Töø ñònh nghóa cuûa haøm g, khi x ≥ 1, ta coù
n≤x
µ(n)g(xn) = n≤x
µ(n)
m≤ xn
f( xmn) =
1≤mn≤x
µ(n)f( xmn)
Nhoùm toång sau cuøng theo mn = r, 1 ≤ r ≤ x, ta ñöôïc
1≤mn≤x
µ(n)f( xmn) = 1≤r≤x
f(xr)
n|r
µ(n) = f(x).
⇐ . Töø
f(x) =
n≤x
µ(n)g(xn),
54 4. CAÙC HAØM SOÁ HOÏC ta suy ra
m≤x
f(xm) =
m≤x
n≤ xm
µ(n)g( xmn) = 1≤mn≤x
µ(n)g( xmn).
Cuõng nhö tröôùc, ta coù
1≤mn≤x
µ(n)g( xmn) = 1≤r≤x
g(xr)
n|r
µ(n) = g(x).
BAØI TAÄP CHÖÔNG IV
1. Tích Dirichclet cuûa hai haøm soá hoïc f, g ñöôïc ñònh nghóa bôûi
(f ∗ g)(n) = d|n
f(d)g(n/d).
Chöùng minh raèng: f ∗ g = g ∗ f; (f ∗ g) ∗ h = f ∗ (g ∗ h). 2. Haøm soá hoïc ι ñöôïc ñònh nghóa bôûi
ι(n) =
1 neáu n = 1 0 neáu n > 1
(Nhôù laïi: ι(n) = d|n
µ(d).)
a) Chöùng minh raèng haøm ι laø coù tính nhaân.
b) Chöùng minh raèng ι ∗ f = f ∗ ι = f vôùi moïi haøm soá hoïc f.
3. Haøm soá hoïc g ñöôïc goïi laø nghòch ñaûo cuûa haøm soá hoïc f neáuu f ∗ g = g ∗ f = ι.
a) Chöùng minh raèng haøm soá hoïc f coù nghòch ñaûo khi vaø chæ khi f(1) = 0. b) Chöùng minh raèng neáu haøm soá hoïc f coù nghòch ñaûo thì nghòch ñaûo cuûa noù laø duy nhaát.
4.4. HAØM MO¨BIUS µ(N). 55
4. Chöùng minh raèng neáu f,g laø caùc haøm coù tính nhaân thì tích Dirichlet f ∗ g cuõng coù tính nhaân.
5. Chöùng minh raèng
ϕ(2n) =
ϕ(n) neáu n leû 2ϕ(n) neáu n chaün
6. Chöùng minh raèng neáu n coù k öôùc nguyeân toá leû khaùc nhau thì 2k | ϕ(n). 7. Chöùng minh raèng neáu m, k laø nguyeân döông thì ϕ(mk) = mk−1ϕ(m). 8. Chöùng minh raèng neáu a, b laø caùc soá nguyeân döông thì ϕ(ab)=(a, b)ϕ(a)ϕ(b)/ϕ((a, b)).
9. Duøng bieán ñoåi ngöôïc Mo¨bius vaø coâng thöùc n = d|n ϕ(n/d), haõy chöùng minh raèng:
a) ϕ(pk) = pk − pk−1
b) Haøm ϕ coù tính nhaân.
10. Haõy tính soá öôùc vaø toång caùc öôùc cuûa caùc soá: 2100, 5374115, 30!
11. Haõy xaùc ñònh caùc soá nguyeân döông coù ñuùng:
a) Ba öôùc döông,
b) Boán öôùc döông.
Haøm σk(n) laø toång caùc luõy thöøa k cuûa caùc öôùc döông cuûa soá nguyeân
döông n,
σk(n) = d|n
dk.
12. Ñöa ra coâng thöùc tính σk(pα), vôùi p nguyeân toá vaø α nguyeân döông. 13. Chöùng minh raèng haøm σk coù tính nhaân.
14. Ñöa ra coâng thöùc tính σk(n), khi n coù khai trieån thaønh luõy thöøa nguyeân
toá n = pα1
2 ··· pαk
1 pα2
k .
15. Tìm taát caû caùc soá nguyeân döông n thoûa ϕ(n) + σ(n)=2n.
56 4. CAÙC HAØM SOÁ HOÏC
16. Chöùng minh raèng coù ñuùng τ (n2) caëp coù thöù töï hai soá nguyeân döông vôùi boäi chung nhoû nhaát baèng n.
17. Giaû söû n ≥ 2 laø soá nguyeân. Daõy caùc soá nguyeân n1, n2, n3, ... ñöôïc xaùc ñònh bôûi n1 = τ (n), nk+1 = τ (nk), k = 1, 2, 3, .... Chöùng minh raèng coù soá nguyeân döông r sao cho 2 = nr+k vôùi moïi soá töï nhieân k.
18. Ñaët
T(N) =
N
τ (n).
a) Chöùng minh raèng
T(N) =
n=1 N
N n
.
n=1
b) Chöùng minh raèng
.
AÙp duïng tính 100
T(N) = −[√N]2 + 2[√N] n=1
N n
n=1 τ (n).
c) Chöùng minh raèng T(N) = N ln N + (2γ − 1)N + O(√N). (γ laø haèng soá Euler)
19. Tính ñònh thöùc cuûa n × n−matraän A vôùi caùc phaàn töû aij = (i, j). 20. Giaû söû θ laø haøm coù tính nhaân vaø µ laø haøm Mo¨bius. Chöùng minh raèng
neáu n coù khai trieån thaønh luõy thöøa nguyeân toá n = pα1
2 ··· pαk
k thì
1 pα2
µ(d)θ(d) = (1 − θ(p1))(1 − θ(p2))···(1 − θ(pk)).d|n
5
CAÊN NGUYEÂN THUÛY
5.1 Baäc cuûa soá nguyeân vaø caên nguyeân thuyû
Trong phaàn naøy chuùng ta seõ nghieân cöùu caùc thaëêng dö döông nhoû nhaát modulo n cuûa luõy thöøa cuûa soá nguyeân a. Chuùng ta seõ baét ñaàu baèng söï nghieân cöùu baäc cuûa soá nguyeân a modulo n.
Theo ñònh lyù Euler neáu m laø soá nguyeân döông vaø a laø soá nguyeân sao cho (a, m)=1 thì aϕ(m) ≡ 1 (mod m). Ñieàu naøy noùi leân ñoàng dö ax ≡ 1 (mod m) coù nghieäm nguyeân döông.
Soá nguyeân döông nhoû nhaát x thoûa ax ≡ 1 (mod m) ñöôïc chuùng ta goïi laø baäc cuûa a modulo m vaø kyù hieäu laø ordma.
Deã daøng thaáy raèng, vôùi n > 1 thì soá nguyeân a coù baäc modulo n khi vaø chæ khi (a, n)=1.
Ví duï 5.1.1. Ta caàn xaùc ñònh baäc cuûa 2 modulo 7. Ta thaáy 21 ≡ 2 (mod 7), 22 ≡ 4 (mod 7), 23 ≡ 1 (mod 7).
Vaäy ord72=3.
Töông töï, ñeå tìm baäc cuûa 3 modulo 7, ta coù:
31 ≡ 3 (mod 7), 32 ≡ 2 (mod 7), 33 ≡ 6 (mod 7)
34 ≡ 4 (mod 7), 35 ≡ 5 (mod 7), 36 ≡ 1 (mod 7)
Vaäy ord73=6.
57
58 5. CAÊN NGUYEÂN THUÛY
Ñònh lyù 5.1. Giaû söû n laø soá nguyeân döông vaø (a, n)=1. Theá thì: soá nguyeân döông x laø nghieäm cuûa ñoàng dö ax ≡ 1 (mod n) khi vaø chæ khi ordna | x.
Chöùng minh. ⇒ . Neáu ordna | x, thì x = k · ordna vôùi k nguyeân döông. Khi ñoù
ax = ak·ordna = (aordna)k ≡ 1 (mod n).
⇐ . Theo thuaät toaùn chia, x = q · ordna + r, 0 ≤ r < ordna. Ta coù ax = aq·ordna+r = (aordna)qar ≡ ar (mod n).
Vaäy neáu ax ≡ 1 (mod n) thì ar ≡ 1 (mod n). Do 0 ≤ r < ordna neân r = 0.
Ví duï 5.1.2. Chuùng ta caàn xaùc ñònh xem 108 vaø 2003 coù laø nghieäm cuûa ñoàng dö 2x ≡ 1 (mod 7) hay khoâng. Ta ñaõ bieát ord72=3. Nhö vaäy, x = 108 laø nghieäm cuûa 2x ≡ 1 (mod 7) vì ord72=3 | 108; coøn x = 2003 khoâng laø nghieäm cuûa 2x ≡ 1 (mod 7) vì ord72=3 2003.
Heä quaû 5.1.1. Neáu n laø soá nguyeân döông vaø (a, n)=1, thì ordna | ϕ(n). Chöùng minh. Baøi taäp daønh cho ñoïc giaû.
Ví duï 5.1.3. Chuùng ta caàn xaùc ñònh baäc cuûa 5 modulo 17. Vì ϕ(17) = 16 vaø (5, 17) = 1 neân ord175 | 16 = ϕ(17). Do 16 chæ coù caùc öôùc döông laø 1, 2, 4, 8, 16 vaø
51 ≡ 5 (mod 17), 52 ≡ 8 (mod 17), 54 ≡ 13 (mod 17), 58 ≡ 16 (mod 17) neân ord175 = 16.
Ñònh lyù 5.2. Giaû söû n laø soá nguyeân döông vaø (a, n)=1. Theá thì vôùi moïi i, j > 0: ai ≡ aj (mod n) khi vaø chæ khi i ≡ j (mod ordna).
5.1. BAÄC CUÛA SOÁ NGUYEÂN VAØ CAÊN NGUYEÂN THUYÛ 59
Chöùng minh. ⇒ . Giaû söû ai ≡ aj (mod n) vaø i ≥ j. Do ai = ajai−j neân ajai−j ≡ aj (mod n).
Vì (aj , n)=1 neân töø ñoàng dö treân ta suy ra
ai−j ≡ 1 (mod n).
Theo ñònh lyù 5.1 ta coù ordna | i − j, hay i ≡ j (mod ordna).
⇐ . Giaû söû i ≥ j. Töø giaû thieát i ≡ j (mod ordna), suy ra coù soá nguyeân k ≥ 0 ñeå i = j + k · ordna. Theá thì
ai = aj+k·ordna = aj(aordna)k ≡ aj (mod n).
Ví duï 5.1.4. Giaû söû a = 3, n = 14. Ta coù ord143=6. Töø ñònh lyù treân ta coù: 35 ≡ 311 (mod 14) vì ord143 | (11 − 5); vaø 36 ≡ 320 (mod 14) vì ord143 | (20 − 6).
Ñònh lyù 5.3. Neáu ordma = t vaø u laø soá nguyeân döông thì
ordm(au) = t
(t, u).
Chöùng minh. Giaû söû s = ordm(au), ν = (t, u), t = t1ν, u = u1ν. Theá thì (t1, u1)=1.
Ta coù
(au)t1 = (au1ν)t/ν = (at)u1 ≡ 1 (mod m).
Töø ñònh lyù 5.1 ta coù s | t1.
Maët khaùc, do
aus = (au)s ≡ 1 (mod m)
neân theo ñònh lyù 5.1 ta coù t | us. Do ñoù t1ν | u1νs, cuõng vaäy t1 | u1s. Nhöng (t1, u1)=1 neân t1 | s.
Töø s | t1 vaø t1 | s ta suy ra s = t1 = t/ν = t/(t, u).
60 5. CAÊN NGUYEÂN THUÛY
Ví duï 5.1.5. ord143=6, ord149 = ord1432 = 6/(6, 2) = 3, ord1427 = ord1433 = 6/(6, 3) = 2, ord1481 = ord1434 = 6/(6, 4) = 3, ord14243 = ord1435 = 6/(6, 5) = 6, ord14729 = ord1436 = 6/(6, 6) = 1.
Giaû söû n laø soá nguyeân döông. Chuùng ta seõ quan taâm ñeán caùc soá nguyeân a coù baäc modulo n ñuùng baèng ϕ(n). Sau naøy chuùng ta seõ thaáy raèng neáu coù soá nguyeân a nhö vaäy, thì taäp taát caû caùc luõy thöøa döông cuûa a chính laø heä thaëng dö thu goïn modulo n.
Giaû söû n laø soá nguyeân döông. Soá nguyeân r ñöôïc goïi laø caên nguyeân thuyû modulo n neáuu ordnr = ϕ(n).
Chuù yù raèng khoâng phaûi soá nguyeân döông n naøo cuõng coù caên nguyeân thuyû.
Ví duï 5.1.6. 3 laø caên nguyeân thuyû modulo 7 vì ord73=6= ϕ(7); 3 laø caên nguyeân thuyû modulo 14 vì ord143=6= ϕ(14).
2 khoâng laø caên nguyeân thuyû modulo 7 vì ord72=3 = ϕ(7).
Soá 8 khoâng coù caên nguyeân thuyû, vì ϕ(8) = 4 vaø ord81=1, ord83 = ord85 = ord87=2.
Ñònh lyù 5.4. Neáu (r, n)=1 vaø r laø caên nguyeân thuyû modulo n thì r1 , r2 , ··· , rϕ(n)
laø heä thaëêng dö thu goïn modulo n.
Chöùng minh. Chuùng ta chæ caàn chöùng toû raèng (rk, n)=1 vôùi 1 ≤ k ≤ ϕ(n) vaø ri ≡ rj (mod n) vôùi 1 ≤ i = j ≤ ϕ(n).
Töø (r, n)=1 deã daøng suy ra (rk, n)=1 vôùi moïi soá nguyeân döông k.
Giaû söû 1 ≤ i, j ≤ ϕ(n) vaø ri ≡ rj (mod n). Theo ñònh lyù 5.2 ta coù i ≡ j (mod ordna = ϕ(n)), nhöng 1 ≤ i, j ≤ ϕ(n) neân i = j. Ví duï 5.1.7. Do 3 laø caên nguyeân thuyû modulo 7 vaø ϕ(7) = 6 neân caùc soá: 31 = 3, 32 = 9, 33 = 27, 34 = 81, 35 = 243, 36 = 729
laäp thaønh heä thaëng dö thu goïn modulo 7.
5.2. CAÊN NGUYEÂN THUYÛ CUÛA SOÁ NGUYEÂN TOÁ 61
Ñònh lyù 5.5. Giaû söû m > 1 vaø r laø caên nguyeân thuyû modulo m; u laø soá nguyeân döông. Theá thì: ru laø caên nguyeân thuyû modulo m khi vaø chæ khi (u, ϕ(m)) = 1.
Chöùng minh. Theo ñònh lyù 5.3 thì
ordm(ru) = ordmr
(u,ordmr)
= ϕ(m)
(u,ϕ(m)) .
Nhö vaäy, ordm(ru) = ϕ(m) khi vaø chæ khi (u, ϕ(m)) = 1.
Ñònh lyù 5.6. Neáu soá nguyeân döông m coù caên nguyeân thuyû thì noù coù caû thaûy ϕ(ϕ(m)) caên nguyeân thuyû khoâng ñoàng dö nhau modulo m.
Chöùng minh. Giaû söû r laø moät caên nguyeân thuyû cuûa m.
Theo ñònh lyù 5.4 thì r1, r2, ··· , rϕ(m) laø heä thaëng dö thu goïn modulo m.
Do ñònh lyù 5.5, ru laø caên nguyeân thuyû modulo m khi vaø chæ khi (u, ϕ(m)) = 1. Vaäy coù ñuùng ϕ(ϕ(m)) caùc soá u nhö vaäy, hay m coù ñuùng ϕ(ϕ(m)) caên nguyeân thuyû khoâng ñoàng dö nhau modulo m.
Ví duï 5.1.8. Giaû söû m = 11. Do (2, 11) = 1 neân ord112 | ϕ(11) = 10. Ta thaáy 21 ≡ 2 (mod 11), 22 ≡ 4 (mod 11), 25 ≡ 10 (mod 11); suy ra ord112 = ϕ(11). Vaäy 11 coù 2 laø caên nguyeân thuyû, do ñoù 11 coù caû thaûy ϕ(ϕ(11)) = ϕ(10) = 4 caên nguyeân thuyû khoâng ñoàng dö nhau modulo 11. Ñoù laø: 21 = 2, 23 = 8, 27 = 128, vaø 29 = 512; hay cuõng vaäy: 2, 8, 7, vaø 6.
5.2 Caên nguyeân thuyû cuûa soá nguyeân toá
Trong muïc naøy chuùng ta seõ chæ ra raèng moïi soá nguyeân toá ñeàu coù caên nguyeân thuyû. Ñeå ñaït ñöôïc ñieàu naøy, tröôùc heát chuùng ta caàn khaûo saùt vaøi tính chaát cuûa ñoàng dö ña thöùc.
Giaû söû f(x) laø ña thöùc vôùi heä soá nguyeân. Chuùng ta seõ noùi soá nguyeân c laø nghieäm cuûa f(x) modulo m neáuu f(c) ≡ 0 (mod m). Deã daøng thaáy raèng, neáu c laø nghieäm cuûa f(x) modulo m thì moïi soá nguyeân ñoàng dö vôùi c modulo m cuõng laø nghieäm.
62 5. CAÊN NGUYEÂN THUÛY
Ví duï 5.2.1. Ña thöùc f(x) = x2 + x + 1 coù ñuùng hai nghieäm khoâng ñoàng dö nhau modulo 7, cuï theå laø x ≡ 2 (mod 7) vaø x ≡ 4 (mod 7).
Ña thöùc g(x) = x2 + 2 laø khoâng coù nghieäm modulo 5.
Ñònh lyù Fermat cuõng chæ ra raèng, neáu p laø soá nguyeân toá thì ña thöùc h(x) = xp−1 −1 coù ñuùng p−1 nghieäm khoâng ñoàng dö nhau modulo p, cuï theå laø x ≡ 1, 2, 3, ··· , p − 1 (mod p).
Ñònh lyù 5.7. Ñònh lyù Lagrange. Giaû söû p laø soá nguyeân toá; f(x) = anxn + an−1xn−1+···+a1x+a0 laø ña thöùc vôùi heä soá nguyeân, coù baäc n ≥ 1, (an, p)=1. Theá thì f(x) ≡ 0 (mod p) coù khoâng quaù n nghieäm khoâng ñoàng dö nhau modulo p.
Chöùng minh. Chuùng ta chöùng minh ñònh lyù baèng phöông phaùp qui naïp.
Khi n = 1, ta coù f(x) = a1x + a0 vôùi p a1. Nghieäm cuûa f(x) modulo p chính laø nghieäm cuûa ñoàng dö tuyeán tính a1x ≡ a0 (mod p). Ta ñaõ bieát neáu (a1, p)=1 thì a1x ≡ a0 (mod p) coù duy nhaát nghieäm modulo p.
Giaû söû ñònh lyù ñaõ ñuùng cho caùc ña thöùc baäc n − 1. Neáu ña thöùc f(x) = anxn+an−1xn−1+···+a1x+a0 coù quaù n nghieäm khoâng ñoàng dö nhau modulo p. Theá thì coù caùc soá nguyeân c0, c1, ··· , cn khoâng ñoàng dö nhau modulo p sao cho f(ck) ≡ 0 (mod p) vôùi moïi 0 ≤ k ≤ n. Khi ñoù ta coù
f(x) − f(c0) = an(xn − cn0 ) +an−1(xn−1 − cn−1
0 ) + ··· + a1(x − c0)
= an(x − c0) (xn−1 + xn−2c0 + ··· + xcn−2
0 + cn−1
+an−1(x − c0) (xn−2 + xn−3c0 + ··· + xcn−3
0 ) +
0 + cn−2
0 ) + ...
+a1(x − c0)
= (x − c0)g(x) .
trong ñoù g(x) laø ña thöùc baäc n − 1 vôùi heä soá baäc cao nhaát cuõng chính laø an. Töø heä thöùc treân ta coù
(ck − c0)g(ck) = f(ck) − f(c0) ≡ 0 (mod p).
Nhöng vôùi moïi k, 1 ≤ k ≤ n, ck ≡ c0 (mod p); hay (ck − c0, p)=1. Vaäy g(ck) ≡ 0 (mod p), vôùi moïi k, 1 ≤ k ≤ n; ñieàu naøy maâu thuaãn vôùi giaû
5.2. CAÊN NGUYEÂN THUYÛ CUÛA SOÁ NGUYEÂN TOÁ 63
thieát qui naïp: g(x) coù khoâng quaù n − 1 nghieäm khoâng ñoàng dö nhau modulo p.
Ñònh lyù 5.8. Giaû söû p laø soá nguyeân toá vaø d laø öôùc cuûa p−1. Theá thì xd−1 ≡ 0 (mod p) coù ñuùng d nghieäm khoâng ñoàng dö nhau modulo p.
Chöùng minh. Ñaët p − 1 = de. Ta coù
xp−1 −1=(xd)e −1=(xd −1)(xd(e−1) +xd(e−2) +···+xd + 1) = (xd −1)g(x).
Vì p nguyeân toá neân xp−1 − 1=(xd − 1)g(x) ≡ 0 (mod p) khi vaø chæ khi (xd − 1) ≡ 0 (mod p) hoaëc g(x) ≡ 0 (mod p).
Do xp−1 −1 ≡ 0 (mod p) coù ñuùng p−1 nghieäm vaø g(x) vôùi baäc p−1−d seõ coù khoâng quaù p − 1 − d nghieäm khoâng ñoàng dö nhau modulo p; ta suy ra xd − 1 ≡ 0 (mod p) coù khoâng ít hôn d nghieäm khoâng ñoàng dö nhau modulo p. Do ñònh lyù 5.7 ta suy ra xd − 1 ≡ 0 (mod p) coù ñuùng d nghieäm khoâng ñoàng dö nhau modulo p.
Ñònh lyù 5.9. Giaû söû p laø soá nguyeân toá vaø d laø öôùc cuûa p − 1. Theá thì coù ñuùng ϕ(d) soá nguyeân khoâng ñoàng dö nhau modulo p vaø coù baäc baèng d modulo p.
Chöùng minh. Kyù hieäu F(d) laø soá caùc soá nguyeân döông nhoû hôn p vaø coù baäc d modulo p. Vì taát caû caùc soá nguyeân döông nhoû hôn p ñeàu coù baäc vaø baäc laø
öôùc cuûa p − 1 neân
p − 1 =
d|p−1
F(d).
Maët khaùc, theo ñònh lyù **refdl39 ta coù p − 1 =
d|p−1
ϕ(d).
Vaäy d|p−1
F(d) =
d|p−1
ϕ(d).
Ñeå keát thuùc vieäc chöùng minh ñònh lyù, ta chæ caàn chöùng minh raèng F(d) ≤ ϕ(d) vôùi d | p − 1.
Neáu F(d)=0 thì F(d) ≤ ϕ(d) laø hieån nhieân. Ngöôïc laïi, neáu ordpa = d thì
a, a2, ··· , ad
64 5. CAÊN NGUYEÂN THUÛY
laø caùc soá ñoâi moät khoâng ñoàng dö nhau modulo p. Moãi moät trong caùc soá naøy ñeàu laø nghieäm cuûa (xd − 1) ≡ 0 (mod p), vì (ak)d = (ad)k ≡ 1 (mod p). Töø ñònh lyù 5.8 ta suy ra raèng, moãi nghieäm cuûa (xd − 1) ≡ 0 (mod p) ñeàu ñoàng dö modulo p vôùi moät luõy thöøa ak cuûa a, 1 ≤ k ≤ d. Ñònh lyù 5.5 laïi noùi raèng, ak coù baäc baèng d = ordpa khi vaø chæ khi (k, d)=1. Nhö vaäy coù ñuùng ϕ(d) soá khoâng ñoàng dö nhau modulo p vaø coù baäc baèng d. Vaäy F(d) ≤ ϕ(d).
Heä quaû 5.9.1. Moïi soá nguyeân toá ñeàu coù caên nguyeân thuyû.
Chöùng minh. Giaû söû p laø soá nguyeân toá. Theo ñònh lyù treân, vôùi d = p − 1, ta coù caû thaûy ϕ(p − 1) soá khoâng ñoàng dö nhau modulo p vaø coù baäc baèng p − 1 = ϕ(p).
5.3 Caùc soá coù caên nguyeân thuyû
Trong muïc naøy chuùng ta seõ chæ ra taát caû caùc soá coù caên nguyeân thuyû. Tröôùc heát chuùng ta chæ ra raèng caùc luõy thöøa cuûa moãi soá nguyeân toá leû ñeàu coù caên nguyeân thuyû.
Ñònh lyù 5.10. Neáu r laø caên nguyeân thuyû cuûa soá nguyeân toá leû p thì r hoaëc r+p laø caên nguyeân thuyû modulo p2.
Chöùng minh. Vì r laø caên nguyeân thuyû modulo p neân ordpr = ϕ(p) = p − 1.
Ñaët n = ordp2 r, ta coù Suy ra
Theo ñònh lyù 5.1 thì Ta cuõng coù
rn ≡ 1 (mod p2).
rn ≡ 1 (mod p).
p − 1 = ordp | n.
n = ordp2 r | ϕ(p2) = p(p − 1).
Vì p − 1 | n vaø n | p(p − 1) ta suy ra n = p − 1 hoaëc n = p(p − 1). Neáu n = p(p − 1) thì r laø caên nguyeân thuyû modulo p2 vì ordp2 r = n = ϕ(p2). Ngöôïc laïi, neáu n = p − 1 ta coù
rp−1 = rn ≡ 1 (mod p2).
5.3. CAÙC SOÁ COÙ CAÊN NGUYEÂN THUYÛ 65
Ñaët s = r + p. Do s ≡ r (mod p) neân s cuõng laø caên nguyeân thuyû modulo p. Töông töï nhö treân, ta coù ordp2 s = p − 1 hoaëc ordp2 s = p(p − 1). Cuõng töông töï nhö treân, ñeå chöùng minh s laø caên nguyeân thuyû modulo p2 chuùng ta chæ caàn chöùng toû raèng ordp2 s = p − 1. Ta coù
sp−1 = (r + p)p−1 = rp−1 + (p − 1)rp−2p + p − 1
2
vaø rp−1 ≡ 1 (mod p2) neân
rp−3p2 + ··· + pp−1
sp−1 ≡ rp−1 + (p − 1)prp−2 ≡ 1 − prp−2 (mod p2).
Vì (r, p)=1 neân prp−2 ≡ 0 (mod p2), suy ra
sp−1 ≡ 1 (mod p2),
hay ordp2 s = p − 1.
Ví duï 5.3.1. Ta ñaõ bieát r = 3 laø caên nguyeân thuyû modulo p = 7. Söû duïng ñònh lyù ?? ta coù ord493 = p − 1=6 hoaëc ord493 = p(p − 1) = 42. Do
r6 = 36 = 729 ≡ 1 (mod 49)
ta suy ra r = 3 laø caên nguyeân thuyû modulo 49.
Ñònh lyù 5.11. Neáu p laø soá nguyeân toá leû thì pk coù caên nguyeân thuyû vôùi moïi soá nguyeân döông k. Hôn nöõa, neáu r laø caên nguyeân thuyû modulo p2 thì r laø caên nguyeân thuyû modulo pk vôùi moïi soá nguyeân döông k.
Chöùng minh. Heä quaû 5.9.1 noùi raèng p coù caên nguyeân thuyû, vaø do ñoù theo ñònh lyù 5.10 ta suy ra p2 cuõng coù caên nguyeân thuyû. Giaû söû r laø caên nguyeân thuyû modulo p2.
Tröôùc heát, baèng qui naïp chuùng ta chöùng minh raèng vôùi moïi soá nguyeân k ≥ 2 ñeàu coù
rpk−2(p−1) ≡ 1 (mod pk).
Khi k = 2, ta coù rpk−2(p−1) = rp−1 ≡ 1 (mod p2), vì ordp2 r = ϕ(p2) = p(p−1). Giaû söû raèng vôùi soá nguyeân k ≥ 2 ta ñaõ coù
rpk−2(p−1) ≡ 1 (mod pk).
66 5. CAÊN NGUYEÂN THUÛY
Vì (r, pk−1)=1 neân theo ñònh lyù Euler, ta coù
rpk−2(p−1) = rϕ(pk−1) ≡ 1 (mod pk−1),
vaø ñieàu naøy keùo theo
rpk−2(p−1) =1+ dpk−1
trong ñoù p d vì rpk−2(p−1) ≡ 1 (mod pk). Luõy thöøa p hai veá cuûa ñoàng dö treân, ta ñöôïc
rpk−1(p−1) = (1 + dpk−1)p =1+ p(dpk−1) + p2 (dpk−1)2 + ··· + (dpk−1)p.
Suy ra
rpk−1(p−1) ≡ 1 + dpk (mod pk+1).
Nhöng p d neân
rpk−1(p−1) ≡ 1 (mod pk+1).
Baây giôø chuùng ta seõ chöùng minh raèng r laø caên nguyeân thuyû cuûa pk vôùi k ≥ 2. Ñaët n = ordpk r. Ta coù
n | ϕ(pk) = pk−1(p − 1).
Maët khaùc, vì rn ≡ 1 (mod pk) neân rn ≡ 1 (mod p); suy ra p − 1 = ϕ(p) | n.
Do n | pk−1(p−1) vaø (p−1) | n neân n = pt(p−1) vôùi t naøo ñoù, 0 ≤ t ≤ k−1.
Tröôøng hôïp n = pt(p − 1) vôùi 0 ≤ t ≤ k − 2 khoâng theå xaûy ra, vì neáu 0 ≤ t ≤ k − 2 thì
rpk−2(p−1) = (rpt(p−1))k−2−t = (rn)k−2−t ≡ 1 (mod pk),
vaø ñieàu naøy voâ lyù vôùi ñieàu ñaõ ñöôïc chöùng minh laø rpk−2(p−1) ≡ 1 (mod pk).
Vaäy n = pk−1(p − 1), vaø ñieàu naøy noùi leân raèng ordpk r = ϕ(pk), hay cuõng vaäy: r laø caên nguyeân thuyû cuûa pk.
Ñònh lyù 5.12. Neáu a laø soá leû vaø k > 2 thì
aϕ(2k)/2 ≡ 1 (mod 2k).
5.3. CAÙC SOÁ COÙ CAÊN NGUYEÂN THUYÛ 67
Chöùng minh. Chuùng ta chöùng minh baèng phöông phaùp qui naïp theo k. Khi k = 3, ñaët a = 2b + 1. Vì 2 | b(b + 1) neân
aϕ(23)/2 = (2b + 1)2 = 4b(b + 1) + 1 ≡ 1 (mod 23).
Giaû söû ñaõ coù aϕ(2k)/2 ≡ 1 (mod 2k), ta caàn chöùng minh raèng aϕ(2k+1)/2 ≡ 1 (mod 2k+1). Vì ϕ(2n)=2n(1 − 1/2) = 2n−1 neân töø giaû thieát qui naïp ta coù
a2k−2≡ 1 (mod 2k),
suy ra
a2k−2=1+ d2k.
Bình phöông caû hai veá, ta ñöôïc
a2k−1=1+ d2k+1 + d222k ≡ 1 (mod 2k+1),
ñieàu naøy keùo theo
aϕ(2k+1)/2 = a2k−1≡ 1 (mod 2k).
Nhaän xeùt:
1. Ñònh lyù treân noùi leân raèng taát caû caùc luõy thöøa döông cuûa 2, tröø hai soá 2 vaø 4, ñeàu khoâng coù caên nguyeân thuyû.
2. Caùc soá 2 vaø 4 ñeàu coù coù caên nguyeân thuyû.
Ñònh lyù 5.13. Neáu soá nguyeân döông n khoâng laø luõy thöøa nguyeân toá hoaëc hai laàn luõy thöøa nguyeân toá thì n khoâng coù caên nguyeân thuyû.
Chöùng minh. Giaû söû n coù caên nguyeân thuyû r, vaø coù khai trieån thaønh luõy thöøa nguyeân toá
n = pt11 pt22 ··· ptm
m .
Goïi p laø thöøa soá nguyeân toá cuûa n, do (r, pt)=1 neân
rϕ(pt) ≡ 1 (mod pt).
Ñaët
U = [ϕ(pt11 ), ϕ(pt22 ), ··· , ϕ(ptm
m )].
68 5. CAÊN NGUYEÂN THUÛY
Vì ϕ(ptii ) | U neân theo ñònh lyù Trung hoa veà phaàn dö ta coù rU ≡ 1 (mod n).
Ñieàu naøy keùo theo
ordnr = ϕ(n) ≤ U.
Nhöng
ϕ(n) = ϕ(pt11 )ϕ(pt22 )··· ϕ(ptm
m ),
ta suy ra
ϕ(pt11 )ϕ(pt22 )··· ϕ(ptm
m ) ≤ [ϕ(pt11 ), ϕ(pt22 ), ··· , ϕ(ptm
m )].
Vaäy
ϕ(pt11 )ϕ(pt22 )··· ϕ(ptm
m )=[ϕ(pt11 ), ϕ(pt22 ), ··· , ϕ(ptm
m )].
Ñaúng thöùc cuoái cuøng xaûy ra chæ khi caùc soá nguyeân ϕ(pt11 ), ϕ(pt22 ), ··· , ϕ(ptm
laø ñoâi moät nguyeân toá cuøng nhau.
m )
Vôùi chuù yù raèng ϕ(pt) = pt−1(p−1) ta thaáy ϕ(pt) laø soá chaün neáu p leû hoaëc p = 2 vaø t ≥ 2. Nhö vaäy, caùc soá nguyeân ϕ(pt11 ), ϕ(pt22 ), ··· , ϕ(ptm
m ) laø khoâng
ñoâi moät nguyeân toá cuøng nhau, ngoaïi tröø tröôøng hôïp m = 1 hoaëc m = 2 vaø n = 2pt maø p laø soá nguyeân toá leû.
Ñònh lyù 5.14. Neáu p laø soá nguyeân toá leû vaø t laø soá nguyeân döông thì 2pt coù caên nguyeân thuyû. Cuï theå hôn: neáu r laø caên nguyeân thuyû modulo pt vaø r leû thì noù cuõng laø caên nguyeân thuyû modulo 2pt; ngöôïc laïi neáu r laø caên nguyeân thuyû modulo pt vaø r chaün thì r + pt laø caên nguyeân thuyû modulo 2pt.
Chöùng minh. Goïi r laø caên nguyeân thuyû modulo pt, ta coù
rϕ(pt) ≡ 1 (mod pt)
vaø khoâng coù soá muõ nguyeân döông naøo nhoû hôn ϕ(pt) coù tính chaát naøy. Ta coù ϕ(2pt) = ϕ(2)ϕ(pt) = ϕ(pt). Vaäy
rϕ(2pt) ≡ 1 (mod pt).
Neáu r leû thì
rϕ(2pt) ≡ 1 (mod 2).
5.4. CHÆ SOÁ SOÁ HOÏC 69
Vì (2, pt)=1, ta suy ra
rϕ(2pt) ≡ 1 (mod 2pt).
Deã thaáy khoâng coù soá muõ nguyeân döông naøo nhoû hôn ϕ(2pt) = ϕ(pt) coù tính chaát treân, do ñoù ord2pt r = ϕ(2pt).
Neáu r chaün thì r + pt laø soá leû. Do ñoù
(r + pt)ϕ(2pt) ≡ 1 (mod 2).
Maët khaùc, vì r + pt ≡ r (mod pt) neân
(r + pt)ϕ(2pt) ≡ 1 (mod pt).
Suy ra
(r + pt)ϕ(2pt) ≡ 1 (mod 2pt).
Cuõng thaáy raèng khoâng coù soá muõ nguyeân döông naøo nhoû hôn ϕ(2pt) = ϕ(pt) coù tính chaát treân, do ñoù ord2pt (r + pt) = ϕ(2pt).
Töø caùc ñònh lyù 5.11, 5.12, 5.13 vaø 5.14, ta coù ñònh lyù sau
Ñònh lyù 5.15. Soá nguyeân döông n > 1 coù caên nguyeân thuyû khi vaø chæ khi n = 2, 4, pt, 2pt
trong ñoù p laø soá nguyeân toá leû vaø t laø soá nguyeân döông.
5.4 Chæ soá soá hoïc
Giaû söû soá nguyeân döông coá ñònh m coù caên nguyeân thuyû r. Vìù caùc soá nguyeân r1, r2, ··· , rϕ(m)
laøm thaønh heä thaëng dö thu goïn modulo m, neân moãi soá nguyeân a nguyeân toá cuøng nhau vôùi m ñeàu toàn taïi duy nhaát moät soá nguyeân x, 1 ≤ x ≤ ϕ(m), maø
rx ≡ a (mod m).
Soá nguyeân x nhö vaäy ñöôïc goïi laø chæ soá cuûa a vôùi cô sôû r modulo m, kyù hieäu x = indra.
70 5. CAÊN NGUYEÂN THUÛY
Nhö vaäy aindra ≡ a (mod m). Töø ñònh nghóa ta cuõng thaáy ngay raèng, ñoái vôùi moïi soá a, b nguyeân toá cuøng nhau vôùi m, heä thöùc a ≡ b (mod m) laø töông ñöông vôùi indra = indrb.
Coù moät soá tính chaát cuûa chæ soá töông töï nhö cuûa logarithm, chæ coù ñieàu thay daáu baèng bôûi daáu ñoàng dö modulo ϕ(m).
Ñònh lyù 5.16. Giaû söû soá nguyeân döông m coù caên nguyeân thuyû r, vaø a, b laø caùc soá nguyeân toá cuøng nhau vôùi m. Theá thì:
1. indr1 ≡ 0 (mod ϕ(m)).
2. indr(ab) ≡ indra + indrb (mod ϕ(m)).
3. indrak ≡ k · indra (mod ϕ(m)) vôùi k nguyeân döông.
Chöùng minh. 1. rϕ(m) ≡ 1 (mod m), keùo theo indr1 = ϕ(m) ≡ 0 (mod ϕ(m)).
2. rindr(ab) ≡ ab ≡ rindra · rindrb ≡ rindra+indrb (mod m). Theo ñònh lyù 5.2 ta coù
indr(ab) ≡ indra + indrb (mod ϕ(m)).
3. rindrak≡ ak ≡ (rindra)k ≡ rk·indra (mod m), keùo theo
indrak ≡ k · indra (mod ϕ(m)).
Ví duï 5.4.1. Chuùng ta caàn giaûi ñoàng dö 7x ≡ 6 (mod 17). Deã daøng xaùc ñònh ñöôïc ϕ(17) = 16 vaø 3 laø caên nguyeân thuyû modulo 17. Nhö vaäy, baèng caùch laáy chæ soá vôùi cô sôû 3 modulo 17 caû hai veá, ta coù
ind37x ≡ ind36 = 15 (mod 16).
Vì
ind37x ≡ x · ind37 ≡ 11x (mod 16),
neân
11x ≡ 15 (mod 16).
Do 3 laø nghòch ñaûo cuûa 11 modulo 16, neân
x ≡ 3 · 15 = 45 ≡ 13 (mod 16).
5.4. CHÆ SOÁ SOÁ HOÏC 71
Giaû söû m, k laø caùc soá nguyeân döông vaø (a, m) = 1; ta seõ noùi a laø thaëng dö luõy thöøa k cuûa m neáuu ñoàng dö xk ≡ a (mod m) coù nghieäm.
Khi m coù caên nguyeân thuyû, ñònh lyù sau ñaây seõ cho moät tieâu chuaån ñeå xem soá nguyeân a nguyeân toá cuøng nhau vôùi m coù laø thaëng dö luõy thöøa k cuûa m hay khoâng.
Ñònh lyù 5.17. Giaû söû m coù caên nguyeân thuyû, k laø caùc soá nguyeân döông vaø (a, m)=1. Theá thì: ñoàng dö xk ≡ a (mod m) coù nghieäm khi vaø chæ khi
aϕ(m)/d ≡ 1 (mod m)
trong ñoù d = (k, ϕ(m)). Hôn nöõa, neáu ñoàng dö xk ≡ a (mod m) coù nghieäm thì coù ñuùng d nghieäm khoâng ñoàng dö nhau modulo m.
Chöùng minh. Giaû söû r laø caên nguyeân thuyû cuûa m. Ñoàng dö xk ≡ a (mod m)
töông ñöông vôùi
k · indrx ≡ indra (mod ϕ(m)).
Ñaët d = (k, ϕ(m)), y = indrx, hay cuõng vaäy x ≡ ry (mod m).
Ta ñaõ bieát ñoàng dö ky ≡ indra (mod ϕ(m)) khoâng coù nghieäm y khi d indra, hay cuõng vaäy, khoâng coù x thoûa
xk ≡ a (mod m).
Trong tröôøng hôïp d | indra, ñoàng dö ky ≡ indra (mod ϕ(m)) coù ñuùng d caùc nghieäm y khoâng ñoàng dö nhau modulo ϕ(m), do ñoù coù ñuùng d nghieäm x cuûa
xk ≡ a (mod m)
khoâng ñoàøng dö nhau modulo m.
Maët khaùc, ta coù
d | indra
töông ñöông vôùi
(ϕ(m)/d)indra ≡ 0 (mod ϕ(m)),
72 5. CAÊN NGUYEÂN THUÛY
hay
indraϕ(m)/d ≡ indr1 (mod ϕ(m)).
Ñoàng dö cuoái cuøng laïi töông ñöông vôùi
aϕ(m)/d ≡ 1 (mod m).
Trong ñònh lyù treân, neáu m = p laø soá nguyeân toá vaø (a, p)=1 thì a laø thaëng dö luõy thöøa k cuûa p khi vaø chæ khi
a(p−1)/d ≡ 1 (mod p)
trong ñoù d = (k, p − 1).
Ví duï 5.4.2. 1. Caàn xaùc ñònh xem 4 coù laø thaëng dö luõy thöøa naêm cuûa 11 hay khoâng, nghóa laø xeùt xem ñoàng dö
x5 ≡ 4 (mod 11)
coù nghieäm hay khoâng.
Ta coù
410/(5,10) = 42 = 16 ≡ 1 (mod 11),
vaäy 4 khoâng laø thaëng dö luõy thöøa naêm cuûa 11.
2. Ta coù 4 laø thaëng dö bình phöông cuûa 11 vì
410/(2,10) = 45 = 1024 ≡ 1 (mod 11),
vaäy 4 laø thaëng dö bình phöông cuûa 11.
BAØI TAÄP CHÖÔNG V
5.4. CHÆ SOÁ SOÁ HOÏC 73
1. Haõy tìm baäc cuûa caùc soá sau:
ord52; ord103; ord1310; ord107;
ord113; ord172; ord2110; ord259.
2. Haõy tìm taát caû caùc caên nguyeân thuyû cuûa caùc soá sau:
2; 3; 4; 5; 6; 7; 8; 9; 10.
3. Chöùng minh raèng:
neáu a¯ laø nghòch ñaûo cuûa a modulo m thì ordma = ordma. ¯
4. Chöùng minh raèng:
neáu (a, m)=(b, m)=(ordma, ordmb)=1 thì ordm(ab) = ordma·ordmb. 5. Chöùng minh raèng neáu (a, m)=1 vaø ordma = st thì ordmat = s.
6. Cho p laø soá nguyeân toá leû. Chöùng minh raèng r laø caên nguyeân thuyû modulo p khi vaø chæ khi
r(p−1)/q ≡ 1 (mod p)
ñoái vôùi moïi öôùc nguyeân toá q cuûa p.
7. Chöùng minh raèng neáu r¯ laø nghòch ñaûo cuûa r modulo m vaø r laø caên nguyeân thuyû cuûa m thì r¯ cuõng laø caên nguyeân thuyû cuûa m.
8. Giaû söû m = an − 1, vôùi a, n laø caùc soá nguyeân döông. Chöùng minh raèng ordma = n vaø n | ϕ(m).
9. Cho p, q laø caùc soá nguyeân toá leû khaùc nhau. Chöùng minh raèng pq laø soá giaû nguyeân toá cô sôû 2 khi vaø chæ khi ordq2 | (p − 1) , ordp2 | (q − 1).
10. Cho p, q laø caùc soá nguyeân toá leû khaùc nhau. Chöùng minh raèng pq laø soá giaû nguyeân toá cô sôû 2 khi vaø chæ khi MpMq = (2p − 1)(2q − 1) laø soá giaû nguyeân toá cô sôû 2.
11. Xaùc ñònh soá nghieäm khoâng ñoàng dö nhau modulo 11 cuûa caùc ña thöùc sau
x2 + 2; x2 + 10; x4 + x2 + 1.
12. Xaùc ñònh soá nghieäm khoâng ñoàng dö nhau modulo 13 cuûa caùc ña thöùc sau
x2 + 1; x2 + 3x + 2; x4 + x2 + x + 1.
74 5. CAÊN NGUYEÂN THUÛY
13. Cho p laø soá nguyeân toá leû. Chöùng minh raèng ñoàng dö x2 ≡ −1 (mod p) coù nghieäm khi vaø chæ khi p ≡ 1 (mod 4).
14. Giaû söû q vaø p = 2q + 1 laø caùc soá nguyeân toá, 1