SZÁMELMÉLET Vasile Berinde, Filippo Spagnolo A számelmélet a matematika egyik legrégibb ága, és az egyik legnagyobb is egyben. Ennek a fejezetnek az a célja, hogy egy elemi bevezetést nyújtson az első szinten lévő diákok számára néhány gyakorlaton és feladaton keresztül. Ezekben az egész számokkal foglalkozunk: egész számok közötti oszthatóság, az Euklideszi-algoritmus és a legnagyobb közös osztó létezése, a prímszámok elemi tulajdonságai, a Diophantoszi-egyenletek néhány speciális esete és még különféle egyebek. 1. Egész számok oszthatósága Legyen a pozitív egész számok (vagy természetes számok) halmazának jelölése . Azt mondjuk, hogy a ∈ osztható a b ∈ számmal vagy, ekvivalens módon, hogy b osztja a -t, ha létezik, olyan c ∈ , hogy a = b⋅c . Ezt b | a vagy a M b képletekkel jelöljük, és azt mondjuk, hogy b az a szám osztója, vagy tényezője. Hasonlóan mondhatjuk azt is, hogy az a szám a b többszöröse és ebben az esetben a következő jelölést használjuk: a = M b . Ez a definíció a nem 0 egész számokra is alkalmazható, de a következőkben mi a pozitív egész számokra szorítkozunk. Most a következő elemi oszthatósági feltételekre emlékeztetünk: 1) Egy a ∈ szám osztható 2-vel, ha az utolsó számjegye páros (azaz osztható 2-vel); 2) Egy a ∈ szám osztható 5-tel, ha az utolsó számjegye osztható 5-tel (azaz 0 vagy 5); 3) Egy a ∈ szám osztható 3-mal, ha a számjegyeinek az összege osztható 3-mal; 4) Egy a ∈ szám osztható 9-cel, ha a számjegyeinek összege 9; 5) Egy a ∈ osztható 10n -nel, ha n darab 0-ra végződik. Ennek a fejezetnek az utolsó részének kivételével, minden természetes szám a tízes számrendszerbeli alakjában lesz feltüntetve. 1.1. Mutassuk meg, hogy két páratlan vagy két páros szám összege (különbsége) mindig egy páros szám. Megoldás. Legyen m és n a két páratlan természetes szám, ekkor, m = 2p + 1 , p ∈ és n = 2r + 1 , r ∈ . Ekkor a + b = 2( p + r + 1) és a − b = 2( p − r ) , amik egyaránt páros számok. Az az eset, amikor m és n egyaránt páros, hasonló. Gyakorlatok (1) 1.2. Mutassuk meg, hogy minden n egész szám esetén n(n + 1) osztható 2-vel! 1.3. Mutassuk meg, hogy minden n egész szám esetén n(n + 1)(n + 2) osztható 3-mal! 1.4. Keressük meg x értékét úgy, hogy 2 x 5 osztható 3-mal (illetve 9 esetén is keressük meg). 1.5. Mutassuk meg, hogy két egymást követő köbszám különbsége soha nem osztható 2-vel! Megoldás. Azt kapjuk, hogy (n + 1)3 − n 3 = 3n(n + 1) + 1 és mivel n(n + 1) páros, az 1.2-es gyakorlat szerint azt kapjuk, hogy két egymást követő köbszám különbsége mindig páratlan. 1.6. Keressük meg 72003 utolsó számjegyét! Megoldás. Jelöljük ld (u ) -val az u szám utolsó jegyét! (ld a last digit angol kifejezés
rövidítéseként, jelentése: utolsó számjegy)
Ekkor ld (71 ) = 7 ; ld (72 ) = 9 ; ld (73 ) = 3 ;
ld (74 ) = 1 …. Mivel 2003 = 4 ⋅ 500 + 3 , azt kapjuk, hogy ld (72003 ) = 3 . 1.7. Mutassuk meg, hogy N = 19961998 + 19971999 + 19982000 osztható 5-tel!
Megoldás. 19961998 utolsó jegye mindig 6; 19971999 utolsó jegye megegyezik 71999 utolsó jegyével, ami 3 (mivel 1999 = 4 ⋅ 494 + 3 ); 1998 2000 utolsó jegye megegyezik 82000 utolsó jegyével, ami 6 (mivel 2000 osztható 4-gyel). Így, N utolsó számjegye a következő összeg utolsó számjegye lesz, 6 + 3 + 6 = 15 , ami 5, ezért N osztható 5-tel. 1.8. Mutassuk meg, hogy N = 19831986 + 19841986 + 19851986 osztható 10-zel! 1.9. Mutassuk meg, hogy a = 52 n + 3 ⋅ 9n + 2 + 32 n +1 ⋅ 25n +1 osztható 17-tel bármely n ∈ esetén. 1.10. Mutassuk meg, hogy a = 63n + 7n +1 ⋅ 32n +1 − 21n ⋅ 3n + 2 osztható 13-mal bármely n ∈ esetén. 1.11. Bizonyítsuk be a 3–mal (vagy 9-cel) való oszthatóság feltételét! 2. Legnagyobb közös osztó és legkisebb közös többszörös Egy p > 1 természetes számot prímszámnak hívunk, ha csak 2 osztója van: 1 és önmaga. Ellenkező esetben összetett számnak hívjuk. Minden természetes szám egyedi módon kifejezhető a prím osztóinak szorzataként. Két a és b természetes szám esetén a d természetes számot hívjuk a legnagyobb közös osztónak, ha 1) d | a és d | b ; 2) ha c | a és c | b akkor c | d . a és b legnagyobb közös osztóját minden esetben egyértelműen meghatározhatjuk és lnko( a, b) vagy egyszerűen (a, b ) jelöléssel jelöljük, (hasonló módon bevezethető a legkisebb közös többszörös (továbbiakban lkkt(a,b)) fogalma, legyen ez az olvasó dolga): 1. Példa lnko(24,90) = 6 például, mivel
24 = 23 ⋅ 31 és 90 = 2 ⋅ 32 ⋅ 5 . Két a és b természetes számot, amikre lnko( a, b) = 1 , relatív prímszámoknak nevezzük. Megjegyzés. Ha lnko( a, b) = 1 akkor ab | n akkor és csakis igaz, ha a | n és b | n . 2. Példa Legyen n = 360 , a = 24 és b = 90 . Ekkor a | n és b | n (lásd az előző példát), de n nem osztható a ⋅ b -vel, mivel lnko( a, b) = 6 ≠ 1 . Gyakorlatok (2) 2.1. Adott a 21x természetes szám, keressük meg az x számjegy értékét úgy, hogy a megadott számnak osztója legyen az: a) 5; b) 6; c) 12. 2.2. Keressük meg az olyan összes 2 x 3 y alakú számot, ami osztható 15-tel! 2.3. Keressük meg a legnagyobb és legkisebb olyan 619 x 7 y alakú számot, amik oszthatóak 18-cal! 2.4. Keressük meg x és y értékét úgy, hogy 45 osztója legyen az 4xy számnak! 2.5. Mutassuk meg, hogy a = 3 + 32 + ... + 31986 osztható 156-tal! 2.6. Mutassuk meg, hogy az a = 15n +1 + 3n +1 + 5 ⋅ 3n + 2 alakú számok oszthatóak 27-tel minden n > 1 esetén! 2.7. Mutassuk meg, hogy bármely n ∈ 18-cal!
szám esetén az a = 2n ⋅ 5n + 1988 szám osztható
2.8. Mutassuk meg, hogy 30 osztója az n 5 - n kifejezésnek bármely n pozitív szám esetén.
2.9. Mutassuk meg, hogy az a = 22 n +1 ⋅ 32 n ⋅ 5n +1 + 4n ⋅ 32 n ⋅ 5n szám osztható 1980-cal bármely n ∈ esetén! 2.10. Legyen a, b ∈ igaz?
. Mutassuk meg, hogy ha 3a + 5b M17 akkor, 4a + b M17 . Fordítva is
2.11. Mutassuk meg, 11 x + 3 y M 31 ( x, y ∈ ) .
hogy
5 x + 7 y M 31
akkor
és
csakis
akkor
igaz,
ha
2.12. Mutassuk meg, hogy 5a + 8b M17 akkor és csakis akkor igaz, ha 4a + 3b M17 (a, b ∈ ) . 2.13. Mutassuk meg, hogy 3a + 4b M13 akkor és csakis akkor igaz, ha 2a + 7b M13 (a, b ∈ ) . 2.14. Mutassuk meg, hogy a következő számpárok bármely n ∈
esetén relatív prímek:
a) 6n + 5 és 7n + 6; b) 10n + 3 és 15n + 4; c) 4 ⋅ 7 + 3 és 5 ⋅ 7 + 4 n
n
Egy a összetett szám osztóinak a száma, aminek a prím osztói p1, p2 ,..., pn az α1,α 2 ,...,α n kitevőkkel rendre, azaz a = p1α1 ⋅ p2α2 ⋅ K ⋅ pnαn a következőképpen adható meg: τ (a ) = (α1 + 1)(α 2 + 1)...(α n + 1)
(1) .
(2)
Példa. Az a = 30870 szám az a = 2 ⋅ 3 ⋅ 5 ⋅ 7 szorzat formájában írható fel, így az osztóinak a száma: (1 + 1) ⋅ (2 + 1) ⋅ (1 + 1) ⋅ (3 + 1) = 48 . 1
2
1
3
2.15. Keressük meg az összes olyan kétjegyű számot, aminek pontosan 3 osztója van! Megoldás. A (2)-es képletet használva arra jutunk, hogy n = 1 és α1 = 2 , azaz a p 2 formájú számok, ahol p egy prímszám. A p = 5 és p = 7 esetén kapunk kétjegyű számokat. Így, a keresett számok a 25 és 49. Gyakorlatok (3) 2.16. Keressük meg az összes olyan természetes számot, aminek pontosan 4 osztója van, és az osztóinak a szorzata 225! 2.17. Keressük meg az összes olyan négyjegyű számot, aminek pontosan 5 osztója van! 2.18. Keressük meg azt a természetes számot, aminek pontosan 6 osztója van, továbbá az osztóinak a szorzata a) 91125; b) 32768. 2.19. Keressük meg az ab, 72 < ab ≤ 85 számokat úgy, hogy pontosan 4 osztójuk legyen! 2.20. Keressük meg az összes olyan 10-zel osztható számot, aminek pontosan 6 osztója van! 2.21. Keressük meg a legkisebb olyan természetes számot, aminek pontosan 42 osztója van!
2.22. Mutassuk meg, hogy nem létezik olyan 35-tel osztható háromjegyű természetes szám, aminek pontosan 9 osztója van. 2.23. Keressük meg a legkisebb és legnagyobb olyan 3a ⋅ 5b alakú számot, aminek pontosan 12 osztója van. 2.24. Keressük meg az x, y , z prímszámokat úgy, hogy az n = 11x ⋅ 19 y ⋅ 31z számnak pontosan 144 osztója legyen. 2.25. Keressük meg az olyan n = 3a ⋅ 5b ⋅ 7c alakú számokat, amelyekre a 27 ⋅ n számnak 36-tal több osztója van, és a 49 ⋅ n számnak 12-vel több osztója van, mint az n számnak.
Két vagy több természetes szám legnagyobb közös osztóját vagy legkisebb közös többszörösét azonban a számok szorzótényezőkre bontása nélkül is meg lehet határozni, az úgy nevezett Euklideszi-algoritmussal. Legyen a, b ∈ a két szám úgy, hogy, b ≠ 0 és b /| a . Először elosztjuk az a számot a b számmal és így megkapjuk a q1 hányadost és az r1 maradékot, azaz a = b ⋅ q1 + r1, 0 ≤ r1 < b. Ezután lecseréljük az a számot b-re, b-t pedig r1-re, és megismételjük az előbbi műveletet: b = r1 ⋅ q2 + r2 , 0 ≤ r2 < r1 r1 = r2 ⋅ q3 + r3 M Amikor elérjük az rn +1 = 0 -t, akkor az előző maradék, azaz rn a keresett legnagyobb közös osztó, azaz lnko(a, b) = rn . Példa. Keressük meg lnko(93,51) értékét! Megoldás. Azt kapjuk, hogy 93 = 51 ⋅ 1 + 42
51 = 42 ⋅ 1 + 9 42 = 9 ⋅ 4 + 6 9 = 6 ⋅1+ 3 6 = 3⋅2+0 és ezért lnko(93, 51) = 3 . Megjegyzés. Egyszerű meglátni, hogy 93 = 3 ⋅ 31 és 51 = 3 ⋅ 17 , ami ugyanazt az eredményt adja. 2.26. Keressük meg az a, b ∈ számokat úgy, hogy a + b = 1089 és lnko( a, b) = 121 . Megoldás. Azt kapjuk, hogy a = 121 ⋅ m , b = 121⋅ n és lnko( a, b) = 1 . Mivel a + b = 1089( = 121 ⋅ 9) , azt kapjuk, hogy m + n = 9 , ami alapján a következő relatív prím számpárokat kapjuk: ( m, n ) ∈ {(1,8), (2,7), (4,5), (5, 4), (7,2), (8,1)} . A keresett számok: (121,986),(242,847),(484,605),(847,242),(968,121) . 2.27. Keressünk két különböző a, b > 1 számot úgy, hogy lkkt( a, b) = 667 . Megoldás. Mivel 667 = 23 ⋅ 29 , ezért a két szám a következő lehet:
a) 23 és 29; b) 23 és 667; c) 29 és 667. Gyakorlatok (4)
2.28. Keressük meg azokat az a, b ∈ a ⋅ b = 1600 és lkkt( a, b) = 4 ⋅ lnko( a, b)
számokat, amik kielégítik a következő feltételeket:
2.29. Keressük meg az a, b ∈
számokat úgy, hogy a + b = 108 és lkkt( a, b ) = 315 .
2.30. Keressük meg az a, b ∈
számokat úgy, hogy 3 ⋅ a = 7 és lkkt( a, b ) = 231 .
2.31. Keressük meg az a, b ∈
számokat úgy, hogy lnko( a, b ) = 4 és a3 ⋅ b3 = 884736 .
2.32. Keressük meg az a, b , a < b számokat úgy, hogy lkkt( a, b) − lnko( a , b) = 34 .
Ezt a részt két gyakorlatiasabb feladattal zárjuk, amik a legkisebb közös többszörös és/vagy legnagyobb közös osztó segítségével oldhatóak meg. 2.33. Ha egy iskola diákjait 2-es, 3-as, 4-es, 5-ös, 6-os sorokba rendezzük, akkor minden alkalommal egy diák marad ki a sorokból, de ha 7-es sorokba rendezzük el a diákokat, akkor minden sor teljes és egy diák sem marad ki. Keressük meg az iskolában tanuló diákok számának legkisebb lehetséges számát! Megoldás. Mivel lkkt(2, 3, 4, 5, 6) = 60 , ezért a k szám minimális értékét úgy kell megkeresnünk, hogy (60 ⋅ k + 1)M 7 . A keresett érték a k = 5 és így az iskolának 301 diákja van. 2.34. Egy busz állomásról 4 busz indul 4 különböző irányban rendre 5, 8, 12 és 18 percenként, 6 és 21 óra között. Tudva, hogy először 7:00-kor indul egyszerre mind a négy busz, keressük meg azokat az időpontokat még a nap folyamán, amikor mindegyik busz egyszerre indul. Megoldás. Mivel lkkt(5,8,12,18) = 360 és 360 perc = 6 óra, ezért azt kapjuk, hogy a buszok a következő időpontokban indulnak mind egyszerre: 7:00; 13:00 és 19:00. Gyakorlatok (5) 2.35. Ha elosztjuk az a számot 24-gyel, 36-tal, 30-cal és 75-tel, akkor a maradék minden esetben 5 lesz. Keressük meg azt az a < 10000 számot, ami osztható 11-gyel! 2.36. Ha egy n számot 9-cel, 12-vel és 15-cel osztunk, akkor az osztási maradék rendre 6, 9 és 12 lesz. Keressük meg a maradék értékét, ha az n számot 180-cal osztjuk! 2.37. Keressük meg a legkisebb és legnagyobb olyan háromjegyű n számot, hogy n 9-cel, 10-zel és 15-tel történő osztás esetén is 7 maradékot ad! 2.38. Keressük meg az összes olyan 7-tel osztható háromjegyű számot, hogy 2-vel, 3-mal, 4-gyel, 5-tel és 6-tal történő osztás esetén ugyanannyi maradékot ad! 1.3. Prímszámok
A prímszámokkal és összetett számokkal kapcsolatos feladatok számottevően változatosak. A következőkben bemutatunk néhány példát. 3.1. Keressük meg az összes olyan p prímszámot, amire p + 1 egy négyzetszám.
Megoldás. Ha p + 1 = n 2 akkor p = n 2 − 1 = (n − 1)(n + 1) , ami összetett szám bármely n > 2 esetén. Az n = 2 esetben azt kapjuk, hogy p = 3 , ami egyetlen létező kért prímszám, ami a keresett tulajdonságokkal rendelkezik. 3.2. Keressünk két a, b prímszámot úgy, hogy a + b = 883 . Megoldás. A 2 kivételével minden prímszám páratlan. Mivel a + b páratlan ezért a = 2 vagy b = 2 ami azt adja, hogy b = 881 vagy a = 881 , ami egy prímszám (ellenőrizzük is!). 3.3. Mutassuk meg, hogy a 2n + 1 és n 2 + n számok relatív prímek minden nemnegatív természetes n szám esetén! Megoldás. A következőt használjuk fel: 1. Lemma Két a és b szám akkor és csakis akkor relatív prím, ha léteznek olyan p, q egész számok, hogy pa + qb = 1 .
Így a következő jelölést használva: a = 2n + 1, b = n 2 + n azt kapjuk, hogy p = 2n + 1, q = −4 úgy, hogy pa + qb = 1 . Ezért 2n + 1 és n 2 + n relatív prímszámok. 3.4. Keressük meg az összes olyan n prímszámot, amire az n + 4 és n + 8 számok is prímszámok. Megoldás. Az n + 4 és n + 8 számok prímszámok, ha n páratlan és n > 1 (az 1 nem prímszám). Legyen n = 2k + 1, k ∈ . A feladatban lévő három szám ekkor
2k + 1, 2k + 5, 2k + 9, k ∈ * . (3) Vegyük észre, hogy k = 1 esetén azt a megoldást kapjuk, hogy 3, 7, 11. Megpróbáljuk leellenőrizni, hogy vajon ez adja-e az egyetlen megoldást. Ezért megpróbáljuk megmutatni, hogy az összes többi értékre, amit a k szám felvehet, a fenti listán (3) lévő számok közül legalább az egyik nem prímszám lesz. Kihasználhatjuk azt a tényt is, hogy a fenti megoldásban a legkisebb szám a 3. A 3-at is figyelembe véve, bármely k ∈ szám felírható a következő alakok egyikébe: 3 p , 3 p + 1, 3 p + 2, ( p ∈ ) mivel 0, 1 vagy 2 maradékot adhat k 3-mal osztva. Ha k = 3 p + 1 , akkor 2k + 1 = 3(2 p + 1) nem prímszám (kivétel a p = 0 esetet, amikor k = 1, ami a már megtalált megoldást adja meg.). Ha k = 3 p + 2 , akkor 2k + 5 = 3(2 p + 3) , ami nem prímszám, ∀ p ∈ . Ha k = 3 p , akkor 2k + 9 = 3(2 p + 3) , ami nem prímszám, ∀ p ∈ . Ezért egyedül k = 1 esetén, azaz n = 3 esetén lesz mindhárom megadott szám egyszerre prímszám. Gyakorlatok (6) 3.5. Mutassuk meg, hogy bármely n > 3 természetes szám felírható prímszámok összegeként. Végezzük el a felírást n = 2004 esetére. 3.6. Keressük meg az összes olyan prímszámot, ami egyaránt felírható két prímszám összegeként és különbségeként is! 3.7. Három egymást követő prímszám összege n 2 + n, n ∈ . Keressük meg ezeket a számokat, ha tudjuk, hogy van köztük két egymást követő szám!
3.8. Keressük meg az a, b, c prímszámokat úgy, hogy azok kielégítsék az a + b - c = 1530 és a - b = 966 feltételeket! 3.9. Keressük meg az a, b, c prímszámokat úgy, hogy azok kielégítsék az a + b = 271 és a + b + c = 1994 feltételeket! 3.10. Keressük meg az összes olyan a, b, c prímszámot, hogy a + 10b + 12 c = 82. 3.11. Keressük meg az összes olyan a, b, c prímszámot, hogy 3a + 7b + 9c = 54 . 3.12. Keressük meg az a, b prímszámokat úgy, hogy aba , aab és baa is prímszámok és az összegük 555. 3.13. Keressük meg a p prímszámot úgy, hogy 2 p + 1, 3 p + 2, 4 p + 3 és 6p + 1 egyaránt prímszámok! 3.14. Keressük meg az összes n prímszámot úgy, hogy n + 2, n + 6, n + 8 és n + 14 szintén prímek! 3.15. Keressük meg az összes olyan n pozitív prímszámot, amire n + 1, n + 3, n + 7 , n + 9 és n + 15 egyaránt prímszámok. 3.16. Határozzuk meg a p ∈ prímek.
számot úgy, hogy a p, p2 + 2, p2 + 4 , p2 + 20 számok mind
3.17. Határozzuk meg az n, p ∈ számok mind prímek.
számokat úgy, hogy az n, n + 2 p , n + 2 p +1, n + 2 p + 2
3.18. Határozzuk meg az n, p ∈ számok mind prímszámok.
számokat úgy, hogy a p, p + 2n , p + 2n +1, p + 2n + 2 , p + 2n+3
3.19. Határozzuk meg az n, p ∈ mind prímszámok.
számokat úgy, hogy p, p + 3n , p + 3n +1, p + 3n + 2 , p + 3n +3
3.20. Határozzuk meg az összes olyan p prímszámot, hogy 24 p + 1 egy négyzetszám. 3.21. Határozzuk meg az összes olyan p prímszámot, hogy 17 p + 1 egy négyzetszám. 3.22. Mutassuk meg, hogy a következő számok összetett számok! 12321, 1234321, 123454321, 12345654321 3.23. Mutassuk meg, hogy az a = 2 ⋅ 10 n + 61, n ∈
*
szám nem egy prímszám.
3.24. Határozzuk meg az a = 22 n +1 ⋅ 25n ⋅ 53 − 1 szám jegyeinek a számát! Prímszám-e ez a szám? 3.25. A 22004 + 1 szám prímszám-e? 3.26. Mutassuk meg, hogy az a = 262 + 1 szám két 1-nél nagyobb relatív prímszám szorzata!
3.27. Létezik-e olyan természetes n szám, hogy az a = n 4 + 2n 3 + 2n 2 + 2n + 1 szám egy prímszám? 3.28. Bizonyítsuk be az 1. lemmát! 1.4. Számok más számrendszerekben történő megjelenítései
Az előző részekben minden számot a tízes számrendszerbeli alakjukban használtunk. Léteznek más számrendszerbeli megjelenítések is, amik különböző okok miatt fontosak: például a 2-es illetve 16-os számrendszernek az informatikában fontos szerepe stb. A kettes számrendszer két számjegyet használ, a 0-t és 1-et, a hármas számrendszerbeli megjelenítés 3 számjegyet használ: 0-t, 1-et és 2-őt és így tovább. Hogy jelöljük, hogy az adott N szám egy b alapú számrendszerben van megjelenítve, azt írjuk, hogy N( b ) . b = 10 esetén elhagyhatjuk a jelölést: 4.1. Mutassuk meg, hogy 1(2) +11(3) +111(4) +1111(5) +11111(6) =3311(8) . Megoldás. Mindegyik számot átalakítjuk a tízes számrendszerbeli alakjába: 1(2) = 1; 11(3) = 1⋅ 31 + 1 = 4; 111(4) = 1 ⋅ 42 + 1⋅ 41 + 1 = 21;
1111(5) = 1⋅ 53 + 1⋅ 52 + 1 ⋅ 51 + 1 = 156; 11111(6) = 1 ⋅ 6 4 + 1 ⋅ 63 + 1 ⋅ 62 + 1 ⋅ 61 + 1 = 1555; 3311(8) = 3 ⋅ 83 + 3 ⋅ 82 + 1⋅ 81 + 1 = 1737, és leellenőrizzük az egyenlőséget. Valóban, azt kapjuk, hogy 1 + 4 + 21 + 156 + 1555 = 1737 . 4.2. Határozzuk meg az x számjegy értékét, ha x ( x + 1)(7) = ( x + 1) x (4) . Megoldás. Igaznak kell lennie, hogy x + 1 ≤ 3 és x ≥ 1. Mivel x ( x + 1)(7) = 7 x + x + 1 = 8 x + 1
és ( x + 1)x = 4( x + 1) + x , így azt kapjuk x = 1.
Gyakorlatok (7) 4.3. Határozzuk meg az x és y számokat úgy, hogy 12( x ) + 36( y ) = 34 . 4.4. Határozzuk meg az x és y számokat úgy, hogy 13( x ) + 31( y ) = 23 . 4.5. Hány jegyű a p szám a kettes számrendszerben, ha 1 + p = 22004 számrendszerben) ?
(a tízes
4.6. A kettes számrendszerbeli alakjuk felírása nélkül határozzuk meg, hány jegyűek az 1234 és 567 számok a kettes számrendszerben! 4.7. Keressük meg a köbszámokat az a = 123(4) , b = 325(6) , és c = 117(8) számok közt! 1.5. Kevert feladatok
22...2 szám felírható két egymást követő pozitív egész 5.1. Mutassuk meg, hogy az 44...4 {{ n − szer
n − szer
szám szorzataként. 5.2. Keressük meg az összes olyan háromjegyű abc számot, hogy abc = 8abc . 5.3. Mutassuk meg, hogy abab ⋅ cd = cdcd ⋅ ab . 5.4. Mutassuk meg, hogy egyetlen n ∈ b = 2n +1 ⋅ 5n + 1 számok négyzetszámok.
esetén sem lesznek az a = 2n ⋅ 5n +1 + 1 és
5.5. Prímszám-e az n = 22007 + 1 szám? 5.6. Mutassuk meg, hogy 7n − 4 nem négyzetszám egyetlen n ≥ 1 szám esetén sem! 5.7. Mutassuk meg, hogy hét egymást követő természetes szám négyzetének összege osztható 7-tel. 5.8. Határozzuk meg az a, b, c, d értékét úgy, hogy abcd + abc + ab + a = 2002 . 5.9. Határozzuk meg az a, b, c, d értékét úgy, hogy abcd + bcd + cd + d = 2222 . 5.10. Határozzuk meg az a és b nem 0 számjegyeket úgy, hogy aa × a0a = bbbb . 5.11. Határozzuk meg az a, b, c számjegyeket úgy, hogy ac × b1 = 1abc . 5.12. Határozzuk meg az a, b, c, d számjegyeket úgy, hogy abcd = cd × bcd . 5.13. Határozzuk meg az a, b, c számjegyeket és az n számot úgy, hogy abc × abc = ncba . 1.6. Megoldások, útmutatók, válaszok 1.6.1. Gyakorlatok (1) 1.8. ld (19831986 ) = ld (31986 ) = 9 , mivel 1986 ≡ 2(modulo 4) ,
ld (19841986 ) = ld (41986 ) = 6 és ld (19851986 ) = 5 . Így ld (N ) = 0 és ezért N M10 . 1.9. a = 52 n + 3 ⋅ 32( n + 2) + 32 n +1 ⋅ 52( n +1) = 52n + 2 ⋅ 32n +1(5 ⋅ 33 + 1) = 136 ⋅ 52n + 2 ⋅ 32n +1 . 136 = 8 ⋅ 17 , ezért azt kapjuk, hogy aM17 . 1.10.
a = (7 ⋅ 9)n + 7n +1 ⋅ 32n +1 - (3 ⋅ 7)n ⋅ 3n + 2 = 7n ⋅ 32n + 7n +1 ⋅ 32n +1 − 32n + 2 ⋅ 7n = = 7n ⋅ 32n (1 + 7 ⋅ 3 − 32 ) = 13 ⋅ 7n ⋅ 32n M13 .
1.11. Legyen N = an an -1 … a2a1 a megadott szám. Azt kapjuk, hogy
Mivel
N = an ⋅ 10n −1 + an −1 ⋅ 10n −2 + K + a2 ⋅ 10 + a1 = = an (9 + 1)n −1 + an −1(9 + 1)n −2 + K + a2 ⋅ (9 + 1) + a1 = = M 9 + an + an −1 + K + a2 + a1 . Ezért N M 3 , (rendre 9-re is) akkor és csakis akkor, ha a számjegyeinek az összege osztható 3-mal, illetve rendre 9-cel. 1.6.2. Gyakorlatok (2) 2.1.
a) x ∈ {0,5} ; b) x ∈ {0,6} ; c) x = 6 .
2.2. Mivel 15 = 3 ⋅ 5 és lnko(3, 5) = 1 , 15 | 2 x3 y akkor és csakis akkor ha osztható 3-mal és 5-tel is. Azt kapjuk, hogy y = 0 és x ∈ {1, 4,7} ; y = 5 és x ∈ {2,5,8} . 2.3. ( x, y ) ∈ {(0, 4), (2,2), (4,0), (5,8), (7,6),(9, 4)} . 2.4. ( x, y ) ∈ {(5,0), (0,5), (9,5)} . 2.5. Mivel 156 = 4 ⋅ 39 és lnko(4, 39) = 1 , ezért elegendő bebizonyítani, hogy N M 4 és N M 39 . Csakugyan, így következik, hogy N = (3 + 32 + 33 ) + 33 (3 + 32 + 33 ) + … + 31983 (3 + 32 + 33 ) = 39 ⋅ A , és N = (3 + 32 ) + 32 (3 + 32 ) + … + 31984 (3 + 32 ) = 12 ⋅ B . 2.6. és 2.7. Az 1.7-hez hasonlóan. 2.8.
a = n 5 − n = n(n 4 − 1) = n(n 2 − 1)(n 2 + 1) = (n - 1) ⋅ n ⋅ (n + 1) ⋅ (n 2 + 1) . Az 1.2 és 1.3 alapján tudjuk, hogy ( n − 1) ⋅ n ⋅ ( n + 1)M 6 . Mivel 30 = 6 ⋅ 5
és
lnko(5, 6) = 1 ezért azt kell bizonyítanunk, hogy aM 5 . Bármely n természetes szám felírható a következő alakok egyikébe: {5k , 5k + 1, 5k + 2, 5k + 3, 5k + 4}, k ∈ N . Ha n ∈ {5k , 5k + 1, 5k + 4} , akkor nyilvánvalóan aM 5 . Ha n = 5k + 2 , akkor n 2 + 1 = 25 k 2 + 20 k + 4 + 1 = M 5 , n 2 + 1 = 25 k 2 + 30 k + 9 + 1 = M 5 .
míg
ha
n = 5k + 3 ,
akkor
2.9. Az 1.7-eshez hasonlóan. 2.10. Ez a következőből következik: 2 ⋅ (3a + 5b ) + 7 ⋅ (4a + b ) = 17(2a + b ) . Visszafelé is nyilvánvalóan igaz. 2.11. - 2.13. A 2.10-hez hasonlóan. 2.14. a) Legyen d = lnko(6n + 5, 7 n + 6) , ami azt jelenti, hogy d | 6n + 5 és d | 7n + 6 . Ekkor d | 6 ⋅ (7n + 6) - 7 ⋅ (6n + 5) = 1 , azaz, d = 1 . 1.6.3. Gyakorlatok (3)
2.16. Két esetünk lehet, vagy n = d11 ⋅ d21 (d1 < d2 ) vagy n = d 3 , ahol d1, d 2 ,d prímszámok. A
második esetben az osztók d , d 2 , d 3 de a d 6 = 225 egyenletnek nincsen egész gyöke. Így az marad, hogy n = d1d 2 és a d1 ⋅ d 2 ⋅ d1d 2 = 225 kifejezésből azt kapjuk, hogy d1 = 3 és d2 = 5 . Ezért n=15 a keresett szám. 2.17. A számnak a következő alakúnak kell lennie n = d 4 , d egy prímszám. Ezért n csak d = 7 esetén lesz egy négyjegyű szám és ekkor n = 74 = 2401.
2.18. a) n = 45 ; b) n = 32 . 2.19. ab = p 3 , p egy prímszám, vagy ab = m ⋅ n , m és n prímszám. Azt kapjuk, hogy
ab ∈ {74, 77, 82, 85} . 2.20. Mivel 10 = 2 ⋅ 5 és 6 = 2 ⋅ 3 , ezért azt kapjuk, hogy n = 2a ⋅ 5b ahol (a + 1)( b + 1) = 6 . Ha a = 1, b = 2, n = 50 ; ha a = 2, b = 1 , akkor n = 20 . 2.21. 42 = 2 ⋅ 3 ⋅ 7 és innen n = a m ⋅ b n ⋅ c p ahol (m + 1)(n + 1)( p + 1) = 2 ⋅ 3 ⋅ 7 . A legkisebb
számot m = 1, n = 2, p = 6, a = 5, b = 3, c = 2 esetén kapjuk meg, azaz 26 ⋅ 32 ⋅ 5 = 2880 . 2.22. Legyen abc = 7 n ⋅ 5 m … .. Az osztóinak a száma (n + 1)(m + 1)… = 3 ⋅ 3 ⇒ n + 1 = 3 és m + 1 = 3 . Így a legkisebb lehetséges szám a 72 ⋅ 52 = 1225 lesz, ami négyjegyű.
2.23. A legkisebb szám a 675 és a legnagyobb az 511 (ha elfogadjuk, hogy az a és b szám lehet 0 is). 2.24. Tudjuk, hogy ( x + 1)( y + 1)( z + 1) = 144 . Mivel x, y, z prímszámok, ezért a következő szorzatra bontást használjuk: 144 = 4 ⋅ 6 ⋅ 6 ami megadja a megoldásokat: (3,5,5), (5,3,5), (5,5,3). 2.25. n ∈ 32 ⋅ 5 ⋅ 75 ; 3 ⋅ 52 ⋅ 73 } újraírni!
. 1.6.4. Gyakorlatok (4) 2.28. lnko( a, b) ⋅ lkkt( a, b) = a ⋅ b ⇒ 4 ⋅ [ lnko( a, b) ] = 1600 ⇒ lnko( a, b) = 20 . 2
Így, a = 20, b = 80 vagy a = 80, b = 20 a megoldások. 2.29. 3 és 105. 2.30. a = 77, b = 33 . 2.31. (a, b ) ∈ {(4,24), (8,12), (12,8),(24,4)} . 2.32. Mivel lnko( a, b) | a és a | lkkt( a, b) , ezért következik, hogy lnko( a, b) | lkkt( a, b) ahonnan lnko( a, b)|(lkkt( a, b) − lnko( a, b)) , ami szerint 34|lnko( a, b) . Alkalmazzuk a következő jelölést d = lnko( a, b) . Ekkor d ∈ {1,2,17,34} és a megoldások:
(a, b ) ∈ {(1,35),(5,7), (2,36), (4,18), (17,51), (34,68)} .
1.6.5. Gyakorlatok (5) 2.35. lkkt(24,36, 30, 75) = 1800 , így x = 1800k + 5 , 11| x . Azt kapjuk, hogy x = 7205 . 2.36. lkkt(9,12,15 = 180) , n = 9 ⋅ c1 + 6 ; n = 12 ⋅ c2 + 9 és n = 15 ⋅ c3 + 12 . Így 9 | ( n + 3) ,
12 | ( n + 3) k∈
*
és
15 | ( n + 3) .
Ezért
180 | ( n + 3) ,
azaz
n + 3 = 180k ,
⇒ n = 180k - 3 = 180(k - 1) + 177 . A maradék 177.
2.37. lkkt(9,10,15) = 90 ⇒ n = 90k + 7 ; n ∈ {187,997} . 2.38. A maradék 0 vagy 1 lehet. Ha , r = 0 ⇒ n = lkkt(2, 3, 4, 5, 6, 7) ⋅ k k ∈ ⇒ n ∈ {210, 420,630, 840} . Ha r = 1 ⇒ lkkt(2, 3, 4, 5, 6, 7) = 30 és a legkisebb szám a 30 ⋅ 10 + 1 = 301 . A megoldások: 301 + 210 ⋅ k , k ∈ , azaz, n ∈ {301, 511, 721, 931} . 1.6.6. Gyakorlatok (6) 3.5. Ha
n = 2k , akkor
n = 214243 + 2 + ... + 2 , míg n = 2k + 1 esetén azt kapjuk, hogy k − szor
n = 214243 + 2 + ... + 2 + 3 . k −1− szer
3.6. Legyen p egy prímszám, p > 2 , így p egy páratlan szám. Ha q1 + r1 = p és q2 − r2 = p , akkor a q1, r1 számok egyike és a q2 , r2 számok egyikének párosnak kell lennie, azaz, p = q1 + 2 = q2 − 2 , ahol q1 és q2 prímszámok. Ezért p − 2, p és p + 2 mind prímszámok, így p = 5 az egyetlen megoldás (bizonyítsuk be!). 3.7. n 2 + n = n(n + 1)M2 , így a prímszámok egyike páros, azaz egyenlő 2-vel, és így a többi páratlan, és így nem egymást követő számok. Hogy legyen két egymást követő prímszám, a 3-nak benne kell lennie a halmazban, és a harmadik szám az n 2 + n − 5 , ami prímszám n = 3 esetén. A számok 2, 3 és 7. 3.8. a = 1249, b = 283, c = 2 . 3.9. a = 2, b = 269, c = 1723; a = 269, b = 2, c = 1723 . 3.10. a = 2, b = 2, c = 5 . 3.11. 233 és 532. 3.12. a = 1, b = 3 . 3.13. p = 5 . 3.14. n = 5 . 3.15. n = 4 . 3.16. p = 3 esetén a következő megoldást kapjuk: 3, 11, 13, 29. Bebizonyítjuk, hogy ez az egyetlen megoldás. Bármely p természetes szám felírható a következő alakok egyikébe:
3k , 3k + 1, 3k + 2, k ∈ . Ha p = 3k és k > 1, p egy összetett szám ( p = 1 esetén kapjuk a fenti megoldást); Ha p = 3k + 1 , akkor p2 + 2 = 3(3k 2 + 2k + 1) , ami egy összetett szám ∀ k ∈ Ha p = 3k + 2 , akkor p + 20 = 3(3k + 4k + 8) , ami egy összetett szám ∀ k ∈ 2
2
; .
3.17. Az n prímszámnak páratlannak kell lennie. Mivel a 2 p , 2 p +1, 2 p + 2 számok között mindig találunk legalább egy M 3 + 1 alakú számot, és legalább egy M 3 + 2 alakú számot (bizonyítsuk be!), ezért a megadott sorozatban akkor és csakis akkor lehetnek prímszámok, ha n = 3k (és k = 1), ellenkező esetben legalább az egyik szám összetett szám lesz. Ezért n = 3 és a sorozat: 3, 3 + 2 p , 3 + 2{ p+1} , 3 + 2{ p + 2} . A következő eseteket vizsgáljuk: p ∈ {3m, 3m + 1, 3m + 2 | m ∈ } . 1) p = 3m esetén azt kapjuk, hogy
2 p = (23 )m = (7 + 1)m = M 7 + 1 2 p +1 = 2 p ⋅ 2 = ( M 7 + 1) ⋅ 2 = M 7 + 2 2p +2 = M 7 + 4 és ezért a 3 + 2 p + 2 = M 7 szám összetett szám m ≥ 1 esetén (az m = 0 esetben 3 + 2 p = 4 egy összetett szám); 2) p = 3m + 1 esetén azt kapjuk, hogy 3 + 2 p +1 = 3 + 23 m + 2 = 3 + 2 p +1 = 3 + 23 m + 2 = M 7 , ami összetett szám m ≥ 1 esetén. Az m = 0 esetben egy prímszámokból álló sorozatot kapunk: 3, 5, 7 és 11; 3) p = 3m + 2 esetén azt kapjuk, hogy 3 + 2p = M 7 , egy összetett szám minden m ≥ 1 esetén. Az m = 0 esetben p = 2 , és egy prímszámokból álló sorozatot kapunk {3,7,11,19}. Ezért a feladatunk megoldása ( n, p ) ∈ {(3,1),(3,2)} . 3.18. A 2.53-hoz hasonlóan, azt kapjuk, hogy p = 3 és ekkor n = 1. 3.19. Mivel a 3 n , 3 n +1, 3n + 2 , 3n + 3 számok páratlanok, ezért a p számnak párosnak kell lennie, azaz p = 2 . Az egymást követő 3 n , 3 n +1, 3n + 2 , 3n + 3 hatványok utolsó jegyei 3, 9, 7, 1 lesznek
valamilyen sorrendben bármely n ∈ * esetén. Így az egyik hatvány utolsó számjegye 3 lesz és így ennek a hatványnak és 2-nek az összege 5-re fog végződni, azaz osztható lesz 5-tel. Így az n = 0 vagy n = 1 eseteket kaphatjuk, rendre a 2, 3, 5, 11, 29 és 2, 5, 11, 29, 83 megoldásokkal. 3.20. 24 p + 1 = k 2 ⇒ p = p ∈ {2,5,7} .
k2 −1 , k = 2l + 1, l ∈ 24
és innen p =
l (l + 1) , l∈ 6
3.21. 17 p + 1 = k 2 ⇒ 17 p = (k − 1)(k + 1) stb. A válasz: p = 19 . 3.22. 12321 = 1112 , 1234321 = 11112 ,K . 3.23. a = 2 00...061 1 424 3 és így a számjegyeinek összege 9, így aM 9 . n − 2 − szer
. Azt kapjuk, hogy
3.24. a = 22 n +1 ⋅ 53 − 1 = ( 2 ⋅ 5 )
2 n +1
⋅ 52 − 1 = 25000...0 { ⇒ 2n + 3 jegye van. Mivel 123 − 1 = 24 99...9 2 n +1− szer
2 n +1− szer
a számjegyeinek összege 2 + 4 + 9(2n + 1)M 3 , ezért a osztható 3-mal is. 3.25. Vegyük észre, hogy 2004 = 3 ⋅ 668 és innen 22004 + 1 = (2668 )3 + 1 = (2668 + 1)(22⋅668 − 2668 + 1) . Így a szám összetett szám. 3.26. a = 262 + 1 = 431 + 1 = (4 + 1)(430 - 429 + … - 4 + 1) = 5k , ahol
k = 430 − 429 + 428 − K + 42 − 4 + 1 = (5 − 1)30 − (5 − 1)29 + K + (5 − 1)2 −
−(5 − 1) + 1 = M 5 + 114 + 124 + ... + 31 = M 5 + 1 , ami relatív prímszám az 5-höz képest. 31− szer
3.27.
a = n 2 (n 2 + 2n + 1) + (n 2 + 2n + 1) = (n 2 + 2n + 1)(n 2 + 1) = (n + 1)2 ⋅ (n 2 + 1)
összetett szám, ∀ n ∈
*
ami
egy
.
1.6.7. Gyakorlatok (7) 4.3. x = 5, y = 7 . 4.4. x = 7, y = 4 vagy x = 4, y = 5 . 4.5. p = 22004 − 1 = 22003 + 22002 + ... + 2 + 1 = 11...1 {
2004 − szer
(2) ,
így p-nek 2004 számjegye van a kettes
számrendszerbeli alakjában. 4.6. 210 < 1234 < 211; 29 < 567 < 210 . Így, 1234-nek 11 jegye van és 567-nek 10 jegye van a kettes számrendszerben. 4.7. a = 27 = 33 , b = 125 = 53 . 1.6.8. Kevert feladatok 5.1.
a = (1 + 10 + K10n −1 ) + 4 ⋅ 10n (1 + 10 + K + 10n −1 ) =
10n − 1 10n − 1 10n − 1 2 ⋅ 10n − 2 2 ⋅ 10n + 1 + 4 ⋅ 10n ⋅ = 2⋅ (1 + 2 ⋅ 10n ) = ⋅ . 9 9 9 3 3 A 2 ⋅ 10n − 2 és 2 ⋅ 10n + 1 számok oszthatók 3-mal, mivel = 2⋅
2 ⋅10n − 2 = 2 ⋅10n + 1 − 3 = 2 00...01 { −3 n −1− szer
és
2 ⋅10 n + 1 = 2 000...01 123 . n −1− szer
Továbbá,
2 ⋅ 10n − 2 2 ⋅ 10n + 1 +1= . 3 3
5.2. abc = 8abc ⇔ bc = 4a(2bc − 25) . Megoldások: 128; 672. 5.3. abab = ab ⋅ 101 .
5.4. a = 500...01 { és b = 200...01 { . Az a és b számok egyaránt oszthatóak 3-mal, de 9-cel n −1− szer
n −1− szer
nem, így nem négyzetszámok. 5.5. Mivel 2007 = 9 ⋅ 223 , ezért n egy összetett szám. 5.6. Bármely négyzetszám felírható a következő alakok egyikébe 8k, 8k + 1, 8k + 4 (bizonyítsuk is be!). Ezután látjuk, hogy a 7n − 4 szám 8k + 5 (ha n páros) vagy 8k + 3 formájú (ha n páratlan). 5.7.
(7k )2 + (7k + 1)2 + (7k + 2)2 + (7k + 3)2 + (7k + 4)2 + (7k + 5)2 + (7k + 6)2 = 6 ⋅ 7 ⋅ 13 = M 7 + 1 + 22 + 3 2 + 4 2 + 5 2 + 6 2 = M 7 + = M7. 6
5.8. 1803. 5.9. 1573. 5.10. a = 2, b = 4; a = 3, b = 9; a = b = 1 . 5.11.
ac × b1 = 1abc ⇔ c − 1 =
100 + 9a − 10a b
(4)
ami azt mutatja, hogy
100 + 9a ∈ . (5) 6 Az nem lehet, hogy c = 1 mivel akkor a (4)-es állításból az következne, hogy 100 = a(10b − 9) és így a = 4 (mivel 10b − 9 páratlan) és innen 10b − 9 = 29 ami lehetetlen. Ezért c − 1 ≥ 1 és a (4)-es alapján azt kapjuk, hogy 100 + 9a 1≤ − 10a ≤ 8 . (6) b Ha a b ∈ {7,8} eseteket megvizsgáljuk, akkor a (6)-osból azt kapjuk, hogy a = 1 , amire a (4)es nem igaz. A b = 5 esetben a (4)-es állításból az következik, hogy a ∈ {4,8} , amik nem elégítik ki a (6)-ot. Ezért a b = 2 eset maradt. Az (5)-ből az következik, hogy a páros és a (6)-ból az következik, hogy 11a ≥ 84 , azaz a ≥ 8 . Így a = 8 és akkor a (4)-es szerint azt kapjuk a végén, hogy c = 7 . Így, a = 8, b = 2 és c = 7 az egyetlen megoldás. 5.12. A 2.81-hez hasonlóan megoldva azt kapjuk, hogy a = 3, b = 1, c = 2, d = 5 . 5.13. Az egyetlen megoldás: a = 9, b = 6, c = 3 és 963 × 963 = 927369 .
