Giáo trình "Lý thuyết số" ra mắt đến các bạn những ngôn từ về số nguyên, ước chung lớn nhất, sự đối chiếu ra vượt số nguyên tố, đồng dư, các hàm số học, căn thủy căn,... Hy vọng đó là tài liệu xem thêm 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 phân chia trong Z . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Bieåu dieãn soá nguyeân . . . . . . . . . . . . . . . . . . . . . . . 72 ÖÔÙC thông thường LÔÙN NHAÁT. SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ. 13 2.1 Öôùc thông 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ö nước 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 phổ biến . . . . . . . . . . . . . . . . . . . . . . . . . . 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 toá . . . . . . . . . . . . . . . 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 toá 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ä ba Pythagoras . . . . . . . . . . . . . . . . . . . . . . 125 8.2 Toång cuûa nhì soá thiết yếu phöông . . . . . . . . . . . . . . . . . . 126 8.3 Toång cuûa boán soá bao gồm 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 thế nào 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 lại 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 tiền 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 ñò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. 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; 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 bé 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 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≤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 trườn chaën döôùi thì M chöùa soá nhoû nhaát.Chöùng minh. Chuùng toâi chæ chöùng minh đến tröôøng hôïp taäp M laø bò 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 đến tröôøng hôïp taäp M bò 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 tách heát đến soá nguyeân b = 0, xuất xắc 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 cho b, xuất xắc b khoâng phân tách 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. 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. Khi ñ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 vì chưng noù phân chia heát cho một vaø chủ yếu noù. Soá nguyeân lôùn hôn 1 maø noù coù ñuùng hai öôù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 thuộc 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 đến 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 phân tách q0 đến 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, quận 2 = 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 = centimet bm + cm−1 bm−1 + · · · + c1 b + c0 . (∗)Do ñònh lyù 1.6: phaàn dö cuûa pheùp phân tách n đến 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 = cm 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 sang heä nhò phaân. Vì chưng 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 vày 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ùcpheùp chia cho 16 vào heä thaäp phaân: 2003 = 16 · 125 + 3, 125 = 16 · 7 + 13, 7 = 16 · 0 + 7. Thuaät chia döøng bởi vì thöông ñaõ baèng 0. Caùc soá dö vieát vào heä thaäp luïcphaân töông öùng laø: c0 = 3, c1 = D, c2 = 7; vaäy soá ñaõ mang đến 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 nhỏ 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 tách cho 7 vaø đế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 đến −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 làm 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ä lịch sự 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 thanh lịch 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 trọng 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 thế nào cho a n − 1 laø soá nguyeân tháo dỡ 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 toá khoâng vöôït quaù n. 19. Chöùng minh√raèng neáu öôùc nguyeân toá nhoû nhaát phường cuûa soá nguyeân döông n vöôït quaù n thì n/p laø soá nguyeân túa hoaëc baèng 1. 312 1. SOÁ NGUYEÂN2ÖÔÙC bình thường LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁNGUYEÂN TOÁ.2.1 Öôùc phổ biến 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 vào caùc öôùc chung naøy. Öôùc bình thường 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 phân tách heát ñoàng thôøi caû a vaø b. Öôùc chung 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 chung 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 phổ biến lôùn nhaát cuûa cuûa caùc soá nguyeân. Ñoù bao gồm laø soá nguyeân lôùn nhaátchia 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ùcsoá nguyeân a1 , a2 , · · · , an ñöôïc kyù hieäu laø (a1 , a2 , · · · , an ).Ví duï 2.1.1. Öôùc thông thường 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 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 tháo 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 làm 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 bình thường cuûa a vaø b, thì bởi ñò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 phổ biến cuûaa + cb vaø b, thì cuõng vì chưng ñò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ính 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ì chưng 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ủ yếu laø taäp taát caû caùc boäi cuûa moät soá nguyeândöông e naøo ñoù. Vì chưng 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, vì 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 bình thường lôùn nhaát cuûa nhị soá nguyeân avaø b. Lúc ñ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 thông thường c cuûa caùc soá a1 , a2 , · · · , an , an+1 hieån nhieânlaø öôùc thông 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 thông 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 phân tách ñöôï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 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 hai boå ñeà sauñaây.Boå ñeàù 2.6.1. Neáu a, b, c laø caùc soá nguyeân döông làm sao để cho (a, b) = 1 vaø a | bcthì a | c.Chöùng minh. Vày (a, b) = 1 neân theo ñònh lyù 2.3, coù caùc soá nguyeân x, y saocho 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 dỡ 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 cởi 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ù phường | 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 thông thường 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 túa ñöôï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) ·
Xem thêm: ✅ Bài Tập Toán Đổi Đơn Vị Đo Độ Dài Lớp 3 ⭐️⭐️⭐️⭐️⭐️, Kiến Thức Về Bảng Đơn Vị Đo Độ Dài
2. Theo heä quaû 2.3.1 thì coù caùc soá nguyeân s, t ñeå as + bt = d.