Giáo trình "Lý thuyết số" trình làng đến các bạn những câu chữ về số nguyên, ước chung lớn nhất, sự đối chiếu ra vượt số nguyên tố, đồng dư, những hàm số học, căn thủy căn,... Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.




Bạn đang xem: Lý thuyết số


TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT F7G GIAÙO TRÌNHLYÙ THUYEÁT SOÁ VUÕ VAÊN THOÂNGMUÏC LUÏC1 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 . . . . . . . . . . . . . . . . . . . . . . . 72 ÖÔÙC chung LÔÙN NHAÁT. SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ. 13 2.1 Öôùc bình thường 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 . . . . . . . . . . . . . . . 193 Ñ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 . . . . . . . . . . . . . . . . 344 CAÙC HAØM SOÁ HOÏC 43 4.1 Nhaän xeùt tầm thường . . . . . . . . . . . . . . . . . . . . . . . . . . 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 12 MUÏC LUÏC5 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 dỡ . . . . . . . . . . . . . . . 61 5.3 Caùc soá coù caên nguyeân thuyû . . . . . . . . . . . . . . . . . . . 64 5.4 Chæ soá soá hoïc . . . . . . . . . . . . . . . . . . . . . . . . . . . 696 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 tháo Euler . . . . . . . . . . . . . . . . . . . . . 877 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 .... . . . . . . . . . . . 1188 MOÄT VAØI PHÖÔNG TRÌNH DIOPHANTUS PHI TUYEÁN 125 8.1 Caùc boä bố Pythagoras . . . . . . . . . . . . . . . . . . . . . . 125 8.2 Toång cuûa hai soá chủ yếu phöông . . . . . . . . . . . . . . . . . . 126 8.3 Toång cuûa boán soá thiết yếu phöông . . . . . . . . . . . . . . . . . 128 8.4 Phöông trình Pell . . . . . . . . . . . . . . . . . . . . . . . . . 1311SOÁ NGUYEÂN1.1 Vaønh soá nguyeânVaø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ùcpheùp toaùn coäng vaø nhaân làm 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 liêu heä nhì 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). Coi nhö baøi taäp, yeâu caàu ñoïc giaû töï kieåm tra tính ñuùng ñaén cuûa ñònhnghóa caùc pheùp toaùn neâu treân vaø chöùng toû raèng (Z, +, ·) laø moät vaønh giaohoaù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ø 34 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. Lúc ñ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; vị ñ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 1.2. CAÙC TÍNH CHAÁT CÔ BAÛN CUÛA Z 5Chöù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åuchöù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öûanhoù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 liêu 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 ≤ xyTreân Z ta ñöa ra quan lại heä 2-ngoâi ≤ nhö sau: x ≤ y neáuu y − x ∈ N. Deã thaáyñaây laø quan lại heä thöù töï treân Z vaø laø môû roäng cuûa quan tiền 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 đến ñ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≤0Caùc tính chaát veà trò tuyeät ñoái coi nhö ñaõ roõ.Ñònh lyù 1.4. Giaû söû M laø taäp khoâng roãng caùc soá nguyeân. Lúc ñ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ø trườn chaëntreân. Ñaët A = M ∩ N. Neáu A = ∅ phaàn töû lôùn nhaát b cuûa A seõ laø phaàntöû 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ôùib = min −x : x ∈ M . Ñoïc giaû töï chöùng minh mang đến tröôøng hôïp taäp M trườn chaën döôùi. 6 1. SOÁ NGUYEÂN1.3 Pheùp chia trong ZChuùng ta noùi raèng soá nguyeân a phân chia heát mang đến soá nguyeân b = 0, tuyệt a laø boäicuûa b, kyù hieäu a :. B, neáuu coù soá nguyeân c ñeå a = bc. Trong tröôøng hôïp naøyta cuõng noùi laø b phân chia chia heát a, xuất xắc 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 đến b, hay b khoâng phân tách heát a, kyùhieäu b  a.Ví duï 1.3.1.6 | 12 ; −5 | đôi mươi ; 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. Lúc ñ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. Lúc ñoù toàn taïi duy nhaát caùcsoá nguyeân q, r thoûa: a = bq + r vaø 0 ≤ r 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 nhị öôùc döông bởi vì noù phân tách heát cho 1 vaø chủ yếu noù. Soá nguyeân lôùn hôn 1 maø noù coù ñuùng nhị öôùc döông, ñöôïc goïi laø soá nguyeântoá. 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ânChuùng ta ñaõ quen vôùi vieäc bieåu dieãn caùc soá nguyeân vào 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á mang lại vieäc bieåu dieãn caùc soá nguyeân. Vaøvì moãi soá nguyeân aâm laø soá ñoái cuûa soá nguyeân döông neân ñònh lyù sau ñaây laøcaên baûn.Ñònh lyù 1.7. Giaû söû b > 1 laø moät soá nguyeân. Theá thì, moïi soá nguyeân döông nñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng n = ak bk + ak−1 bk−1 + · · · + a1 b + a0trong ñ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 mang lại 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: q.1 = bq2 + a2 , 0 ≤ a2 ≤ b − 1, q2 = bq3 + a3 , 0 ≤ a3 ≤ b − 1, .. .8 1. SOÁ NGUYEÂN qk−2 = bqk−1 + ak−1 , 0 ≤ ak−1 ≤ b − 1, qk−1 = b.0 + ak , 0 ≤ ak ≤ b − 1. Deã daøng suy ra: n = ak bk + ak−1 bk−1 + · · · + a1 b + a0vôùi ø 0 ≤ aj ≤ b − 1, ak = qk−1 = 0. Ta seõ chöùng minh tính duy nhaát cuûa bieåu dieãn baèng qui naïp theo soánguyeân döông n. Tröôøng hôïp n = 1 ta chæ coù bieåu dieãn duy nhaát vôùi k = 0, vaø a0 = 1. Giaûsöû ta coùn = ak bk + ak−1 bk−1 + · · · + a1 b + a0 = cm bm + cm−1 bm−1 + · · · + c1 b + c0 . (∗)Do ñònh lyù 1.6: phaàn dö cuûa pheùp chia n mang lại b laø duy nhaát, neân a0 = c0. Doa0 = c0 neân töø (*) ta suy ra: n1 = ak bk−1 + ak−1 bk−2 + · · · + a1 = centimet bm−1 + cm−1 bm−2 + · · · + c1 .Deã chöùng toû ñöôïc raèng n1 1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 9Ví duï 1.4.1. Chuùng ta caàn ñoåi soá thaäp phaân 610 thanh lịch heä nhò phaân. Bởi vì trongheä 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 chiacho 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 phân chia döøng do thöông ñaõ baèng 0. Caùc soá dö vieát vào 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 vào 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 trọng heä thaäp luïc phaân. Vìsoá thaäp luïc vào heä thaäp phaân ñöôïc vieát laø 16 neân ta thöïc hieän lieân tieáp caùcpheùp phân tách cho 16 trong heä thaäp phaân: 2003 = 16 · 125 + 3, 125 = 16 · 7 + 13, 7 = 16 · 0 + 7. Thuaät phân chia döøng vị thöông ñaõ baèng 0. Caùc soá dö vieát trong heä thaäp luïcphaân töông öùng laø: c0 = 3, c1 = D, c2 = 7; vaäy soá ñaõ cho coù bieåu dieãn trongheä thaäp luïc phaân laø 7D3.  BAØI TAÄP CHÖÔNG I10 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 bé 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 phân chia cho 7 vaø mang đến −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ö vào pheùp phân tách cho 17 vaø mang lại −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 lúc vaø chæ lúc 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 quý phái heä sang trọng 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 quý phái 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 lịch sự 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.4. BIEÅU DIEÃN SOÁ NGUYEÂN 11 14. Chöùng minh raèng moïi soá nguyeân n = 0 ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng n = ak 3k + ak−1 3k−1 + · · · + a1 3 + a0 vào ñ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 a n − 1 laø soá nguyeân tháo thì a = 2 vaø n laø soá nguyeân toá. 18. Chöùn√g minh raèng neáu n laø hôïp soá thì noù coù öôùc nguyeân tháo dỡ khoâng vöôït quaù n. 19. Chöùng minh√raèng neáu öôùc nguyeân cởi nhoû nhaát p cuûa soá nguyeân döông n vöôït quaù n thì n/p laø soá nguyeân tháo hoaëc baèng 1. 312 1. SOÁ NGUYEÂN2ÖÔÙC tầm thường LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁNGUYEÂN TOÁ.2.1 Öôùc chung lôùn nhaátNeá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 chungcuûa a vaø b laø höõu haïn vaø chöùa caùc soá +1 vaø −1. Chuùng ta seõ quan tiền taâm ñeánsoá nguyeân lôùn nhaát naèm trong caùc öôùc bình thường naøy. Öôùc bình thường lôùn nhaát cuûa nhì 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 phổ biến lôùn nhaát cuûa nhị soá nguyeân a vaø b ñöôïc kyù hieäu laø (a, b). Khaùi nieäm öôùc bình thường lôùn nhaát cuûa cuûa caùc soá nguyeân khoâng ñoàng thôøibaèng khoâng a1 , a2 , · · · , an ñöôïc hieåu hoaøn toaøn töông töï nhö khaùi nieämöôùc thông thường lôùn nhaát cuûa cuûa caùc soá nguyeân. Ñoù chính laø soá nguyeân lôùn nhaátchia heát ñoàng thôøi taát caû caùc aj , 1 ≤ j ≤ n. Öôùc thông thường lôùn nhaát cuûa cuûa caùcsoá nguyeân a1 , a2 , · · · , an ñöôïc kyù hieäu laø (a1 , a2 , · · · , an ).Ví duï 2.1.1. Öôùc phổ biến 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. 1314 2. ÖÔÙC phổ biến LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ.  Chuùng ta cuõng quan liêu taâm ñeán caùc caëp soá nguyeân maø chuùng khoâng coù öôùcchung lôùn hôn 1. Caùc caëp soá nguyeân nhö vaäy ñöôïc goïi laø nguyeân túa cuøngnhau. 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 thông thường cuûa a vaø b; töø ñoù de ≤ d; suy ra e = 1. Neáu u laø moät öôùc thông thường cuûa a vaø b, thì vì chưng ñònh lyù 1.5 ta coù u | (a + cb);vaäy u laø öôùc bình thường cuûa a + cb vaø b. Ngöôïc laïi, neáu u laø moät öôùc tầm thường cuûaa + cb vaø b, thì cuõng do ñònh lyù 1.5 ta coù u | (a + cb) − cb = a; vaäy u laø öôùcchung 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ántí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ínhchaá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õngthuoä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öôøngM chủ yếu laø taäp taát caû caùc boäicuû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 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 bao gồm 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ândöô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 rae ≤ d. Maët khaùc, do d | (ax + by) vôùi moïi x, y ∈ Z neân d phân tách heát moïi phaàntöû 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 thông thường lôùn nhaát cuûa nhị soá nguyeân avaø 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 tầm thường 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ânlaø öôùc tầm thường cuûa an vaø an+1 , vày ñoù c laø öôùc cuûa (an , an+1 ). Vaäy c laø öôùcchung cuûa caùc soá a1 , a2 , · · · , an−1 , (an , an+1 ). Ngöôïc laïi, hieån nhieân moãi öôùc tầm thường 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áuthuaät toaùn chia ñöôïc thöïc hieän lieân tieáp rj = rj+1 qj+1 + rj+2, 0 16 2. ÖÔÙC bình thường 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 = r1 q 1 + r2 0 2.3. ÑÒNH LYÙ CÔ BAÛN CUÛA SOÁ HOÏC 172.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 tháo dỡ theo thöù töïkhoâng giaûm. Tröôùc lúc chöùng minh ñònh lyù cô baûn, chuùng ta chöâng minh nhị boå ñeà sauñaây.Boå ñeàù 2.6.1. Neáu a, b, c laø caùc soá nguyeân döông sao để cho (a, b) = 1 vaø a | bcthì a | c.Chöùng minh. Do (a, b) = 1 neân theo ñònh lyù 2.3, coù caùc soá nguyeân x, y saocho ax + by = 1. Nhaân nhị 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 túa cuûa tích a1 a2 · · · ak , ôû ñaây a1 , a2 , · · · , aklaø 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 = 1laø taàm thöôøng. Giaû söû p laø öôùc nguyeân toá cuûa tích a1 a2 · · · ak ak+1 . Neáup  ak+1 ta suy ra (p, ak+1 ) = 1; vaäy theo boå ñeà 2.6.1 ta coù p | a1 a2 · · · 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öôønghôïp n = 2 laø taàm thöôøng. Soá nguyeân n+1 > 2 neáu laø soá nguyeân toá thì khoângcoù 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 n = pα1 1 ... Pαk k , vôùi 1 ≤ k, 0 18 2. ÖÔÙC phổ biến 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 tháo ñöôïc saép theo thöù töï taêng daàn: p1 = 2 2.4. PHÖÔNG TRÌNH DIOPHANTUS TUYEÁN TÍNH 19Ta coù  +∞ minαk ,βk +maxαk ,βk  +∞ (a, b) · = chiến đấu = pαk k +βk = ab. K=0 k=0 Ví duï 2.3.1. Öôùc phổ biến lôùn nhaát cuûa 2100 = 22 · 3 · 52 · 7, 40 = 23 · 5 baèng22 · 5 = 20. Boäi bình thường 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ínhCaùc phöông trình maø chuùng ta chæ xeùt chuùng vào 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 a1 x1 + a2 x2 + · · · + an xn = ctrong ñ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). Lúc ñ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 làm thế nào cho ax + by = c. Vì d | a vaø d | b neân d | ax + by = c, voâ lyù vôùi giaû thieát d  c.

Xem thêm: Top 13 Kể Về Một Việc Tốt Mà Em Đã Làm Khiến Bố Mẹ Vui Lòng ❤️️

2. Theo heä quaû 2.3.1 thì coù caùc soá nguyeân s, t ñeå as + bt = d.