2. Feladatsor
´ sa ´g, legnagyobb ko ¨ zo ¨ s oszto ´, Oszthato ´cio ´ az eg´ ´mok ko ¨ r´ pr´ımfaktoriza esz sza eben1
¨ telezo ˝ ha ´zi feladat(ok) Ko 2.∗,∗∗ Hat´arozzuk meg a ϕ : Z → Z, z 7→ 5z lek´epez´es magj´at. Adjuk meg a ker(ϕ)-hez tartoz´o oszt´alyoz´as egy reprezent´ansrendszer´et. 3.∗,∗∗ Rajzoljuk le az ¨osszes 2-, 3-, illetve 4-pont´ u Hasse-diagramot. 4.∗,∗∗ Legyen k tetsz˝oleges term´eszetes sz´am. Defini´aljuk az Nk = {(a1 , . . . , ak ) : a1 , . . . , ak ∈ N} halmazon a v rel´aci´ot az al´abbi m´o don. Legyen (a1 , . . . , ak ), (b1 , . . . , bk ) ∈ Nk , ekkor (a1 , . . . , ak ) v (b1 , . . . , bk ) pontosan akkor teljes¨ ul, ha vagy ai = bi (i = 1, . . . , k), vagy van olyan i0 ∈ {1, . . . , k}, amelyre teljes¨ ul, hogy k a1 = b1 , . . . , ai0 = bi0 ´es ai0 +1 < bi0 +1 . Mutassuk meg, hogy (N ; v) r´eszbenrendezett halmaz. ´zi feladat(ok) Ha 5.∗,∗∗ Mutassuk meg, hogy ha m > 2 eg´esz sz´am, akkor 2n + 1 sohasem oszthat´o (2m − 1)-gyel. √ 6.∗,∗∗ Mutassuk meg, hogy a [2k 2] : k ∈ N halmazban v´egtelen sok ¨osszetett sz´am van. 7.∗,∗∗ Adott 2k + 1 darab (k term´eszetes sz´am) pozit´ıv eg´esz sz´am, melyek szorzat´anak k k¨ ul¨onb¨oz˝o pr´ımoszt´o ja van. Mutassuk meg, hogy a sz´amok k¨oz¨ott van n´eh´any olyan, amelyek szorzata k¨obsz´am.
1
2007/2008. tavaszi f´el´ev, Algebra ´ es sz´ amelm´ elet gyakorlat (MBN211G-2,3). A *-gal jel¨ olt feladatok a m´asodik, a **-gal jel¨olt feladatok a harmadik csoportnak sz´olnak.
1
´ sa ´g Oszthato 10. Igazoljuk az al´abbi oszthat´os´agokat: (a) 9 | 1018 + 8;
(b) 72 | 1016 + 8;
(c) 31 | 517 + 6;
(d) 18 | 1719 + 1917 .
Megold´ as/´ Utmutat´ as. (a) a sz´amjegyek ¨osszege 9;2 (b) Gondoljuk meg, hogy 72 | 1016 + 8 pontosan akkor teljes¨ ul, ha 8 | 1016 + 8 16 3 ´es 9 | 10 + 8; (c) 517 + 6 = 517 − 52 + 31 = 52 (515 − 1) + 31. Gondoljuk meg, hogy 31 | 53 − 1 | 515 − 1.4 (d) Mutassuk meg, hogy 2, 9 | 1719 + 1917 .5 11. Hat´arozzuk meg a fel´ırt sz´am hi´anyz´o sz´amjegyeit (10-es sz´amrendszerben) u ´ gy, hogy teljes¨ ulj¨on az al´abbi oszthat´os´ag. Valamennyi megold´ast keress¨ uk meg. (a) 36 | 52x2y;
(b) 45 | 24x68y;
(c) 99 | 62xy427
(d) 1155 | xxyzzuv ´es 2 - x, y, z, u, v.
Megold´ as/´ Utmutat´ as. (a) (x, y) ∈ {(0, 0), (1, 8), (5, 4), (9, 0)}; (b) (x, y) ∈ {(2, 5), (7, 0)}; (c) (x, y) ∈ {(2, 4)}; (d) (x, y, z, u, v) ∈ {(1, 9, 7, 3, 5), (9, 7, 1, 1, 5)}. 12. Mutassuk meg, hogy a k¨ovetkez˝o sz´amok ¨osszetettek. (a) 106 − 57 ;
(b) 1010 − 7
(c) 420 − 1;
(d) 1 000 027;
(e) 347 777 743;
(f) 49 + 610 + 320 ;
(g) 5123 + 6753 + 7203 ;
(h) 19 · 8n + 17 (n ∈ N).
2
A 1018 + 8 eg´esz sz´ am pr´ımhatv´ anyt´enyez˝os felbont´ asa 23 · 32 · 97 · 32779 · 166667. 16 A 10 + 8 eg´esz sz´ am pr´ımhatv´ anyt´enyez˝os felbont´ asa 23 · 32 · 138888888888889. 4 13 A 5 + 6 eg´esz sz´ am pr´ımhatv´ anyt´enyez˝os felbont´ asa 31 · 24610950101. 5 A 1719 + 1917 eg´esz sz´ am pr´ımhatv´ anyt´enyez˝os felbont´ asa 22 · 35 · 43 · 223637 · 3092071 · 8461451. 3
2
Megold´ as/´ Utmutat´ as. (a) 5 | 106 − 57 = 56 · 59; (b) 3 | 1010 − 7 = 3 · 673 · 4952947; (c) 3 | 420 − 1 = 3 · 52 · 11 · 17 · 31 · 41 · 61681; (d) 7 | 1 000 027 = 7 · 19 · 73 · 103; (e) 347 777 743 = 3333333 + 11111110 + 333333300 = 313 · 1111111 = 239 · 313 · 4649; (f) 49 + 610 + 320 = (29 + 310 )2 = 595612; (g) 5123 + 6753 + 7203 = 229 · 467 · 7621; (h) ha n p´aros, akkor 3 | 19 · 8n + 17, ha 4 | n + 1, akkor 5 | 19 · 8n + 17, ha 4 | n − 1, akkor 13 | 19 · 8n + 17. 13. Melyik az az ¨otjegy˝ u sz´am, amely egyenl˝o sz´amjegyei szorzat´anak 45sz¨or¨os´evel? Megold´ as/´ Utmutat´ as. A keresett eg´esz sz´am a 77175. 14. Hat´arozzuk meg azokat az n term´eszetes sz´amokat, amelyekre n + 4 oszt´o ja n2 + 8n + 15-nek. Megold´ as/´ Utmutat´ as. Mivel n2 + 8n + 15 = (n + 4)2 − 1, ez´ert n + 4 n2 + 8n + 15, ha n ∈ N. 15. Tegy¨ uk fel, hogy az a, b, c eg´esz sz´amokra teljes¨ ul az a + b + c = (a − b)(b − c)(c − a) egyenl˝os´eg. Mutassuk meg, hogy 27 | a + b + c. Megold´ as/´ Utmutat´ as. Mutassuk meg, hogy ha a+b+c = (a−b)(b−c)(c−a), akkor a, b ´es c ugyanazt a marad´ekot adj´ak 3-mal osztva. ¨ zo ¨ s oszto ´ Legnagyobb ko 16. Hat´arozzuk meg mindazokat az a, b term´eszetes sz´amokat, amelyekre ln.k.o.(a, b) = 22 ´es lk.k.t.(a, b) = 264. Megold´ as/´ Utmutat´ as. (a, b) ∈ {(22, 264), (66, 88), (88, 66), (264, 22)}. 17. Mely c, d term´eszetes sz´amokra oldhat´o meg az ln.k.o.(a, b) = c, lk.k.t.(a, b) = d. egyenletrendszer a term´eszetes sz´amok halmaz´an? H´any megold´as van? Megold´ as/´ Utmutat´ as. Az egyenletrendszer pontosan akkor oldhat´o meg, ha βs+1 c | d. Legyen c = pα1 1 · · · pαs s ´es d = pβ1 1 · · · pβs s ps+1 · · · pβt t , ahol p1 , . . . , pt 3
p´aronk´ent k¨ ul¨onb¨oz˝o pr´ımsz´amok, 1 6 αi 6 βi minden i-re (1 6 i 6 s) ´es 1 6 βj minden j-re (s+1 6 j 6 t). Ekkor a megold´asok a k¨ovetkez˝o alak´ uak: a = pγ11 · · · pγt t ,
b = pδ11 · · · pδt t ,
ahol {γi , δi } = {αi , δi }. 18. Hat´arozzuk meg az F2007 ´es F2008 Fibonacci-sz´amok6 legnagyobb k¨oz¨os oszt´o j´at. Megold´ as/´ Utmutat´ as. ln.k.o.(F2007 , F2008 ) = 1. Az is igaz, hogy ln.k.o.(Fn , Fn+1 ) = 1 teljes¨ ul tetsz˝oleges n ∈ N-re. 19. Legyenek a ´es b tetsz˝oleges eg´esz sz´amok. Mutassuk meg, hogy 7 | 10a+b pontosan akkor teljes¨ ul, ha 7 | a − 2b. Ennek seg´ıts´eg´evel d¨ontse el, hogy a 28210392 term´eszetes sz´am oszthat´o-e 7-tel. Megold´ as/´ Utmutat´ as. Az ´all´ıt´as abb´ol k¨ovetkezik, hogy (10a + b) + 4(a − 2b) = 7(2a − b) oszthat´o 7-tel ´es ln.k.o.(4, 7) = 1. 20. Legyenek a, b ´es k, l tetsz˝oleges term´eszetes sz´amok. Mutassuk meg, hogy ha ak ´es bl relat´ıv pr´ımek egym´ashoz, akkor a ´es b is relat´ıv pr´ımek egym´ashoz. 21. Hat´arozzuk meg a 234 ´es 432 eg´eszek legnagyobb k¨oz¨os oszt´o j´at ´es oldjuk meg az al´abbi diofantoszi egyenleteket: (a) 234x + 432y = 6564; (b) 234x − 432y = 6570. Megold´ as/´ Utmutat´ as. (a) Nincs megold´as, mivel ln.k.o.(234, 432) = 18 6564. (b) Az egyenlet megoldhat´o: x = 41 + 24t, y = 7 + 13t (t ∈ Z). 22. Mely n term´eszetes sz´amokra lehet egyszer˝ us´ıteni a 6
7n+5 9n−2
t¨ortet?
A Fibonacci-sz´ amokat az al´ abbi rekurzi´ oval defini´ aljuk: F1 = F2 = 1, Fn = Fn+1 + Fn+2 (n > 3).
4
Megold´ as/´ Utmutat´ as. Legyen d = ln.k.o.(7n + 5, 9n − 2). Ekkor d | 9(7n + 5) − 7(9n − 2) = 59. A t¨ortet pontosan akkor lehet egyszer˝ us´ıteni, ha d > 1. Azaz d = 59. Ez pontosan akkor k¨ovetkezik be, ha n = 33+59t (t ∈ N∪{0}). 23. Egy tizenh´ettag´ u kal´ozcsapat egy zs´ak aranyp´enzt zs´akm´anyolt. Amikor megpr´ob´alt´ak egyenl˝o en elosztani, azt tapasztalt´ak, hogy h´arom aranyp´enz kimaradt. A kimaradt aranyak feletti vit´aban egy kal´ozt v´eletlen¨ ul meg¨oltek. Ezut´an u ´ jraosztott´ak egyenl˝o ar´anyban a zs´akm´anyt, ´es most t´ız arany maradt ki. Az e feletti vit´aban egy u ´ jabb kal´oz t´avozott az ´el˝ok sor´ab´ol. Ezut´an m´ar el tudt´ak osztani az aranyat u ´ gy, hogy mindenki ugyanannyit kapott. Legkevesebb h´any aranyp´enz volt a zs´akban? 24. Mutassuk meg, hogy tetsz˝oleges a, b, c eg´esz sz´amokra, ha ln.k.o.(b, c) = 1, akkor ln.k.o.(a, bc) =ln.k.o.(a,b)ln.k.o.(a, c). a1 + a2 25. Mutassuk meg, hogy az t¨ort nem egyszer˝ us´ıthet˝o, ha |a1 b2 − b1 + b2 a2 b1 | = 1.
Megold´ as/´ Utmutat´ as. Legyen d = ln.k.o.(a1 + a2 , b1 + b2 ). Ekkor d | b2 (a1 + a2 ) − a2 (b1 + b2 ) = a1 b2 − a2 b1 = ±1.
26. Hat´arozzuk meg a 2072x + 1813y = 2849 diofantoszi egyenlet ´altal´anos megold´as´at. Megold´ as/´ Utmutat´ as. A megold´as: x = 4 + 7t, y = −3 − 8t (t ∈ Z). 27. Hat´arozzuk meg a 19x + 20y = 1909 diofantoszi egyenlet azon megold´asait, amelyekre x, y > 0 teljes¨ ul. Megold´ as/´ Utmutat´ as. (x, y) ∈ {(91, 9), (71, 28), (51, 47), (31, 66), (11, 85)}. ´cio ´ Z-ben Pr´ımfaktoriza 28. Mi´ert nem lehet 1991 k´et pr´ımsz´am ¨osszege? 29. Legyen p > 3 pr´ımsz´am. Mutassuk meg, hogy 24 | p2 − 1.
Megold´ as/´ Utmutat´ as. Gondoljuk meg, hogy minden pr´ımsz´am p = 12k ± l alakban ´ırhat´o, ahol l ∈ {1, 5, 7, 11}. ´Igy p2 − 1 = 144k 2 − 24k + l2 − 1. 30. Mutassuk meg, hogy ha p ´es p2 + 8 pr´ımsz´amok, akkor p2 + p + 1 is az. Megold´ as/´ Utmutat´ as. Mutassuk meg, hogy csak p = 3 lehets´eges.
5
31. Igazoljuk, hogy tetsz˝oleges m ´es n term´eszetes sz´amokra (2m)!(2n)! m!n!(m + n)! eg´esz sz´am. Megold´ as/´ Utmutat´ as. Legyen n tetsz˝oleges term´eszetes sz´am ´es p tetsz˝oleges pr´ımsz´am. Legyen kp az a nemnegat´ıv eg´esz, amelyre pkp 6 n < pkp +1 . Tov´abb´a legyen νp = [n/p] + [n/p2 ] + · · · + [n/pkp ]. Mutassuk meg, hogy pνp | n! ´es pνp +1 - n!. Ezt felaszn´alva igazoljuk az ´all´ıt´ast. 32. Jel¨olje E a p´aros eg´eszek halmaz´at. Azt mondjuk, hogy a ∈ E osztja b ∈ E-t, ha van olyan c ∈ E, amelyre b = ca teljes¨ ul. A q ∈ E elemet felbonthatatlannak nevezz¨ uk, ha nincsenek olyan a, b ∈ E elemek, amelyekre q = ab teljes¨ ul. (a) Mik a felbonthatatlan elemek E-ben? (b) Igaz-e, hogy egy 0-t´ol k¨ ul¨onb¨oz˝o E-beli elem vagy felbonthatatlan, vagy felbonthatatlan elemek szorzat´ara bonthat´o? Megold´ as/´ Utmutat´ as. (a) Azok az E-beli elemek felbonthatatlanok, amelyek nem oszthat´ok 4-gyel. (b) Igaz. Ha n = 2r m, ahol r ∈ N ´es m p´aratlan eg´esz, akkor n = |2 ·{z · · 2} ·(2m). (r−1) darab
6
