Giáo trình Lý thuyết số - Vũ Văn Thông

139 trang phuongnguyen 9970

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết số - Vũ Văn Thông", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_so_vu_van_thong.pdf

Nội dung text: Giáo trình Lý thuyết số - Vũ Văn Thông

TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT F 7 G 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 neáu x ≥ 0 |x| = −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 k k−1 n = akb + ak−1b + ···+ 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: k k−1 n = akb + ak−1b + ···+ 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 =1ta chæ coù bieåu dieãn duy nhaát vôùi k =0, vaø a0 =1. Giaû söû ta coù k k−1 m m−1 n = akb + ak−1b + ···+ a1b + a0 = cmb + cm−1b + ···+ 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: k−1 k−2 m−1 m−2 n1 = akb + ak−1b + ···+ a1 = cmb + cm−1b + ···+ 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ù k k−1 n = ak2 + ak−12 + ···+ 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: k k−1 1) Soá nguyeân döông n = akb + ak−1b + ···+ 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 k k−1 n = akb + ak−1b + ···+ 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 k k−1 n = ak3 + ak−13 + ···+ 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 =2vaø 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)=1vaø a | bc thì a | c. Chöùng minh. Vì (a, b)=1neâ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 =2laø 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 1 ñeàu coù bieåu dieãn duy nhaát α1 αk n = p1 pk , 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 +∞ αk n = pk , k=0 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á +∞ +∞ αk βk a = pk vaø b = pk k=0 k=0 thì +∞ +∞ min{αk,βk} max{αk,βk} (a, b)= pk , [a, b]= pk vaø (a, b) · [a, b]=ab. k=0 k=0 Chöùng minh. Deã daøng thaáy raèng +∞ +∞ γk θk c = pk laø öôùc cuûa d = pk khi vaø chæ khi vôùi moïi k : γk ≤ θk. k=0 k=0 Töø ñaây deã daøng suy ra +∞ +∞ min{αk,βk} max{αk,βk} (a, b)= pk , [a, b]= pk . k=0 k=0
2.4. PHÖÔNG TRÌNH DIOPHANTUS TUYEÁN TÍNH 19 Ta coù +∞ +∞ min{αk,βk}+max{αk,βk} αk+βk (a, b) · [a, b]= pk = pk = ab. k=0 k=0 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 =20khoâ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 =2thì ñ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)=1thì (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)=1vaø c | a + b thì (c, a)=(c, b)=1. 5. Chöùng toû raèng neáu (a, b)=(a, c)=1thì (a, bc)=1. Toång quaùt hôn, neáu (a1,b)=(a2,b)=···=(an,b)=1thì (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)=1vaø 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   neáu  a a = b 2(a/2,b/2) neáu a, b cuøng chaün (a, b)= neáu chaün vaø leû  (a/2,b) a b (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)=1thì (an,bn)=1vôù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ì abc(a, b, c) [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: a) x + y + z = 100 b) x + y + z = 100 x +8y +50z = 156 x +6y +21z = 121 1 1 1 26. Tìm taát caû caùc nghieäm cuûa phöông trình Diophantus + = . x y 14
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(mod9)vì 9 | (22 − 4) = 18; −24 ≡ 3(mod9)vì 9 | (−24 − 3) = −27; 13 ≡ 5(mod9)vì 9 (13 − 5) = 8; 24 ≡−5(mod9) 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)=1thì 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)=1neâ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)=1thì 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(modm) 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)=1neân coù soá nguyeân yj thoaû ñoàng dö Mjyj ≡ 1(modmj). Ñ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(mod3) ≡  x 2(mod5) x ≡ 3(mod7) 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(mod3) 21y2 ≡ 1(mod5) 15y3 ≡ 1(mod7) 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:       a11 a12 ··· a1n x1 b1        a21 a22 ··· a2n   x2   b2  A =  .  , X =  .  , B =  .  .  .   .   .  an1 an2 ··· ann xn 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 n aikckj ≡ bikckj (mod m); k=1 k=1 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, i+j vôùi phaàn töû cij laø tích cuûa (−1) 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 ∆=detA. Theá thì A = ∆(adjA), laø nghòch ñaûo cuûa A modulo m. Chöùng minh. Ta coù A · adjA = adjA · A =(detA)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). 34 Ví duï 3.4.1. Giaû söû coù ma traän: A = . Vì 2 laø nghòch ñaûo cuûa 25 7=detA modulo 13, neân ta coù 5 −4 10 −8 10 5 A =2 = ≡ (mod 13). −23 −46 96 Ñò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(mod7) ≡  2x1 + x3 4(mod7) x1 +2x2 +3x3 ≡ 1(mod7) Ta coù det A = −5, (det A, 7) = 1. Nghòch ñaûo cuûa det A modulo 7 baèng 4.     256 −2 −35 Nghòch ñaûo cuûa A =  201 laø A =4 −5010 (mod 7). 123 41−10 Vaäy heä coù nghieäm laø           x1 −2 −35 3 −52 4           x2 ≡ 4 −5010· 4 = −20 ≡ 1 (mod 7). x3 41−10 1 24 3
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)=1neâ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(modp), 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(modp). Nhaân caùc veá vôùi (p − 1) ta coù (p − 1)! ≡ 1 · (p − 1) ≡−1(modp). Ñò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(modn) thì n laø soá nguyeân toá. Chöùng minh. Giaû söû n laø hôïp soá; ta coù n = ab vôùi 1 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: amodm= 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 m − 3 m − 1 − , − , , −1, 0, 1, , 2 2 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<j≤ m thì ari ≡ arj (mod m). Thaät vaäy, neáu ari ≡ arj (mod m) thì arj − ari | m, hay a(rj − ri) | m. Do (a, m)=1ta suy ra (rj − ri) | m vaø ñieàu naøy khoâng theå xaûy ra vì 0 <rj − ri <m. Ñònh lyù 3.14. Ñònh lyù nhoû Fermat. Neáu p laø soá nguyeân toá vaø p a thì ap−1 ≡ 1(modp). Chöùng minh. Khoâng coù soá naøo trong caùc soá a, 2a, ··· , (p − 1)a laø chia heát cho p; vì neáu p | ja thì do (a, p)=1neân p | j voâ lyù vôùi 1 ≤ j ≤ p − 1. Maët khaùc, deã daøng thaáy raèng (p − 1) soá a, 2a, ··· , (p − 1)a laø ñoâi moät khoâng ñoàng dö vôùi nhau modulo p; do ñoù chuùng ñoàng dö modulo p vôùi heä 1, 2, ··· ,p− 1. Vaäy: a · 2a ···(p − 1)a ≡ 1 · 2 ···(p − 1) (mod p). Suy ra: ap−1(p − 1)! ≡ (p − 1)! (mod p). Vì ((p − 1)!,p)=1, neân theo ñònh lyù 3.3 ta coù: ap−1 ≡ 1(modp).
36 3. ÑOÀNG DÖ Nhaän xeùt: 1. Ñònh lyù nhoû Fermat noùi raèng neáu n laø soá nguyeân toá vaø b laø soá nguyeân baát kyø thì bn ≡ b (mod n). Ñieàu naøy cuõng coù nghóa laø neáu coù soá nguyeân b ñeå bn ≡ b (mod n) thì n laø hôïp soá hoaëc n =1. 2. Neáu b laø moät soá nguyeân döông, n laø hôïp soá vaø bn ≡ b (mod n) thì ta noùi n laø soá giaû nguyeân toá cô sôû b. 3. Hôïp soá n ñöôïc goïi laø soá Carmichael neáu bn ≡ b (mod n) vôùi moïi soá nguyeân döông b maø (b, n)=1. Ñoái vôùi moãi soá nguyeân döông n, chuùng ta kyù hieäu ϕ(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. Haøm soá ϕ(n) ñöôïc goïi laø phi-haøm Euler. Taäp goàm ϕ(m) caùc soá nguyeân ñöôïc goïi laø heä thaëng dö thu goïn modulo m neáu moïi soá nguyeân nguyeân toá cuøng nhau vôùi m ñeàu ñoàng dö 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ø heä thaëng dö ûthu goïn modulo m khi vaø chæ khi heä naøy coù ñuùng ϕ(m) soá, nguyeân toá cuøng nhau vôùi m vaø ñoâi moät khoâng ñoàng dö vôùi nhau modulo m. Ví duï 3.5.2. Caùc soá 1, 3, 5, 7 laø heä thaëng dö ûthu goïn modulo 8. Caùc soá −3, −1, 1, 3 cuõng laø heä thaëng dö ûthu goïn modulo 8. Heä goàm (p − 1) : soá 1, 2, ··· ,p− 1 laø heä thaëng dö thu goïn modulo nguyeân toá p. Ñònh lyù 3.15. Neáu caùc soá r1,r2, , rϕ(m) laø moät heä thaëng dö thu goïn modulo m vaø a nguyeân toá cuøng nhau vôùi m thì heä ar1,ar2, ··· ,arϕ(m) cuõng laø moät heä thaëng dö thu goïn modulo m. Chöùng minh. Heä ar1,ar2, ··· ,arϕ(m) goàm ϕ(m) soá nguyeân. Töø (a, m)=(rj,m)=1deã daøng suy ra (arj,m)=1;vaäy moãi soá cuûa heä nguyeân toá cuøng nhau vôùi m.
3.5. ÑÒNH LYÙ WILSON VAØ ÑÒNH LYÙ EULER 37 Neáu coù 1 ≤ i<j≤ ϕ(m) ñeå ari ≡ arj (mod m) thì m | a(ri − rj). Do (m, a)=1ta suy ra m | (ri − rj), hay ri ≡ rj (mod m), ñieàu naøy voâ lyù vôùi giaû thieát ri ≡ rj (mod m). Ñònh lyù sau ñaây laø moät môû roäng cuûa ñònh lyù Fermat Ñònh lyù 3.16. Ñònh lyù Euler. Neáu m laø soá nguyeân döông vaø (a, m)=1thì aϕ(m) ≡ 1(modm). Chöùng minh. Laáy heä thaëng dö thu goïn ar1,ar2, ··· ,arϕ(m). Do (a, m)=1, neân töø ñònh lyù treân ta coù ar1,ar2, ··· ,arϕ(m) cuõng laø heä thaëng dö thu goïn. Vaäy caùc soá cuûa heä naøy ñoàng dö modulo m vôùi caùc soá cuûa heä kia. Vaäy ar1ar2 ···arϕ(m) ≡ r1r2 ···rϕ(m) (mod m) Hay ϕ(m) a r1r2 ···rϕ(m) ≡ r1r2 ···rϕ(m) (mod m) ϕ(m) Vì (r1r2 ···rϕ(m),m)=1ta suy ra a ≡ 1(modm). Ñònh lyù Euler coù raát nhieàu öùng duïng. Chaúng haïn, ta coù theå deã daøng xaùc ñònh nghòch ñaûo a cuûa soá nguyeân a modulo m. Ta ñaõ bieát raèng soá nguyeân a coù nghòch ñaûo modulo m khi vaø chæ khi (a, m)=1. Do Ñònh lyù Euler: a · aϕ(m)−1 = aϕ(m) ≡ 1(modm), ta coù a = aϕ(m)−1. Ví duï 3.5.3. Tìm nghòch ñaûo modulo 10 cuûa 3. Giaûi phöông trình 3x ≡ 8 (mod 10). Ta coù 3=3ϕ(10)−1 =34−1 =27≡ 7 (mod 10). 3x ≡ 8 (mod 10) ⇔ 3·3x ≡ 3·8 (mod 10) ⇔ x ≡ 7·8 (mod 10) ⇔ x ≡ 6 (mod 10) BAØI TAÄP CHÖÔNG III
38 3. ÑOÀNG DÖ 1. Giaû söû a, b, c laø caùc soá nguyeân, c>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(modpk). 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(mod7) e) 6x ≡ 3(mod9) 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(mod7) b) 2x +4y ≡ 6(mod8) c) 6x +3y ≡ 0(mod9) 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(modpk) coù ñuùng hai nghieäm khoâng ñoàng dö nhau modulo pk, ñoù laø x ≡±1(modpk). 9. Chöùng minh raèng ñoàng dö x2 ≡ 1(mod2k) coù ñuùng boán nghieäm khoâng ñoàng dö nhau modulo 2k, ñoù laø x ≡±1(modpk) hoaëc x ≡±(1 + 2k−1 (mod pk) khi k>2. Chöùng toû raèng khi k =1thì chæ coù moät nghieäm vaø khi k =2thì 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 ≡ 1(mod2) x ≡ 4 (mod 11) a) b) x ≡ 2(mod3) x ≡ 3 (mod 17)  x ≡ 3(mod5) 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   x ≡ a1 (mod m1)  x ≡ a2 (mod m2) .  .  x ≡ ak (mod mk) 13. Giaûi caùc heä ñoàng dö sau ≡ ≡ a) x +3y 1(mod5) b) 4x + y 2(mod5) 3x +4y ≡ 2(mod5) 2x +3y ≡ 1(mod5) ≡ ≡ c) 2x +3y 5(mod7) d) 4x + y 5(mod7) x +5y ≡ 6(mod7) x +2y ≡ 4(mod7)
40 3. ÑOÀNG DÖ 14. Giaûi caùc heä ñoàng dö sau   2x +3y + z ≡ 3(mod5) a) ≡  x +2y +3z 1(mod5) 2x + z ≡ 1(mod5)   3x + y +3z ≡ 1(mod7) b) ≡  x +2y +4z 2(mod7) 4x +3y +2z ≡ 3(mod7)   2x + y + z ≡ 3 (mod 11) c) ≡  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(mod4)thì ñoàng dö x2 ≡−1(modp) 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 <k<pthì (p − k)!(k − 1)! ≡ (−1)k (mod p). 18. Haõy söû duïng ñònh lyù Fermat ñeå tìm thaëng dö döông nhoû nhaát cuûa 21000000 modulo 17. 19. Haõy söû duïng ñònh lyù Fermat ñeå tìm chöõ soá cuoái cuøng cuûa 3100 trong heä ñeám cô soá 7. 20. Haõy söû duïng ñònh lyù Fermat ñeå giaûi caùc phöông trình a) 7x ≡ 12 (mod 17) , b) 4x ≡ 11 (mod 19). 21. Chöùng minh raèng neáu p, q laø caùc soá nguyeân toá khaùc nhau thì pq−1 + qp−1 ≡ 1(modpq). 22. Chöùng minh raèng neáu p laø soá nguyeân toá, a, b laø caùc soá nguyeân vaø ap ≡ bp (mod p) thì ap ≡ bp (mod p2).
3.5. ÑÒNH LYÙ WILSON VAØ ÑÒNH LYÙ EULER 41 23. Haõy söû duïng ñònh lyù Euler ñeå tìm chöõ soá cuoái cuøng cuûa: a) 71000. b) 51000000 trong heä thaäp luïc phaân. 24. Haõy tìm moät heä thaëng dö thu goïn modulo 2m. 25. Chöùng minh raèng neáu m>2 vaø c1,c2, ··· ,cϕ(m) laø heä thaëng dö thu goïn modulo m thì c1 + c2 + ···+ cϕ(m) ≡ 0(modm). 26. Chöùng toû raèng ϕ(m1) ϕ(m2) ϕ(mk) x ≡ a1M1 + a2M2 + ···+ akMk (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)=1vôù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ø N F (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 α1 α2 αk Ñònh lyù 4.1. Giaû söû f laø haøm coù tính nhaân vaø n = p1 p2 ···pk laø khai trieån luõy thöøa nguyeân toá cuûa soá nguyeân döông n thì α1 α2 αk f(n)=f(p1 )f(p2 ) ···f(pk ). Chöùng minh. Vì i = j thì pi vaø pj laø caùc soá nguyeân toá khaùc nhau, ta suy ra α1 α2 αk−1 αk (p1 p2 ···pk−1 ,pk )=1, töø ñoù α1 α2 αk−1 αk α1 α2 αk−1 αk f(p1 p2 ···pk−1 pk )=f(p1 p2 ···pk−1 )f(pk ). Ñònh lyù 4.2. Neáu f coù tính nhaân thì haøm g(n)= f(d) d|n cuõng coù tính nhaân. Chöùng minh. Haøm g khoâng ñoàng nhaát baèng khoâng, vì g(1) = f(1) = 1. d|1 α1 α2 αr β1 β2 βs Giaû söû m = p1 p2 ···pr vaø n = q1 q2 ···qs 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)=1thì 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 α1 α2 αr β1 β2 βs mn = p1 p2 ···pr q1 q2 ···qs ñöôï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)= f(d)= f(d1d2). d|mn d1 | m d2 | n Vì f coù tính nhaân vaø (d1,d2)=1neân f(d1d2)=f(d1)f(d2), suy ra g(mn)= f(d1)f(d2)= f(d1) f(d2)=g(m)g(n). d | m 1 d1 | m d2 | n d2 | 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)| B. 3. Vôùi moïi ε>0 ñeàu coù soá N(ε), chæ phuï thuoäc vaøo ε, sao cho |f(pm)| N(ε). Giaû söû α1 α2 αk n = p1 p2 ···pk laø khai trieån luõy thöøa nguyeân toá cuûa soá nguyeân döông n>1. Theá thì α1 α2 αk f(n)=f(p1 )f(p2 ) ···f(pk ). 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 + bj1 m ≡ ai2 n + bj2 m (mod mn). Theá thì ai1 n + bj1 m ≡ ai2 n+bj2 m (mod m). Suy ra m | (ai1 −ai2 )n. Do(m, n)=1neâ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)=1neâ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)=1töông ñöông vôùi (ain + bjm, m)=1 ⇔ (ain, m)=1 ⇔ (ai,m)=1 (ain + bjm, n)=1 (bjm, n)=1 (bj,n)=1 Vì coù ϕ(m) caùc ai thoaû (ai,m)=1vaø ϕ(n) caùc bj thoaû (bj,n)=1neâ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 α1 α2 αk Ñònh lyù 4.6. Neáu n = p1 p2 ···pk laø khai trieån luõy thöøa nguyeân toá cuûa soá nguyeân döông n thì 1 1 1 ϕ(n)=n(1 − )(1 − ) ···(1 − ). p1 p2 pk Ví duï 4.2.1. 1 1 ϕ(100) = ϕ(2252) = 100(1 − )(1 − )=40 2 5 vaø 1 1 1 ϕ(720) = ϕ(24325) = 720(1 − )(1 − )(1 − ) = 192. 2 3 5 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ì 1 n>ϕ(n)=n(1 − ) >n(1 − ε). p Töø ñaây ta nhaän ñöôïc ñònh lyù sau Ñònh lyù 4.7. ϕ(n) lim =1. n→∞ n 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ù ϕ(n) lim = ∞. n→∞ n1−δ Chöùng minh. Vì haøm n1−δ f(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ù pm(1−δ) pm−mδ p−mδ 0 <f(pm)= = = ≤ 2(pm)−δ → 0 khi pm →∞. ϕ(pm) pm(1 − 1/p) 1 − 1/p
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 = ϕ(n/d)= ϕ(d). d|n d|n 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)=1laø coù tính nhaân. Theo ñòng lyù 4.2, ta suy ra caùc haøm σ(n)= d = f1(d); τ(n)= 1= f2(d) d|n d|n d|n d|n laø coù tính nhaân. α1 α2 αk Ñònh lyù 4.11. Neáu n = p1 p2 ···pk laø khai trieån luõy thöøa nguyeân toá cuûa soá nguyeân döông n thì k k αi+1 pi − 1 σ(n)= − ; τ(n)= (αi +1). i=1 pi 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 − 1 σ(pα)=1+p + ···+ pα = . p − 1 Vaäy k k αi+1 − αi p 1 σ(n)= σ(pi )= − . i=1 i=1 pi 1 2. Vì pα chæ coù (α +1)öôùc döông laø pi, 0 ≤ i ≤ α, neân τ(pα)=(α +1). Vaäy k k αi τ(n)= τ(pi )= (αi +1). i=1 i=1 Ví duï 4.3.2. 52 − 1 172 − 1 232 − 1 σ(1955) = σ(5 · 17 · 23) = · · = 2592 5 − 1 17 − 1 23 − 1 τ(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ù τ(n) lim =0. n→∞ nδ Chöùng minh. Vì haøm τ(n) f(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ù m +1 2m 2 log pm 2 log pm 0 <f(pm)= ≤ = · ≤ · → 0 khi pm →∞. pmδ pmδ log p pmδ log 2 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. 1, neáu n =1, µ(d)= 0, neáu n>1. d|n α1 α2 αm Chöùng minh. Giaû söû n = p1 p2 ···pm 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<j),pipjpk (i<j<k), , p1p2 pm. Theá thì µ(d)=µ(1) + µ(pi)+ µ(pipj)+···+ µ(p1p2 pm) d|n i i<j Vaäy m m m m µ(d)=1− + − ···=(1− 1) =0. 1 2 1 d|n Nhaän xeùt raèng, haøm Mo¨bius coù theå ñöôïc ñònh nghóa nhôø ñònh lyù 4.15. Caùc aùp duïng quan troïng cuûa haøm naøy thöôøng döïa treân caùc qui taéc bieán ñoåi coù teân Mo¨bius. Ñònh lyù 4.16. Bieán ñoåi ngöôïc Mo¨bius thöù nhaát. Giaø söû f laø haøm soá hoïc. Khi ñoù ta coù: g(n)= f(d) d|n khi vaø chæ khi n f(n)= µ(d)g( ). d|n d
52 4. CAÙC HAØM SOÁ HOÏC Chöùng minh. ⇒ . Ta coù n µ(d)g( )= µ(d) f(d)= µ(d)f(d)= f(d) µ(d). d|n d d|n d| n dd|n d|n d| n d d Theo ñònh lyù 4.15 thì neáu n vaø µ(d)=0 > 1 µ(d)=1, d| n d d| n d n neân ta suy ra n µ(d)g( )= f(d) µ(d)= f(d) µ(d)=f(n). d|n d d|n d| n d=n d| n d n ⇐ . Vì n f(n)= µ( )g(d), d|n d ta suy ra n n n f(d)= f( )= µ( )g(d )= µ( )g(d ). d|n d|n d d|n d| n dd dd|n dd d Theo ñònh lyù 4.15 thì neáu n vaø µ(d)=0 > 1 µ(d)=1, d| n d d| n d n neân ta suy ra n n f(d)= µ( )g(d )= g(d ) µ( )= g(d ) µ(d)=g(n). d|n dd|n dd d|n d| n dd d=n d| n d 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 g(n)= ϕ(d)=n. d|n Theo dònh lyù 4.16, ta coù n n µ(d) ϕ(n)= µ(d)g( )= µ(d) = n . d|n d d|n d d|n d [x] Ñoái vôùi soá thöïc x, ta kyù hieäu ñeå chæ , vaø toång ñöôïc hieåu laø baèng 0 n≤x n=1 neáu noù khoâng chöùa soá haïng naøo. Ñò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ø x g(x)= f( ). n≤x n Khi ñoù, vôùi x ≥ 1 x f(x)= µ(n)g( ) n≤x n vaø ngöôïc laïi. Chöùng minh. ⇒ . Töø ñònh nghóa cuûa haøm g, khi x ≥ 1, ta coù x x x µ(n)g( )= µ(n) f( )= µ(n)f( ) n≤x n n≤x m≤ x mn 1≤mn≤x mn n Nhoùm toång sau cuøng theo mn = r, 1 ≤ r ≤ x, ta ñöôïc x x µ(n)f( )= f( ) µ(n)=f(x). 1≤mn≤x mn 1≤r≤x r n|r ⇐ . Töø x f(x)= µ(n)g( ), n≤x n
54 4. CAÙC HAØM SOÁ HOÏC ta suy ra x x x f( )= µ(n)g( )= µ(n)g( ). m≤x m m≤x n≤ x mn 1≤mn≤x mn m Cuõng nhö tröôùc, ta coù x x µ(n)g( )= g( ) µ(n)=g(x). 1≤mn≤x mn 1≤r≤x r n|r 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)= f(d)g(n/d). d|n 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 1 neáu n =1 ι(n)= 0 neáu n>1 (Nhôù laïi: ι(n)= µ(d).) d|n 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 ϕ(n) neáu n leû ϕ(2n)= 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 σk(n)= d . d|n α 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 α1 α2 αk toá n = p1 p2 ···pk . 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 N T (N)= τ(n). n=1 a) Chöùng minh raèng N N T (N)= . n=1 n b) Chöùng minh raèng √ [ N] √ N T (N)=−[ N]2 +2 . n=1 n 100 AÙp duïng tính 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 α1 α2 αk neáu n coù khai trieån thaønh luõy thöøa nguyeân toá n = p1 p2 ···pk thì µ(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)=1thì aϕ(m) ≡ 1(modm). Ñ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(modm) ñöôï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(mod7), 22 ≡ 4(mod7), 23 ≡ 1(mod7). Vaäy ord72=3. Töông töï, ñeå tìm baäc cuûa 3 modulo 7, ta coù: 31 ≡ 3(mod7), 32 ≡ 2(mod7), 33 ≡ 6(mod7) 34 ≡ 4(mod7), 35 ≡ 5(mod7), 36 ≡ 1(mod7) 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 x döông x laø nghieäm cuûa ñoàng dö a ≡ 1(modn) 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(modn). ⇐ . Theo thuaät toaùn chia, x = q · ordna + r, 0 ≤ r 0: a ≡ a (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)=1neân töø ñoàng dö treân ta suy ra ai−j ≡ 1(modn). 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 5 11 6 20 ta coù: 3 ≡ 3 (mod 14) vì ord143 | (11 − 5); vaø 3 ≡ 3 (mod 14) vì ord143 | (20 − 6). Ñònh lyù 5.3. Neáu ordma = t vaø u laø soá nguyeân döông thì u t ordm(a )= . (t, u) u Chöùng minh. Giaû söû s = ordm(a ),ν=(t, u),t= t1ν, u = u1ν. Theá thì (t1,u1)=1. Ta coù (au)t1 =(au1ν)t/ν =(at)u1 ≡ 1(modm). Töø ñònh lyù 5.1 ta coù s | t1. Maët khaùc, do aus =(au)s ≡ 1(modm) 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)=1neâ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 2 Ví duï 5.1.5. ord143=6,ord149=ord143 =6/(6, 2) = 3, 3 4 ord1427 = ord143 =6/(6, 3) = 2,ord1481 = ord143 =6/(6, 4) = 3, 5 6 ord14243 = ord143 =6/(6, 5) = 6,ord14729 = ord143 =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)=1vaø 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)=1vôùi 1 ≤ k ≤ ϕ(n) vaø ri ≡ rj (mod n) vôùi 1 ≤ i = j ≤ ϕ(n). Töø (r, n)=1deã daøng suy ra (rk,n)=1vôù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ì u ordmr m ord (r )=(u,ordmr) ϕ(m) = (u,ϕ(m)) . u Nhö vaäy, ordm(r )=ϕ(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(modm). 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(mod7)vaø x ≡ 4(mod7). Ña thöùc g(x)=x2 +2laø 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(modp). n Ñònh lyù 5.7. Ñònh lyù Lagrange. Giaû söû p laø soá nguyeân toá; f(x)=anx + n−1 an−1x +···+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(modp) 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)=1thì 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)= n n−1 anx +an−1x +···+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(modp) vôùi moïi 0 ≤ k ≤ n. Khi ñoù ta coù n n n−1 n−1 f(x) − f(c0)= an(x − c0 )+an−1(x − c0 )+···+ a1(x − c0) n−1 n−2 n−2 n−1 = an(x − c0)(x + x c0 + ···+ xc0 + c0 )+ n−2 n−3 n−3 n−2 +an−1(x − c0)(x + x c0 + ···+ xc0 + c0 )+ . . +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(modp). Nhöng vôùi moïi k, 1 ≤ k ≤ n, ck ≡ c0 (mod p); hay (ck − c0,p)=1. Vaäy g(ck) ≡ 0(modp), 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(modp) khi vaø chæ khi (xd − 1) ≡ 0(modp) hoaëc g(x) ≡ 0(modp). Do xp−1 − 1 ≡ 0(modp) 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(modp) 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(modp) 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= F (d). d|p−1 Maët khaùc, theo ñònh lyù refdl39 ta coù p − 1= ϕ(d). d|p−1 Vaäy F (d)= ϕ(d). d|p−1 d|p−1 Ñ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)=0thì 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(modp), vì (ak)d =(ad)k ≡ 1(modp). Töø ñònh lyù 5.8 ta suy ra raèng, moãi nghieäm cuûa (xd − 1) ≡ 0(modp) ñ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, k a 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ù rn ≡ 1(modp2). Suy ra rn ≡ 1(modp). Theo ñònh lyù 5.1 thì p − 1=ordp | n. Ta cuõng coù 2 n = ordp2 r | ϕ(p )=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 2 2 n = p(p − 1) thì r laø caên nguyeân thuyû modulo p vì ordp2 r = n = ϕ(p ). Ngöôïc laïi, neáu n = p − 1 ta coù rp−1 = rn ≡ 1(modp2).
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ù p−1 p−1 p−1 p−2 p − 1 p−3 2 p−1 s =(r + p) = r +(p − 1)r p + r p + ···+ p 2 vaø rp−1 ≡ 1(modp2) neân sp−1 ≡ rp−1 +(p − 1)prp−2 ≡ 1 − prp−2 (mod p2). Vì (r, p)=1neân prp−2 ≡ 0(modp2), suy ra sp−1 ≡ 1(modp2), hay ordp2 s = p − 1. Ví duï 5.3.1. Ta ñaõ bieát r =3laø caên nguyeân thuyû modulo p =7. Söû duïng ñònh lyù ?? ta coù ord493=p − 1=6hoaëc ord493=p(p − 1) = 42. Do r6 =36 = 729 ≡ 1 (mod 49) ta suy ra r =3laø 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ù k−2 rp (p−1) ≡ 1(modpk). pk−2(p−1) p−1 2 2 Khi k =2, ta coù r = r ≡ 1(modp ), vì ordp2 r = ϕ(p )=p(p−1). Giaû söû raèng vôùi soá nguyeân k ≥ 2 ta ñaõ coù k−2 rp (p−1) ≡ 1(modpk).
66 5. CAÊN NGUYEÂN THUÛY Vì (r, pk−1)=1neân theo ñònh lyù Euler, ta coù k−2 k−1 rp (p−1) = rϕ(p ) ≡ 1(modpk−1), vaø ñieàu naøy keùo theo k−2 rp (p−1) =1+dpk−1 k−2 trong ñoù p d vì rp (p−1) ≡ 1(modpk). Luõy thöøa p hai veá cuûa ñoàng dö treân, ta ñöôïc pk−1(p−1) k−1 p k−1 p k−1 2 k−1 p r =(1+dp ) =1+p(dp )+ (dp ) + ···+(dp ) . 2 Suy ra k−1 rp (p−1) ≡ 1+dpk (mod pk+1). Nhöng p d neân k−1 rp (p−1) ≡ 1(modpk+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(modpk) neân rn ≡ 1(modp); 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ì k−2 t rp (p−1) =(rp (p−1))k−2−t =(rn)k−2−t ≡ 1(modpk), k−2 vaø ñieàu naøy voâ lyù vôùi ñieàu ñaõ ñöôïc chöùng minh laø rp (p−1) ≡ 1(modpk). k−1 k Vaäy n = p (p − 1), vaø ñieàu naøy noùi leân raèng ordpk r = ϕ(p ), 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ì k aϕ(2 )/2 ≡ 1(mod2k).
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 3 aϕ(2 )/2 =(2b +1)2 =4b(b +1)+1≡ 1(mod23). k k+1 Giaû söû ñaõ coù aϕ(2 )/2 ≡ 1(mod2k), ta caàn chöùng minh raèng aϕ(2 )/2 ≡ 1 (mod 2k+1). Vì ϕ(2n)=2n(1 − 1/2) = 2n−1 neân töø giaû thieát qui naïp ta coù k−2 a2 ≡ 1(mod2k), suy ra k−2 a2 =1+d2k. Bình phöông caû hai veá, ta ñöôïc k−1 a2 =1+d2k+1 + d222k ≡ 1(mod2k+1), ñieàu naøy keùo theo k+1 k−1 aϕ(2 )/2 = a2 ≡ 1(mod2k). 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á t1 t2 tm n = p1 p2 ···pm . Goïi p laø thöøa soá nguyeân toá cuûa n, do (r, pt)=1neân t rϕ(p ) ≡ 1(modpt). Ñaët t1 t2 tm U =[ϕ(p1 ),ϕ(p2 ), ··· ,ϕ(pm )].
68 5. CAÊN NGUYEÂN THUÛY ti Vì ϕ(pi ) | U neân theo ñònh lyù Trung hoa veà phaàn dö ta coù rU ≡ 1(modn). Ñieàu naøy keùo theo ordnr = ϕ(n) ≤ U. Nhöng t1 t2 tm ϕ(n)=ϕ(p1 )ϕ(p2 ) ···ϕ(pm ), ta suy ra t1 t2 tm t1 t2 tm ϕ(p1 )ϕ(p2 ) ···ϕ(pm ) ≤ [ϕ(p1 ),ϕ(p2 ), ··· ,ϕ(pm )]. Vaäy t1 t2 tm t1 t2 tm ϕ(p1 )ϕ(p2 ) ···ϕ(pm )=[ϕ(p1 ),ϕ(p2 ), ··· ,ϕ(pm )]. t1 t2 tm Ñaúng thöùc cuoái cuøng xaûy ra chæ khi caùc soá nguyeân ϕ(p1 ),ϕ(p2 ), ··· ,ϕ(pm ) laø ñoâi moät nguyeân toá cuøng nhau. 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 t1 t2 tm p =2vaø t ≥ 2. Nhö vaäy, caùc soá nguyeân ϕ(p1 ),ϕ(p2 ), ··· ,ϕ(pm ) laø khoâng ñoâi moät nguyeân toá cuøng nhau, ngoaïi tröø tröôøng hôïp m =1hoaëc m =2vaø 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ù t rϕ(p ) ≡ 1(modpt) 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 t rϕ(2p ) ≡ 1(modpt). Neáu r leû thì t rϕ(2p ) ≡ 1(mod2).
5.4. CHÆ SOÁ SOÁ HOÏC 69 Vì (2,pt)=1, ta suy ra t rϕ(2p ) ≡ 1(mod2pt). Deã thaáy khoâng coù soá muõ nguyeân döông naøo nhoû hôn ϕ(2pt)=ϕ(pt) coù tính t chaát treân, do ñoù ord2pt r = ϕ(2p ). Neáu r chaün thì r + pt laø soá leû. Do ñoù t (r + pt)ϕ(2p ) ≡ 1(mod2). Maët khaùc, vì r + pt ≡ r (mod pt) neân t (r + pt)ϕ(2p ) ≡ 1(modpt). Suy ra t (r + pt)ϕ(2p ) ≡ 1(mod2pt). Cuõng thaáy raèng khoâng coù soá muõ nguyeân döông naøo nhoû hôn ϕ(2pt)=ϕ(pt) t t coù tính chaát treân, do ñoù ord2pt (r + p )=ϕ(2p ). 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)). k 3. indra ≡ k · indra (mod ϕ(m)) vôùi k nguyeân döông. ϕ(m) Chöùng minh. 1. r ≡ 1(modm), 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)). k 3. rindra ≡ ak ≡ (rindra)k ≡ rk·indra (mod m), keùo theo k indra ≡ 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ù x ind37 ≡ ind36 = 15 (mod 16). Vì x ind37 ≡ 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(modm) 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)). y Ñaët d =(k, ϕ(m)),y= indrx, hay cuõng vaäy x ≡ r (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 ϕ(m)/d indra ≡ indr1(modϕ(m)). Ñoàng dö cuoái cuøng laïi töông ñöông vôùi aϕ(m)/d ≡ 1(modm). Trong ñònh lyù treân, neáu m = p laø soá nguyeân toá vaø (a, p)=1thì a laø thaëng dö luõy thöøa k cuûa p khi vaø chæ khi a(p−1)/d ≡ 1(modp) 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)=1thì ordm(ab)=ordma·ordmb. t 5. Chöùng minh raèng neáu (a, m)=1vaø ordma = st thì ordma = 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(modp) ñ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á p q giaû nguyeân toá cô sôû 2 khi vaø chæ khi MpMq =(2 − 1)(2 − 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(modp) coù nghieäm khi vaø chæ khi p ≡ 1(mod4). 14. Giaû söû q vaø p =2q +1 laø caùc soá nguyeân toá, 1 <a<p− 1. Chöùng minh raèng p − a2 laø caên caên nguyeân thuyû modulo p. 15. Caùc soá nguyeân naøo trong caùc soá töø 1 ñeán 100 coù caên nguyeân thuyû. 16. Xaùc ñònh taát caû caùc caên nguyeân thuyû modulo 22, modulo 25, modulo 38. 17. Chöùng minh raèng m coù caên nguyeân thuyû khi vaø chæ khi ñoàng dö x2 ≡ 1 (mod m) chæ coù caùc nghieäm laø x ≡±1(modm). 18. Giaû söû n coù caên nguyeân thuyû. Baèng caùch söû duïng caên nguyeân thuyû, haõy chöùng minh raèng tích cuûa taát caû caùc soá nguyeân döông nhoû hôn n vaø nguyeân toá cuøng nhau vôùi n laø ñoàng dö vôùi −1 modulo n. (Khi n laø soá nguyeân toá, ta nhaän ñöôïc ñònh lyù Wilson.) 19. Xaùc ñònh taát caû caùc nghieäm cuûa ñoàng dö: a) 3x5 ≡ 1 (mod 23); b) 3x14 ≡ 2 (mod 23); c) 3x ≡ 2 (mod 23); d) 13x ≡ 5 (mod 23). 20. Tìm caùc soá nguyeân a ñeå ñoàng dö sau coù nghieäm: a) ax4 ≡ 2 (mod 13); b) 8x7 ≡ a (mod 29). 21. Söû duïng chæ soá vôùi cô sôû 2 modulo 13 ñeå tìm nghieäm cuûa 2x ≡ x (mod 13). 22. Xaùc ñònh taát caû caùc nghieäm cuûa ñoàng dö: xx ≡ x (mod 23). 23. Cho p laø soá nguyeân toáû leû vaø r laø caên nguyeân thuyû cuûa p. Chöùng minh raèng indr(p − 1) = (p − 1)/2. 24. Giaû söû p laø soá nguyeân toáû leû. Chöùng minh raèng ñoàng dö x4 ≡−1 (mod p) coù nghieäm khi vaø chæ khi p ≡ 1(mod8). 25. Chöùng minh raèng coù voâ soá soá nguyeân toá daïng 8k +1.
6 THAËNG DÖ BÌNH PHÖÔNG 6.1 Thaëêng dö bình phöông Giaû söû m laø soá nguyeân döông. Chuùng ta noùi raèng soá nguyeân a laø thaëng dö bình phöông cuûa m neáuu (a, m)=1vaø ñoàng dö x2 ≡ a (mod m) coù nghieäm. Neáu ñoàng dö x2 ≡ a (mod m) khoâng coù nghieäm thì ta noùi a laø khoâng thaëng dö bình phöông. Ví duï 6.1.1. Ñeå tìm caùc thaëng dö bình phöông cuûa 11 chuùng ta tính bình phöông cuûa taát caû caùc soá 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Ta thaáy 12 ≡ 102 ≡ 1 (11), 22 ≡ 92 ≡ 4 (11), 32 ≡ 82 ≡ 9 (11), 42 ≡ 72 ≡ 5 (11), 52 ≡ 62 ≡ 3 (11). Nhö vaäy, caùc thaëêng dö bình phöông cuûa 11 laø: 1, 3, 4, 5, 9; caùc khoâng thaëng dö bình phöông cuûa 11 laø: 2, 6, 7, 8, 10. Chuùng ta seõ chæ ra raèng neáu p laø soá nguyeân toá leû thì soá caùc thaëng dö bình phöông baèng soá caùc khoâng thaëng dö bình phöông cuûa p trong daõy 1, 2, ··· ,p− 1. Ñònh lyù 6.1. Neáu p laø soá nguyeân toá leû vaø p a thì ñoàng dö x2 ≡ a (mod p) hoaëc khoâng coù nghieäm hoaëc coù ñuùng hai nghieäm khoâng ñoàng dö nhau modulo p. 2 Chöùng minh. Giaû söû ñoàng dö x ≡ a (mod p) coù nghieäm x = x0. Ta thaáy 2 2 x = −x0 cuõng laø nghieäm, vì (−x0) = x0 ≡ a (mod p). Nhöng x0 ≡−x0 (mod p); vì neáu traùi laïi thì p | x0 − (−x0)=2x0, ñieàu naøy keùo theo p | x0, vaø nhö vaäy p | a. 75
76 6. THAËNG DÖ BÌNH PHÖÔNG 2 Giaû söû x = x1 laø moät nghieäm cuûa ñoàng dö x ≡ a (mod p). Theá thì 2 2 2 2 x1 ≡ a ≡ x0 (mod p). Suy ra p | x1 − x0 =(x1 − x0)(x1 + x0); ñieàu naøy keùo theo p | (x1 − x0) hoaëc p | (x1 + x0), hay cuõng vaäy x1 ≡ x0 (mod p) hoaëc x1 ≡−x0 (mod p). Ñònh lyù 6.2. Neáu p laø soá nguyeân toá leû thì soá caùc thaëng dö bình phöông baèng soá caùc khoâng thaëng dö bình phöông cuûa p trong daõy 1, 2, ··· ,p− 1. Chöùng minh. Ñeå xaùc ñònh taát caû caùc caùc thaëng dö bình phöông cuûa p trong daõy 1, 2, ··· ,p− 1 chuùng ta tính caùc thaëng dö döông nhoû nhaát modulo p cuûa bình phöông cuûa taát caû caùc soá 1, 2, ··· ,p− 1. Vì coù caû thaûy p − 1 caùc bình phöông vaø moãi ñoàng dö x2 ≡ a (mod p) hoaëc khoâng coù nghieäm hoaëc coù ñuùng hai nghieäm, ta suy ra coù ñuùng (p − 1)/2 caùc thaëng dö bình phöông, vaø do ñoù coù p − 1 − (p − 1)/2=(p − 1)/2 caùc khoâng thaëng dö bình phöông cuûa p. Giaû söû p laø øsoá nguyeân toá leû vaø p a. Ta ñònh nghóa kyù hieäu Legendre a 1 neáu a laø thaëng dö bình phöông cuûa p := p −1 neáu a laø khoâng thaëng dö bình phöông cuûa p Ví duï 6.1.2. Trong ví duï tröôùc ñaõ chæ ra 1 3 4 5 9 = = = = =1, 11 11 11 11 11 2 6 7 8 10 = = = = = −1. 11 11 11 11 11 Sau ñaây chuùng ta ñöa ra tieâu chuaån cuûa soá nguyeân laø thaëng dö bình phöông cuûa soá nguyeân toá. Ñònh lyù 6.3. Tieâu chuaån Euler. Neáu p laø soá nguyeân toá leû vaø p a thì a ≡ a(p−1)/2 (mod p). p a Chöùng minh. Tröôøng hôïp =1. Khi ñoù, ñoàng dö x2 ≡ a (mod p) coù p nghieäm, giaû söû laø x = x0. Theo ñònh lyù Fermat, ta coù (p−1)/2 2 (p−1)/2 p−1 a ≡ (x0) = x0 ≡ 1(modp).
6.1. THAËÊNG DÖ BÌNH PHÖÔNG 77 a Tröôøng hôïp = −1. Khi ñoù, ñoàng dö x2 ≡ a (mod p) khoâng coù nghieäm. p Vôùi moïi i, 1 ≤ i ≤ p − 1, ñeàu coù duy nhaát j, 1 ≤ j ≤ p − 1 ñeå ij ≡ a (mod p); nhöng do x2 ≡ a (mod p) voâ nghieäm neân i = j. Nhö vaäy ta coù theå nhoùm caùc soá 1, 2, ··· ,p− 1 thaønh (p − 1)/2 caëp coù tích ñoàng dö vôùi a modulo p. Vaäy (p − 1)! ≡ a(p−1)/2 (mod p). Theo ñònh lyù Wilson, (p − 1)! ≡−1(modp), neân ta suy ra a(p−1)/2 ≡−1(modp). Heä quaû 6.3.1. Neáu p laø soá nguyeân toá leû thì −1 1 neáu p ≡ 1(mod4) = p −1 neáu p ≡−1(mod4) Ñònh lyù 6.4. Neáu p laø soá nguyeân toá leû vaø p a, p b thì a b a) Neáu a ≡ b (mod p) thì = . p p ab a b b) = . p p p a2 c) =1. p Chöùng minh. a) Neáu a ≡ b (mod p) thì x2 ≡ a (mod p) coù nghieäm khi vaø chæ khi x2 ≡ b (mod p) coù nghieäm, hay a b = . p p b) Theo tieâu chuaån Euler, ta coù ab a b ≡ (ab)(p−1)/2 = a(p−1)/2b(p−1)/2 ≡ (mod p). p p p a c) Do = ±1, neân p a2 a a = =1. p p p
78 6. THAËNG DÖ BÌNH PHÖÔNG Ñònh lyù 6.5. Boå ñeà Gauss. Neáu p laø soá nguyeân toá leû vaø (a, p)=1vaø s laø soá caùc thaëng dö döông nhoû nhaát lôùn hôn p/2 cuûa caùc soá a, 2a, ··· , ((p − 1)/2)a thì a =(−1)s. p Chöùng minh. Giaû söû u1,u2, ··· ,us laø caùc thaëng dö döông nhoû nhaát lôùn hôn p/2 vaø v1,v2, ··· ,vt laø caùc thaëng dö döông nhoû nhaát nhoû hôn p/2 cuûa caùc soá a, 2a, ··· , ((p − 1)/2)a. Vì (ja,p)=1vôùi moïi j, 1 ≤ j ≤ (p − 1)/2 neân caùc thaëng dö döông nhoû nhaát thuoäc 1, 2, ··· ,p− 1. Chuùng ta seõ chæ ra raèng taäp {p − u1,p− u2, ··· ,p− us,v1,v2, ··· ,vt} chính laø taäp {1, 2, ··· , (p − 1)/2}. Vì (p − 1)/2 soá p − u1,p− u2, ··· ,p− us,v1,v2, ··· ,vt ñeàu nhoû hôn (p − 1)/2 neân ta chæ caàn chöùng toû raèng chuùng khoâng ñoàng dö nhau modulo p. Hieån nhieân p − ui ≡ p − uj (mod p) cuõng nhö vi ≡ vj (mod p) neáu i = j; vì neáu khoâng thì ta suy ra ma ≡ na (mod p), hay m ≡ n (mod p), vaø ñieàu naøy khoâng xaûy ra vôùi m = n maø 1 ≤ m, n ≤ (p − 1)/2. Töông töï, chuùng ta cuõng thaáy p − ui ≡ vj (mod p); vì neáu khoâng thì −m ≡ n (mod p), vaø ñieàu naøy khoâng theå xaûy ra khi m = n vaø 1 ≤ m, n ≤ (p − 1)/2. Vaäy thì p − 1 (p − u1)(p − u2) ···(p − us)v1v2 ···vt = ! 2 hay s p − 1 (−1) u1u2 ···usv1v2 ···vt = ! 2 Do (p−1)/2 p − 1 p − 1 a !=a · 2a ··· a ≡ u1u2 ···usv1v2 ···vt (mod p) 2 2 Suy ra p − 1 p − 1 (−1)sa(p−1)/2 ! ≡ !(modp). 2 2 Vì (p, ((p − 1)/2)!) = 1 neân (−1)sa(p−1)/2 ≡ 1(modp). Suy ra a ≡ a(p−1)/2 ≡ (−1)s (mod p). p
6.1. THAËÊNG DÖ BÌNH PHÖÔNG 79 Ñònh lyù 6.6. Neáu p laø soá nguyeân toá leû thì 2 2 =(−1)(p −1)/8. p Do ñoù, 2 laø thaëng dö bình phöông cuûa moïi soá nguyeân toá p ≡±1(mod8)vaø khoâng laø thaëng dö bình phöông cuûa moïi soá nguyeân toá p ≡±3(mod8). Chöùng minh. Theo boå ñeà Gauss, goïi s laø soá caùc thaëng dö döông nhoû nhaát lôùn hôn p/2 cuûa caùc soá 1 · 2, 2 · 2, ··· , ((p − 1)/2) · 2, thì 2 =(−1)s. p Vì taát caû caùc soá 1 · 2, 2 · 2, ··· , ((p − 1)/2) · 2 ñeàu nhoû hôn p neân soá caùc thaëng dö döông nhoû nhaát lôùn hôn p/2 chính baèng soá caùc soá lôùn hôn p/2 trong daõy 1 · 2, 2 · 2, ··· , ((p − 1)/2) · 2. Soá chaün 2j, vôùi 1 ≤ j ≤ (p − 1)/2, khoâng vöôït quaù p/2 khi j ≤ p/4. Vaäy s =(p − 1)/2 − [p/4]. Suy ra 2 =(−1)(p−1)/2−[p/4]. p Ñeå keát thuùc chöùng minh ñònh lyù, chuùng ta chæ caàn chöùng toû raèng p − 1 − [p/4] ≡ (p2 − 1)/8(mod2). 2 Xeùt tröôøng hôïp p =8k +1, ta coù p − 1 − [p/4] = 4k − [2k +1/4] = 2k ≡ 0 ≡ ((8k +1)2 − 1)/8(mod2). 2 Tröôøng hôïp p =8k +3, ta coù p − 1 −[p/4] = 4k+1−[2k+3/4] = 2k+1 ≡ 1 ≡ ((8k+3)2 −1)/8(mod2). 2 Tröôøng hôïp p =8k +5, ta coù p − 1 −[p/4] = 4k+2−[2k+5/4] = 2k+1 ≡ 1 ≡ ((8k+5)2 −1)/8(mod2). 2 Cuoái cuøng, vôùi p =8k +7, ta coù p − 1 −[p/4] = 4k+3−[2k+7/4] = 2k+2 ≡ 0 ≡ ((8k+7)2 −1)/8(mod2). 2
80 6. THAËNG DÖ BÌNH PHÖÔNG Ví duï 6.1.3. Caàn xaùc ñònh xem 111 coù laø thaëng dö bình phöông modulo 43 hay khoâng. Vì 111 ≡−18 (mod 43) neân ta coù 111 −18 −1 18 9 2 3 2 2 2 = = = − = − = − =1. 43 43 43 43 43 43 43 43 43 Vaäy 111 laø thaëng dö bình phöông modulo 43. 6.2 Luaät thuaän nghòch bình phöông Giaû söû p, q laø caùc soá nguyeân toá leû khaùc nhau vaø ta ñaõ bieát raèng p coù laø thaëng dö bình phöông modulo q hay khoâng. Nhôø vaäy, lieäu ta coù theå noùi ñöôïc gì veà vieäc q coù laø thaëng dö bình phöông modulo p? Luaät thuaän nghòch bình phöông seõ cho ta caâu traû lôøi veà vaán ñeà naøy. Ñeå chöùng minh luaät thuaän nghòch bình phöông, tröôùc heát chuùng ta chöùng minh ñònh lyù sau. Ñònh lyù 6.7. Neáu p laø soá nguyeân toá leû vaø a laø soá leû khoâng chia heát cho p thì a =(−1)T (a,p), p vôùi (p−1)/2 T (a, p)= [ja/p]. j=1 Chöùng minh. Giaû söû u1,u2, ··· ,us laø caùc thaëng dö döông nhoû nhaát lôùn hôn p/2 vaø v1,v2, ··· ,vt laø caùc thaëng dö döông nhoû nhaát nhoû hôn p/2 cuûa caùc soá a, 2a, ··· , ((p − 1)/2)a. Theo thuaät toaùn chia, ta coù ja = p[ja/p]+rj , trong ñoù rj laø moät uj hoaëc vj . Nhö vaäy, (p−1)/2 (p−1)/2 s t ja = p[ja/p]+ uj + vj. j=1 j=1 j=1 j=1
6.2. LUAÄT THUAÄN NGHÒCH BÌNH PHÖÔNG 81 Nhö trong chöùng minh boå ñeà Gauss ñaõ chæ ra raèng taäp {p−u1,p−u2, ··· ,p− us,v1,v2, ··· ,vt} cuõng chính laø taäp {1, 2, ··· , (p − 1)/2}, neân (p−1)/2 s t s t j = (p − uj)+ vj = ps − uj + vj. j=1 j=1 j=1 j=1 j=1 Suy ra (p−1)/2 (p−1)/2 (p−1)/2 s ja − j = p[ja/p] − ps +2 uj, j=1 j=1 j=1 j=1 hay (p−1)/2 s (a − 1) j = pT (a, p) − ps +2 uj. j=1 j=1 Vì a, p leû neân ta suy ra T (a, p) ≡ s (mod 2). Vaäy a =(−1)s =(−1)T (a,p). p 7 Ví duï 6.2.1. Ñeå xaùc ñònh , ta tính 11 5 [j · 7/11] = [7/11] + [14/11] + [21/11] + [28/11] + [35/11] = 7. j=1 Vaäy 7 =(−1)7 = −1. 11 Ñònh lyù 6.8. Luaät thuaän nghòch bình phöông. Neáu p, q laø caùc soá nguyeân toá leû khaùc nhau thì p q p−1 · q−1 =(−1) 2 2 . q p
82 6. THAËNG DÖ BÌNH PHÖÔNG Chöùng minh. Chuùng ta xeùt caùc caëp soá nguyeân (x, y) vôùi 1 ≤ x ≤ (p − 1)/2 vaø ≤ ≤ − Coù caû thaûy p−1 · q−1 caëp nhö vaäy. Chuùng ta chia caùc 1 y (q 1)/2. 2 2 caëp naøy thaønh hai nhoùm. Tröôùc heát ta coù nhaän xeùt laø qx = py vôùi moïi caëp (x, y). Nhoùm thöù nhaát goàm caùc caëp (x, y) maø qx > py, vaø nhoùm thöù hai goàm caùc caëp (x, y) maø qx < py. Ta thaáy nhoùm thöù nhaát goàm caùc caëp (x, y) maø 1 ≤ x ≤ (p − 1)/2 vaø 1 ≤ y ≤ qx/p. Ñoái vôùi moãi x coá ñònh, 1 ≤ x ≤ (p − 1)/2, coù ñuùng [qx/p] caùc soá y thoaû 1 ≤ y ≤ qx/p. Nhö vaäy nhoùm thöù nhaát coù soá caëp laø (p−1)/2 [qj/p]. j=1 Töông töï, ta thaáy nhoùm thöù hai coù soá caëp laø (q−1)/2 [pj/q]. j=1 Vaäy (p−1)/2 (q−1)/2 p − 1 q − 1 [qj/p]+ [pj/q]= · , j=1 j=1 2 2 söû duïng kyù hieäu cuûa ñònh lyù 6.7 ta coù p − 1 q − 1 T (q,p)+T (p, q)= · . 2 2 Theo ñònh lyù 6.7 ta suy ra p q T (p,q) T (q,p) T (p,q)+T (q,p) p−1 · q−1 =(−1) · (−1) =(−1) =(−1) 2 2 . q p Nhaän xeùt:   q neáu ≡ hoaëc ≡  p 1(mod4) q 1(mod4); p p = q  q  neáu p ≡ q ≡ 3(mod4). p