Giáo trình Lý thuyết số

Chia sẻ: Nguyễn Duy | Ngày: | Loại File: PDF | Số trang:139

Thêm vào BST

Báo xấu

977
lượt xem 110
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình "Lý thuyết số" giới thiệu đến các bạn những nội dung về số nguyên, ước chung lớn nhất, sự phân tích ra thừa số nguyên tố, đồng dư, các 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Lý thuyết số

TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT F7G 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. Zlaø 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 n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 trong ñoù k laø soá nguyeân khoâng aâm, caùc aj laø soá nguyeân vôùi 0 ≤ aj ≤ b − 1 vaø heä soá ñaàu tieân ak = 0. Chöùng minh. Töø ñònh lyù 1.6 ta coù: n = bq0 + a0 , 0 ≤ a0 ≤ b − 1. Neáu q0 = 0, tieáp tuïc chia q0 cho b ta ñöôïc: q0 = bq1 + a1 , 0 ≤ a1 ≤ b − 1. Tieáp tuïc quaù trình naøy ñeán luùc ñaït ñöôïc: q1 = bq2 + a2 , 0 ≤ a2 ≤ b − 1, q2 = bq3 + a3 , 0 ≤ a3 ≤ b − 1, .. .
8 1. SOÁ NGUYEÂN qk−2 = bqk−1 + ak−1 , 0 ≤ ak−1 ≤ b − 1, qk−1 = b.0 + ak , 0 ≤ ak ≤ b − 1. Deã daøng suy ra: n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 vôùi ø 0 ≤ aj ≤ b − 1, ak = qk−1 = 0. Ta seõ chöùng minh tính duy nhaát cuûa bieåu dieãn baèng qui naïp theo soá nguyeân döông n. Tröôøng hôïp n = 1 ta chæ coù bieåu dieãn duy nhaát vôùi k = 0, vaø a0 = 1. Giaû söû ta coù n = 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 cho b laø duy nhaát, neân a0 = c0. Do a0 = 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 < n, vaäy theo giaû thieát qui naïp ta coù: m = k vaø a1 = c1 , · · · , ak = ck . Heä quaû 1.7.1. Moïi soá nguyeân döông ñeàu laø toång caùc luõy thöøa khaùc nhau cuûa 2. Chöùng minh. Theo ñònh lyù 1.7 vôùi b = 2, ta coù n = ak 2k + ak−1 2k−1 + · · · + a1 2 + a0 , vôùi k laø soá töï nhieân, caùc aj baèng 0 hoaëc 1, ak = 0. Nhaän xeùt: 1) Soá nguyeân döông n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 trong ñònh lyù 1.7 thöôøng ñöôïc vieát laø (ak ak−1 · · · a1 a0 )b . 2) Vieäc ñoåi soá nguyeân döông (ak ak−1 · · · a1 a0 )q trong heä ñeám cô soá q sang cô soá b ñöôïc thöïc hieän hoaøn toaøn töông töï nhö thuaät toaùn tìm bieåu dieãn cuûa soá nguyeân döông trong ñònh lyù 1.7 chæ löu yù laø khi chia cho b (trong heä q−phaân) thì b ñaõ ñöôïc vieát trong heä q−phaân, sau ñoù caùc soá dö phaûi ñöôïc ñoåi sang heä b−phaân ñeå bieåu dieãn soá trong heä b−phaân.
1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 9 Ví duï 1.4.1. Chuùng ta caàn ñoåi soá thaäp phaân 610 sang heä nhò phaân. Vì trong heä thaäp phaân nhò vaãn ñöôïc vieát laø 2 neân ta thöïc hieän lieân tieáp caùc pheùp chia cho 2 trong heä thaäp phaân: 106 = 2 · 53 + 0, 53 = 2 · 26 + 1, 26 = 2 · 13 + 0, 13 = 2 · 6 + 1, 6 = 2 · 3 + 0, 3 = 2 · 1 + 1, 1 = 2 · 0 + 1. Thuaät chia döøng vì thöông ñaõ baèng 0. Caùc soá dö vieát trong heä nhò phaân töông öùng laø: c0 = 0, c1 = 1, c2 = 0, c3 = 1, c4 = 0, c5 = 1, c6 = 1; vaäy soá ñaõ cho coù bieåu dieãn trong heä nhò phaân laø 1101010. Ví duï 1.4.2. Chuùng ta caàn ñoåi soá thaäp phaân 2003 sang heä thaäp luïc phaân. Vì soá thaäp luïc trong heä thaäp phaân ñöôïc vieát laø 16 neân ta thöïc hieän lieân tieáp caùc pheùp chia cho 16 trong heä thaäp phaân: 2003 = 16 · 125 + 3, 125 = 16 · 7 + 13, 7 = 16 · 0 + 7. Thuaät chia döøng vì thöông ñaõ baèng 0. Caùc soá dö vieát trong heä thaäp luïc phaân töông öùng laø: c0 = 3, c1 = D, c2 = 7; vaäy soá ñaõ cho coù bieåu dieãn trong heä thaäp luïc phaân laø 7D3. BAØI TAÄP CHÖÔNG I
10 1. SOÁ NGUYEÂN 1. Chöùng minh tính ñuùng ñaén cuûa ñònh nghóa pheùp coäng, pheùp nhaân treân Z vaø (Z, +, ·) laø moät vaønh giao hoaùn. 2. Chöùng minh raèng Z laø mieàn nguyeân, ñeám ñöôïc, cöïc tieåu chöùa N nhö laø nöûa nhoùm con coäng vaø nöûa nhoùm con nhaân. 3. Chöùng minh raèng Z, ≤ laø moät vaønh ñöôïc saép thöù töï Archimed. 4. Chöùng minh ñònh lyù1.5 5. Xaùc ñònh thöông vaø phaàn dö trong pheùp chia cho 7 vaø cho −7 cuûa caùc soá: a) 9 b) 99 c) 999 d) 9999 e) 99999 6. Xaùc ñònh thöông vaø phaàn dö trong pheùp chia cho 17 vaø cho −17 cuûa caùc soá: a) − 8 b) − 88 c) − 888 d) − 8888 e) − 88888 7. Chöùng minh raèng neáu a, b, c, d laø caùc soá nguyeân vôùi a vaø c khaùc 0 sao cho a | b vaø c | d thì ac | bd. 8. Giaû söû a, b, c laø caùc soá nguyeân vaø c = 0. Chöùng minh raèng a | b khi vaø chæ khi ac | bc. 9. Chöùng minh raèng neáu a, b laø caùc soá nguyeân vaø a | b thì an | bn vôùi moïi soá soá töï nhieân n. 10. Haõy ñoåi caùc soá thaäp phaân 1955, −1973 sang heä sang heä thaäp luïc phaân, heä töù phaân, heä nhò phaân, heä baùt phaân. 11. Haõy ñoåi soá thaäp luïc phaân ABCDEF sang heää heä nhò phaân, heä töù phaân vaø heä baùt phaân. 12. Haõy phaùt bieåu vieäc chuyeån ñoåi soá töø heä ñeám cô soá r sang heä ñeám cô soá rn vaø ngöôïc laïi ? khi r, n > 1 laø caùc soá nguyeân döông. 13. Chöùng minh raèng neáu b < −1 laø moät soá nguyeân thì moïi soá nguyeân n = 0 ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng n = ak bk + ak−1 bk−1 + · · · + a1 b + a0 trong ñoù k laø soá nguyeân khoâng aâm, caùc aj laø soá nguyeân vôùi 0 ≤ aj ≤ |b| − 1vaø heä soá ñaàu tieân ak = 0. Haõy bieåu dieãn caùc soá thaäp phaân −7, −17, 61 trong heä cô soá −2.
1.4. BIEÅU DIEÃN SOÁ NGUYEÂN 11 14. Chöùng minh raèng moïi soá nguyeân n = 0 ñeàu vieát ñöôïc moät caùch duy nhaát döôùi daïng n = ak 3k + ak−1 3k−1 + · · · + a1 3 + 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 a n − 1 laø soá nguyeân toá 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 p cuûa soá nguyeân döông n vöôït quaù n thì n/p laø soá nguyeân toá hoaëc baèng 1. 3
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öôøngM 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+1 qj+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 = r1 q 1 + r2 0 < r2 < r1 r1 = r2 q 2 + r3 0 < r3 < r2 .. . rj−2 = rj−1 qj−1 + rj 0 < rj < rj−1 .. . rn−2 = rn−1 qn−1 + rn 0 < rn < rn−1 rn−1 = rn qn + 0 . Töø nhaän xeùt treân, ta coù: (a, b) = (r0 , r1 ) = (r1 , r2 ) = · · · = (rn−2 , rn−1 ) = (rn−1 , rn ) = (rn , rn+1 ) = (rn , 0) = rn . Ví duï 2.2.1. Duøng thuaät toaùn Euclid ñeå tìm (610, −1955). Vì (610, −1955) = (610, 1955) neân ta tìm (610, 1955). Ta coù: 1955 = 610 · 3 + 125 610 = 125 · 4 + 110 125 = 110 · 1 + 15 110 = 15 · 7 + 5 15 = 5 · 3 + 0. Vaäy (610, 1955) = 5, suy ra (610, −1955) = 5. Ví duï 2.2.2. Duøng thuaät toaùn Euclid ñeå tìm (1955, 2003). Ta coù: 2003 = 1955 · 1 + 48 1955 = 48 · 40 + 35 48 = 35 · 1 + 13 35 = 13 · 2 + 9 13 = 9 · 1 + 4 9=4·2+1 4 = 1 · 4 + 0. Vaäy (1955, 2003) = 1, hay 1955 vaø 2003 laø caùc soá nguyeân toá cuøng nhau.
2.3. ÑÒNH LYÙ CÔ BAÛN CUÛA SOÁ HOÏC 17 2.3 Ñònh lyù cô baûn cuûa soá hoïc Ñònh lyù 2.6. Ñònh lyù cô baûn cuûa soá hoïc. Moïi soá nguyeân lôùn hôn 1 ñeàu vieát ñöôïc moät caùch duy nhaát thaønh tích cuûa caùc thöøa soá nguyeân toá theo thöù töï khoâng giaûm. Tröôùc khi chöùng minh ñònh lyù cô baûn, chuùng ta chöâng minh hai boå ñeà sau ñaây. Boå ñeàù 2.6.1. Neáu a, b, c laø caùc soá nguyeân döông sao cho (a, b) = 1 vaø a | bc thì a | c. Chöùng minh. Vì (a, b) = 1 neân theo ñònh lyù 2.3, coù caùc soá nguyeân x, y sao cho ax + by = 1. Nhaân hai veá cuûa ñaúng thöùc naøy vôùi c ta ñöôïc acx + bcy = c. Theo giaû thieát a | bc ta suy ra a | acx + bcy = c. Boå ñeàù 2.6.2. Neáu p laø öôùc nguyeân toá cuûa tích a1 a2 · · · 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 a1 a2 · · · ak ak+1 . Neáu p 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öôøng hôïp n = 2 laø taàm thöôøng. Soá nguyeân n+1 > 2 neáu laø soá nguyeân toá thì khoâng coù gì phaûi chöùng minh. Ngöôïc laïi, ta coù n + 1 = ab, vôùi 1 < a, b < n + 1; theo giaû thieát qui naïp thì a, b ñeàu laø tích cuûa caùc soá nguyeân toá. Baây giôø ta chöùng minh tính duy nhaát cuûa bieåu dieãn. Giaû söû laø n = p1 p2 · · · pr = q 1 q 2 · · · q s vôùi p1 ≤ p2 ≤ · · · ≤ pr , q1 ≤ q2 ≤ · · · ≤ qs laø caùc soá nguyeân toá. Töø boå ñeà 2.6.2 ta deã daøng suy ra raèng r = s vaø p 1 = q1 , · · · , pr = qs. Chuù yù: 1. Moïi soá nguyeân n > 1 ñeàu coù bieåu dieãn duy nhaát n = pα1 1 ... pαk k , vôùi 1 ≤ k, 0 < α1 , · · · , αk .
18 2. ÖÔÙC CHUNG LÔÙN NHAÁT.SÖÏ PHAÂN TÍCH RA THÖØA SOÁ NGUYEÂN TOÁ. 2. Neáu daõy taát caû soá nguyeân toá ñöôïc saép theo thöù töï taêng daàn: p1 = 2 < p2 = 3 < p3 = 5 < p4 = 7 < p5 = 11 < · · · thì moïi soá nguyeân döông ñeàu vieát ñöôïc moät caùch duy nhaát duôùi daïng +∞ n= pαk k , 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á +∞ +∞ a= pαk k vaø b = pβkk k=0 k=0 thì +∞ +∞ (a, b) = min{αk ,βk } pk , [a, b] = max{αk ,βk } pk vaø (a, b) · [a, b] = ab. k=0 k=0 Chöùng minh. Deã daøng thaáy raèng +∞ +∞ c= pγkk laø öôùc cuûa d= pθkk 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 } +∞ (a, b) · [a, b] = pk = pαk k +βk = 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 a1 x1 + a2 x2 + · · · + an xn = 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.