Ugrás a tartalomhoz

Elemi matematika feladatgyűjtemény

Hraskó András (2013)

ELTE-TTK

12 Számelmélet feladatok megoldása

12 Számelmélet feladatok megoldása

12.1 Osztók és többszörösök feladatok megoldása

A 4.1.1 feladat megoldása

a)-b) Amikor 7 részre osztott egy darabot, 6-tal nőtt a részek száma, amikor 13 részre osztott egy darabot, 12-vel nőtt a részek száma. Emiatt a részek számának 6-os maradéka nem változott. Mivel eredetileg 1 papírlapja volt és a darabszámot csak hattal osztható darabszámmal tudta növelni, akármit tett, csak a 6k+1 alakú darabszámokat tudta elérni, tehát 2000-et biztosan nem. Másrészt minden 6k+1 alakú darabszám elérhető k db 7 részre tépéssel.

c) Most egy lépésben 6-tal és 15-tel növelhetjük a darabszámot, tehát a növekmény mindig osztható 3-mal. Ezért kizárólag a 3-mal osztva 1 maradékot adó darabszámok érhetők el. Könnyű ellenőrizni, hogy az 1, 4, 7, 10, 13, 16 közül a 4 és a 10 nem érhető el, de a többi igen. A sorozat további tagjai mind elérhetőek, mert a 13 és a 16 hatos növeléseivel minden náluk nagyobb 3k+1 alakú szám előállítható.

d) A darabszám itt 6-tal és 13-mal nőhet, így az alábbi számok elérhetőek: 61=1+106, 62=1+113+86, 63=1+213+66, 64=1+313+46, 65=1+413+26, 66=1+513. További hatos növeléssel ezekből minden 66-nál nagyobb darabszám is elérhető. A 60 viszont nem kapható meg, mert 1-hez képest a hatos maradékot 5-tel kellene növelni, amihez legalább öt 13-as növelés kellene, de az túl nagy számot eredményezne. A 60-nál kisebb pozitív egészek egy része megkapható, másik része nem.

12.1.0.1 Megjegyzés a 4.1.1 c-d) feladatok megoldásához

A téma a 4.7.1 feladatban folytatódik.

A 4.1.2 feladat megoldása

Amikor két szám helyére a különbségüket írjuk, a táblán levő számok összegének paritása nem változik. Ezek szerint, ha a táblán levő számok összege páros, akkor az utolsónak maradt szám is páros lesz, ha az összeg páratlan, akkor páratlan.

A 4.1.3 feladat megoldása

a), c), d) ,e), g) helyes, a többi nem.

b)-re ellenpélda az x=60;

f)-re példa az x=6;

h)-ra példa az x=3 és y=5.

A 4.1.4 feladat megoldása

a) 25, b) 100, c) 441, d) 36 e) 100, f) 1728, g) 648,

h) ilyen nincs (ha egy szám páros és 3-mal osztható, akkor 6-tal is, így a négyzete 36-tal is, így 18-cal is.)

i) 200.

A 4.1.5 feladat megoldása

a) Nincs ilyen számhármas (az első két feltétel miatt n is és k is páros, így legnagyobb közös osztójuk nem lehet páratlan)

b) Nincs ilyen számpár (az első feltétel miatt mindkét szám osztható 3-mal, így a legkisebb közös többszörösüknek is oszthatónak kellene lennie).

c) Mivel 120=2335, a legkisebb pozitív egész, az első feltételnek megfelelő mn a 263252 (m=2335, n=2335)

Így 5mn=263253, melynek legkisebb (pozitív egész) többszöröse amely négyzetszám, az 5-szöröse, vagyis 263254.

m, n számpár pl. az m=23352, n=2335

További megfelelő számpárokat kapunk, pl. ha m és n közül valamelyiket megszorozzuk 2-től, 3-tól és 5-től (és egymástól) különböző prímek páros kitevőjű hatványaival.

A 4.1.6 feladat megoldása

A páros számok száma 2010-ig [20102]=1005, a néggyel oszthatóké [20104]=512 stb.

1005 + 502 + 251 + 125 + 62 + 31 + 15 + 7 + 3 + 1 = 2002 .

Tehát a válasz: 22002.

12.1.0.2 Megjegyzés a 4.1.6 fel. megoldásához

Általában, az n! szorzatban a p prím kitevőjét a

[ n p ] + [ n p 2 ] + [ n p 3 ] +

összeg adja meg, amelyben [x] az x szám egész részét jelöli. Ugyan a fenti összeg általános alakja végtelen tagú, de minden konkrét n-re véges sok tagból áll, hiszen p elég nagy hatványa, már nagyobb n-nél, és így az azokhoz tartozó egész részek már zérók. Magyarázzuk meg a képletet!

A 4.1.7 feladat megoldásai

12.1.0.3 A 4.1.7 a) mego.

A teljes szorzat 2-es és 5-ös prímtényezőit kell számba venni. Nyilván 5-ösből van kevesebb, 24, tehát 24 db 0-ra végződik a szorzat.

12.1.0.4 A 4.1.7 b) fel. I. megoldása

Felírjuk a szorzat prímtényezős alakját:

100 ! = 2 97 3 48 5 24 7 16 11 9 13 7 17 5 19 5 23 4 29 3 31 3 37 2 41 2 43 2 47 2 53 59 61 67 71 73 79 83 89 97

Ha ezt elosztjuk 1024=224524-nel, az így kapott szám, azaz

2 73 3 48 7 16 11 9 13 7 17 5 19 5 23 4 29 3 31 3 37 2 41 2 43 2 47 2 53 59 61 67 71 73 79 83 89 97 utolsó számjegye a kérdés.

A szorzatban szereplő egyes prímhatványok utolsó számjegyei rendre: 2, 1, 1, 1, 7, 7, 9, 1, 9, 1, 9, 1, 9, 9, 3, 9, 1, 7, 1, 3, 9, 3, 9, 7, melyek szorzata 4-re végződik.

12.1.0.5 A 4.1.7 b) fel. II. megoldása

Csoportosítsuk 100! tényezőit az ötös osztó szerint, majd azon belül négyes csapatokban!

Négy tényező: 255075100=58(1234).

További 16 tényező: 51015203045=516(1234)(69)

Míg a maradék 80 tényező: (1234)(69)

Ezek szerint a 100!524 szorzat 5-ös maradéka:

100 ! 5 24 ( 1 2 3 4 ) 1 + 4 + 20 ( - 1 ) 25 - 1 ( mod 5 ) .

Mivel 2241(mod5), így 100!1024-1(mod5), tehát 100! utolsó nemnulla számjegye 9 vagy 4, de nyilván páros, tehát 4.

A 4.1.8 feladat megoldása

186 340 = 2 2 5 7 31 43 .

A 7-es prímtényezőnek a számpár mindkét tagjában szerepelnie kell, 2-es csak az egyikben szerepelhet, ha legnagyobb közös osztójuk 7.

Legyen mondjuk a=227 és b=7

A kérdés most az, hogy a legkisebb közös többszörös maradék 3 prímtényezőjét hányféleképp tudjuk szétosztani a és b között. Lehet, hogy mindhármat a kapja (1 lehetőség), lehet, hogy kettőt a, egyet b (3 lehetőség, függően attól, melyiket kapja b), lehet, hogy egyet a, kettőt b (ugyanúgy 3 lehetőség), és lehet, hogy mindhármat b (1 lehetőség).

Ez összesen 8 lehetőség (megfelelően annak is, hogy mindhárom tényezőre egymástól függetlenül két lehetősége van a-nak: vagy megkapja, vagy nem).

További 8 lehetőséget jelent, ha rendezett számpárokban gondolkodunk, amikor b a páros.

A 4.1.9 feladat megoldása

Az 50! prímtényezős alakja 2473325127811 (a további 50-nél kisebb prímtényezők első hatványon szerepelnek).

Így a legnagyobb négyzetszám, amely az 50! osztója, a 24633251278

A 4.1.10 feladat megoldása

a) 600-ig 300 páros (A halmaz), 200 db 3-mal osztható (B halmaz) és 120 db 5-tel osztható szám (C halmaz) van (lásd a 118. ábrát).

118. ábra

Az egyes halmazok közös részeit számba véve adódik, hogy a kimaradók létszáma 160.

b) A sem 2-vel, sem 3-mal, sem 5-tel nem osztható számok lesznek megfelelőek. Ezek száma 1600.

A 4.1.11 feladat megoldása

Minden pozitív egész szám felírható 2nm alakban, ahol n0, és m páratlan pozitív egész szám.

Ekkor a szám páratlan osztóinak összege megegyezik m osztóinak összegével.

Ha az eredeti szám páros volt (n1), akkor minden páratlan osztónak a kétszerese (alkalmasint a 4-szerese stb) is osztó, így a páros osztóinak összege minimum kétszerese a pártalanokénál. A válasz tehát: csak a páratlan számokra teljesül, hogy páros osztóiknak összege kisebb a páratlan osztóik összegénél amikor is nincs páros osztójuk.

A 4.1.12 feladat megoldásai

12.1.0.6 A 4.1.12 a) mego.

Azok a korongok lesznek végül kékek, amelyeket páratlan sokszor fordítottunk meg, vagyis, amelyek sorszámának páratlan sok osztója van. Többféleképp rájöhetünk arra (próbálgatással, okoskodással az osztók számára vonatkozó képlet felhasználásával), hogy ezek épp a négyzetszámok, vagyis 10 korong lesz kék oldalával felfelé.

12.1.0.7 A 4.1.12 b) mego.

Azok a korongok lesznek kékek, melyek sorszámának osztóit összeadva páratlan számot kapunk. Meggondolható, hogy ehhez az szükséges, hogy páratlan sok páratlan osztójuk legyen, vagyis 2km2 alakúak legyenek. 100-ig 17 ilyen szám van.

A 4.1.13 feladat megoldása

a)-b) Igen, előáll. Pld:

2000 = 398 + 399 + 400 + 401 + 402 = 68 + 69 + + 80 + 81 + + 92 = - 46 + ( - 45 ) + ( - 44 ) + ( - 1 ) + 0 + 1 + 2 + + 16 + + 77 + 78 .

c)-d)-e) Vizsgáljuk először az M pozitív egész szám előállításait úgy, hogy nem törődünk azzal pozitívak vagy negatívak az összeadandók, és megengedjük az egytagú összeget (ez maga M).

Legyen a tagok száma n. Ha n páratlan, akkor van egy középső szám, ami egész. Ha ez x, akkor nx=M. Az M minden pozitív páratlan m osztójához tartozik egy ilyen előállítás, ahol tehát n=m és x=Mn, a tagok:

M n - n - 1 2 , M n - n - 3 2 , , , M n - 1 , M n , M n + 1 , , M n + n - 1 2 .

Az a)-b) részekhez adott fenti példákban M=2000 esetén rendre az n=5, n=25, n=125 osztókhoz tartozó megoldásokat láthatjuk.

Ha n páros, akkor a számok átlaga, x nem egész, hanem egy egész szám fele. Ilyenkor viszont az n2, 2x számok mindketten egészek és 2x páratlan. Ráadásul x (és így 2x is) pozitív, hiszen x=Mn. Az M minden m pozitív páratlan osztójához tartozik egy ilyen megoldás is, ahol tehát az átlag x=m2, a tagok száma pedig n=2Mm. Az előállítás tagjai:

m + 1 2 - M m , m + 3 2 - M m , , m - 1 2 , m + 1 2 , , m - 1 2 + M m .

Pld a 2000 ilyen típusú előállításai:

2000 = = 47 + 48 + + 62 + 63 + + 77 + 78 = ( - 67 ) + + 11 + 12 + 13 + 14 + + 92 = ( - 397 ) + + ( - 1 ) + 0 + 1 + 2 + 3 + 4 + 5 + 402 = ( - 1999 ) + ( - 1998 ) + + ( - 1 ) + 0 + 1 + 2 + + 1999 + 2000 .

Tehát a b) esethez tartozó megoldások száma beleértve az egytagú összeget is az M szám páratlan osztóinak duplája.

Állítjuk, hogy az összes előállítás fele csak pozitív tagokat tartalmaz, a felében pedig előfordul a 0 és esetleg még negatív tagok is. A két csoport tagjai között kölcsönösen egyértelmű megfeleltetést létesítünk.

A tisztán pozitív tagú

k + ( k + 1 ) + + l ,

összeghez rendeljük az ugyanakkora értékű, de enmpozitív tagokat is tartalmazó

( 1 - k ) + ( 2 - k ) + + 0 + + ( k - 2 ) + ( k - 1 ) + k + ( k + 1 ) + + l

összeget. Megfordítva, ha egy összeg nempozitív tagokat is tartalmaz, akkor több pozitív tagja van, mint negatív, hiszen a teljes összeg pozitív. Így a negatív tagokat, azok ellentettjeit és a 0-t kidobhatjuk egyszerre az összegből, miáltal egy legalább egy tagból álló ugyanakkora értékű összeget kapunk.

A megfeleltetés mutatja, hogy a pozitív tagokból áll összegek száma (az egyetlen tagból állóval együtt) megegyezik az M szám páratlan osztóinak számával.

d) Páros számok összegeként csak a páros számok állnak elő, annyiféleképp, ahány (1-nél nagyobb) páratlan osztója a felüknek van.

A 4.1.14 feladat megoldása

a) A számok összege 1-től 10-ig 55. Így nyilván nem lehet egyenlő összegű két (3, 4) részre osztani őket úgy, hogy minden rész összege ugyanannyi legyen.

Öt részre lehet, pl. úgy, hogy az egyes részek a következők: (1;10), (2;9), (3;8), (4;7) és (5;6).

b) Ahhoz, hogy az egyes dobozokban ugyanannyi legyen a számok szorzata, az szükséges (de nem elégséges), hogy a 10! prímtényezői szétoszthatók legyenek a dobozok között, vagyis a 10! prímtényezős alakjában minden prím páros (3-mal, 4-gyel, 5-tel osztható) hatványon szerepeljen. Ez feladatunkban nyilván nem teljesül.

12.1.0.8 Megjegyzés a 4.1.14 feladathoz

Ha 1-től n-ig akarjuk két dobozba osztani a számokat úgy, hogy az összeg egyforma legyen a dobozokban, akkor ez nyilván nem oldható meg, ha 1-től n-ig a számok összege páratlan. További kérdés, hogy egyéb esetekben megoldható-e a kétfelé osztás. A válasz igen, többféle konstrukció elképzelhető, de a sejtés bizonyításra szorul.

A szorzatok két egyenlő részre osztása azon múlik, hogy találunk-e minden előforduló prímtényezőhöz párt. Ezt konkrét határok esetén megvizsgálhatjuk, az általánosítás azon a (Bertrand által sejtett, Csebisev által igazolt) tételen múlik, hogy minden szám és a kétszerese között van prímszám.

A 4.1.15 feladat megoldása

Először T értékét írjuk fel kétféleképpen: legyen M:=N/2. Vegyük észre, ha 1i<M és (i,N)=1, pontosan akkor, ha 1M-i<M és (M-i,N)=1. Ezért

T = 1 i < M , ( i , N ) = 1 i ; T = 1 i < M , ( i , N ) = 1 M - i ,

így összeadva a két formát

2 T = 1 i < M , ( i , N ) = 1 M .

Továbbá 1i<M és (i,N)=1, pontosan akkor, ha M<M+i<M és (M+i,N)=1.

Ezért

S - T = 1 i < M , ( i , N ) = 1 M + i = 1 i < M , ( i , N ) = 1 M + 1 i < M , ( i , N ) = 1 i = 2 T + T ,

amiből S=4T.

12.2 Oszthatósági szabályok

A 4.2.1 feladat megoldása

A 11-gyel és a 9-cel való oszthatóság segít: a=b=6.

A 4.2.2 feladat megoldása

Nincs ilyen négyzetszám (A számjegyek összege osztható 3-mal, így maga a szám is, de 9-cel nem)

12.3 Közös osztók, legnagyobb közös osztó feladatok megoldása

A 4.2.3 feladat megoldása

Ilyen számhármas pl. a 6=23, 10=25, 15=35.

Ha p, q és r különböző prímek, akkor általában is megfelelő számhármas a pq, pr, qr, de egyéb módon is gyárthatunk további jó számhármasokat, sőt akár számnégyeseket stb.

A 4.2.4 feladat megoldása

A legkisebb olyan k pozitív egészt keressük, amelyre 360|k75. Mivel 360=23325 és 75=352, így a legkisebb megfelelő k a 233=24.

A 4.2.5 feladat megoldása

Első eset: a és b relatív prímek. Ekkor az átló nem halad át rácsponton. Ahhoz, hogy például a bal alsó sarokból eljussunk a jobb felső sarokba, a-1 függőleges és b-1 vízszintes rácsegyenest kell kereszteznünk. Valahányszor átlépünk egy rácsegyenest, új kiszínezendő mezőbe lépünk, így a kiszínezett mezők száma a-1+b-1+1=a+b-1 lesz (+1 a kezdeti mező).

Ha a és b nem relatív prímek ((a;b)=d), akkor a téglalap felosztható a/b×b/d-es téglalapokra, melyekből éppen d darab helyezkedik el az átló mentén, így az eredmény (a/d+b/d-1)d=a+b-d.

12.4 Számrendszerek feladatok megoldása

A 4.3.1 feladat megoldása

A 112a+b=92b+a egyenletből 3a=2b. Mivel az a, b számjegyek a kilences számrendszerben is szerepeltek, így 0a,b8, azaz két nemtriviális megoldás van: a=2 és b=3 illetve a=4 és b=6, amelyek a tízes számrendszerbeli 245, 490 számoknak felelnek meg.

A 4.3.2 feladat megoldásai

12.4.0.1 A 4.3.2 fel. I. megoldása

(Elölről)

A kettő hatványai:

44. táblázat

Választunk egy 1024-et, marad 2010-1024=986. Ehhez választunk egy 512-t

2010 = 11111011010 2 = 1 2 10 + 1 2 9 + 1 2 8 + 1 2 7 + 1 2 6 + 0 2 5 + 1 2 4 + 1 2 3 + 0 2 2 + 1 2 1 + 0 2 0 .

12.4.0.2 A 4.3.2 fel. II. megoldása

(Hátulról)

A legkisebb helyiértéktől kezdjük meghatározni a felírást. 2010 páros, így 20=1-ből nem lehet benne. Ha ezt letöröljük a szám végéről, akkor a fele akkor a szám kettes számrendszerbeli alakját kapjuk meg. Így újra és újra 2-vel osztunk, a maradék lesz a kettes számrendszerbeli alak hátulról következő jegye és a hányadossal dolgozunk tovább (az alábbi táblázatban az új osztandó az előző osztás hányadosa:

45. táblázat

Tehát 2010=111110110102

12.4.0.3 A 4.3.2 fel. III. megoldása

(Ad hoc)

2048 = 2 11 azaz 2047=111111111112 (tizenegy darab 1-esből álló szám). Mivel 2047-2010=37=32+4+1=1001012, így 2010=111110110102.

Kérdések a 4.3.2 feladatról

1. Miért létezik és egyértelmű a (9) alakú felírás minden pozitív egész számra?

2. Nem egész számok kettes számrendszerbeli alakja hogy értelmezhető?

3. Létezik-e és egyértelmű-e a (9) alakú felírás, ha a számjegyeket módosítjuk? Helyettesítsük pl a k{0,1,,m} esetén 0nk1 részt ezzel: k{0,1,,m} esetén nk{-1,+1}, tehát a jegyek nem 0 és 1, hanem -1 és 1 lehetnek. Fel lehet-e így írni a 2010-et? Egyértelmű-e a felírás?

A 4.3.3feladat megoldásai

12.4.0.4 A 4.3.3 a) mego.

Az a alapú számrendszerbeli 2010a szám értéke

2 a 3 + a = a ( 2 a 2 + 1 ) ,

ami osztható a-val.

12.4.0.5 A 4.3.3 b) mego.

Nincs.

Ha 7 nem osztja a-t, akkor relatív prím hozzá, így a(2a2+1) csak akkor osztható héttel, ha a (2a2+1) kifejezés értéke osztható héttel. A négyzetszámok (lásd a2) hetes maradékai: 0, 1, 2 és 4, ezek dupláinak (lásd 2a2) hetes maradékai 0, 2, 4 és 1, így az ennél eggyel nagyobb szám (2a2+1) nem lehet osztható héttel.

12.4.0.6 A 4.3.3 c) mego.

A 4.3.3 b) mego. szerint az kell, hogy (2a2+1) osztható legyen tizeneggyel. Ez teljesül pl a=4 esetén, ami tehát megfelelő alap. Valóban, ekkor 20104=264+14=132=1112.

A 4.3.4 feladat megoldása

Legyen a szám A=10x+y. Az utolsó számjegy kétszeresét levonva x-ből a B=x-9y számot kapjuk. Ekkor A-10B=10x+y-10x+90y=91y, ami osztható 7-tel, így ha B osztható, akkor A is.

Megfordítva: ha A osztható, akkor 10B is, és mivel a 10 és a 7 relatív prímek, B is.

12.4.0.7 Megjegyzés a 4.3.4 feladathoz

Könnyen gyárthatunk hasonló szabályt más számokkal való oszthatóságra, pl. a fenti szabály ugyanilyen alapon 13-ra is jó (91=713).

A 4.3.5 feladat megoldása

A dndn-1d3d2d1d0¯ számjegysorozat értelmezése a alapú számrendszerben:

d n d n - 1 d 3 d 2 d 1 d 0 ¯ a = d n a n + d n - 1 a n - 1 + + d 3 a 3 + d 2 a 2 + d 1 a + d 0 .

Ha a (126) szám m számmal vett maradéka érdekel bennünket, akkor tudnunk kell az

1 , a , a 2 , a 3 , , a n - 1 , a n

számok m-es maradékait.

A 2 táblázatban gyűjtöttük ki a=10, azaz a 10-es számrendszer esetén néhány lehetséges m osztóra a 10 hatványainak maradékait .

2. táblázat. A $10$ hatványainak maradékai modulo $m$

A táblázat alapján

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d 0 ( mod 2 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d n + d n - 1 + + d 3 + d 2 + d 1 + d 0 ( mod 3 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d 1 d 0 ¯ 10 ( mod 4 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d 0 ( mod 5 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 + 3 d 7 + d 6 + 5 d 5 + 4 d 4 + 6 d 3 + 2 d 2 + 3 d 1 + d 0 ( mod 7 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d 2 d 1 d 0 ¯ 10 ( mod 8 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d n + d n - 1 + + d 3 + d 2 + d 1 + d 0 ( mod 9 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 d 0 ( mod 10 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 ( - 1 ) n d n + ( - 1 ) n - 1 d n - 1 ± + d 2 - d 1 + d 0 ( mod 11 ) d n d n - 1 d 3 d 2 d 1 d 0 ¯ 10 - 3 d 7 + d 6 + 4 d 5 + 3 d 4 - d 3 - 4 d 2 - 3 d 1 + d 0 ( mod 13 )

A 10 hatványainak m-es maradékai periodikus sorozatot alkotnak, így elvileg minden m-re készíthetünk oszthatósági szabályt, de az gyakran kényelmetlen, pl. a fenti 7-es és 13-as szabályok is azok. Fontos azonban látni, hogy a fenti képletek nem csak oszthatóság kérdéséről nyilatkoznak, hanem a maradékot is egyszerűbben kiszámítható alakban adják meg.

8 -as számrendszerben a 8 osztóival, azok hatványaival és 8±1 osztóival kapcsolatban kapunk egyszerű oszthatósági szabályt.

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 8 = d n 8 n + d n - 1 8 n - 1 + + d 3 8 3 + d 2 8 2 + d 1 8 + d 0 ,

így m=2k esetén n=[k3]-mal m|8n+1, tehát

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 8 d n d n - 1 d 2 d 1 d 0 ¯ 8 ( mod m ) ,

azaz csak az utolsó kb k3 db jegy számít.

m = 7 esetén 8i(7+1)i1(modm), tehát

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 8 d n + d n - 1 + + d 2 + d 1 + d 0 ( mod m ) ,

azaz a számjegyek összegének 7-es maradéka lesz a maradék.

m = 3 és 9 esetén m|(8+1), azaz m(-1)(modm), ezért

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 8 ( - 1 ) n d n + ( - 1 ) n - 1 d n - 1 ± - d 3 + d 2 - d 1 + d 0 ( mod m ) ,

azaz a számjegyek váltakozó előjelű összegének 3-as (9-es) maradéka lesz a maradék.

m = 5 esetén nem ilyen egyszerű, de nem is nagyon bonyolult az oszthatósági pontosabban maradékképzési szabály. A

8 0 , 8 1 , 8 2 , 8 3 , 8 4 , 8 5

stb számok 5-ös maradékai rendre

1 , 3 , - 1 , - 3 , 1 , 3

stb, tehát

d n d n - 1 d 3 d 2 d 1 d 0 ¯ 8 - 3 d 7 - d 6 + 3 d 5 + d 4 - 3 d 3 - d 2 + 3 d 1 + d 0 ( mod 5 ) .

A fentiekhez hasonlóan, a 9-es számrendszerben a 3-hatványokkal való oszthatóság (és a maradék is) csak az utolsó néhány jegyen múlik, a 2, 4, 8-cal való osztás maradéka megegyezik a számjegyek összegének maradékával, míg az 5-tel való osztási maradékhoz a számjegyek előjeles összegének maradékát lehet jól használni.

A 4.3.6 feladat megoldásai

12.4.0.8 A 4.3.6 a) mego.

Ha a számrendszer alapszáma a, akkor a 9-es számjegy szereplése miatt a>9. Mivel 169a=a2+6a+9=(a+3)2, így minden 9-nél nagyobb alak megfelelő, 169a=(13a)2.

12.4.0.9 A 4.3.6 b) mego.

Itt is szükséges az a>9 feltétel a megadott szám értelmezéséhez.Ilyen a számokra

( a + 3 ) 2 = a 2 + 6 a + 9 < a 2 + 9 a + 6 = 196 a < a 2 + 10 a + 25 = ( a + 5 ) 2 ,

tehát 196a csak 14a négyzete lehet. Az a2+9a+6=(a+4)2 egyenletből a=10 adódik, ez az egyetlen megoldás.

12.4.0.10 A 4.3.6 c) mego.

Most az a>5, a,bN feltétel mellett kell megoldanunk a

2 a 2 + 2 a + 5 = b 2

diofantikus egyenletet. Kettővel való szorzás és teljes négyzetté alakítás után kapjuk, hogy

( 2 a + 1 ) 2 + 9 = 2 b 2 .

Négyzetszám hármas maradéka 0 vagy 1, így (129) csak akkor teljesülhet, ha 2a+1 és b is osztható hárommal. Legyen tehát A=2a+13, B=b3, ahol tehát A és B is pozitív számok és A>3. Egyenletünk klasszikus Pell egyenlet (lásd a 3.8.1, 6.3.22 feladatokat):

A 2 + 1 = 2 B 2 .

Ennek végtelen sok megoldása van. Az első néhány:

46. táblázat

Ha az A>3, B>0 egész számok kielégítik a (130) egyenletet, akkor A feltétlenül páratlan, így az a=3A-12, b=3B számok pozitív egészek, sőt a>5 és ezek a számok kielégítik a (128) egyenletet is, tehát az ilyen a alapú számrendszerben 225¯a négyzetszám, a b egész szám négyzete. A fenti táblázatban A=1-hez nem tartozik megfelelő számrendszer alap, a többinek rendre a 10-es, 61-es, 358-as alapú számrendszerek felelnek meg.

A 4.3.7 feladat megoldásai

12.4.0.11 A 4.3.7 a) fel. I. megoldása

Ha a számrendszer alapszáma legalább 7, akkor

47. táblázat

tehát a szám pontosan akkor egész, ha 1=0,6666, azaz ha az alapszám 7.

Ötös számrenszerben az egyes szorzások jók, de 4+2+1=125, így az összeg 1122,2222, ami nem egész.

Négyes számrendszerben:

48. táblázat

azaz az eredmény 11133,33334=112004=35210.

Míg hármas számrendszerben:

49. táblázat

azaz az eredmény 20022,22223=201003=17110. Háromnál kisebb alap a 2-es jegy előfordulása miatt ne mjön szóba. Tehát a 3, 4, 7 alapú számrendszerek a megfelelőek.

12.4.0.12 A 4.3.7 a) fel. II. megoldása

Ha a számrendszer alapszáma a>2, akkor x=2222a=2a3+2a2+2a+2=2a4-1a-1, míg ha

y = 0 , 201020102010 a a 4 y = 2010 , 201020102010 a ,

akkor

( a 4 - 1 ) y = 2010 a ,

azaz y=2a3+aa4-1. A vizsgált szorzat:

x y = 2 a 4 - 1 a - 1 2 a 3 + a a 4 - 1 = 2 2 a 3 + a a - 1 .

Mivel 2a3+a=(a-1)(2a2+2a+3)+3, így

x y = 2 ( 2 a 2 + 2 a + 3 ) + 6 a - 1 ,

ami pontosan akkor egész, ha (a-1) a 6 osztója, azaz a{2,3,4,7}. Ezekből a 2-nél nagyobb értékek a megfelelőek.

12.4.0.13 A 4.3.7 b) mego.

Minden olyan alapnál egyenlő a két kifejezés, ahol értelmesek, hiszen ez nem más, mint az

( 2 a 3 + a ) 2 a - 1 = 2 a 4 - 1 a - 1 2 a 3 + a a 4 - 1

azonosság.

A 4.3.8 feladat megoldásai

12.4.0.14 A 4.3.8 fel. I. megoldása

(Elölről)

A faktoriálisok:

50. táblázat

A 7! már túl sok. Választunk két 6!-t, marad 2010-1440=570. Ehhez választunk négy 5!-t

2010 = 243300 ! = 2 6 ! + 4 5 ! + 3 4 ! + 3 3 ! + 0 2 ! + 0 1 ! .

Érdemes elgondolkodni rajta, hogy miért egyértelmű a megoldás.

12.4.0.15 A 4.3.8 fel. II. megoldása

(Hátulról)

Az

1 , 2 , 3 2 , 4 3 2 , 5 4 3 2 ,

helyiértékek közül az első kivételével mind osztható 2-vel, így a paritást az 1! helyiérték jegye dönti el. Mivel 2010 páros, így az 1!-os helyiérték jegye 0. Osszuk le a számot és a helyiértékeket is 2-vel! Most már az 1005-öt kell felbontanunk a

1 , 3 , 4 3 , 5 4 3 ,

helyiértékekre. Ezek közül az első kivételével mindegyik osztható 3-mal

51. táblázat

Tehát 2010=243300!

12.4.0.16 Megjegyzések a 4.3.8 feladathoz

I. A faktoriális számrendszerben fel lehet tüntetni egy 0-adik helyiértéket, a 0!=1-nek megfelelőt, azonban az ehhez tartozó jegy csak a 0 lehet, tehát kizárólag díszitésnek való ez a további helyiérték és kötelezően 0 számjegy.

II. A faktoriális számrendszer minden n pozitív egész esetén kölcsönösen egyértelmű megfeleltetést ad az n elem összes permutációjából álló Sn halmaz és az Nn!-1={0,1,2,,n!-1} halmaz között. Ezt a megfeleltetést Lehmer leképezésnek nevezik, alább 2010 példáján mutatjuk be.

Példánkban n=7. A hat jeggyel lekódolható legnagyobb szám a faktoriális számrendszerben a

6 6 ! + 5 5 ! + 4 4 ! + 3 3 ! + 2 2 ! + 1 1 ! = 7 ! - 1 ,

tehát a

0 10 = 000000 ! , 1 10 = 000001 ! , 7 ! - 1 = 5039 10 = 654321 ! ,

számok épp annyian vannak, mint a {0,1,2,3,4,5,6} számok permutációi.

A számokat faktoriális számrendszerben képzeljük el, míg a π permutációt a

[ π ( 0 ) , π ( 1 ) , π ( 2 ) , π ( 3 ) , π ( 4 ) , π ( 5 ) , π ( 6 ) ]

alakban adjuk meg. Például a [1,0,5,4,3,2,6] permutáció az alábbi értéktáblázattal megadott függvény:

52. táblázat

A 201010 szám faktoriális számrendszerbeli alakja 243300!. A hozzá tartozó permutáció megkereséséhez ennek kiolvasását balról kezdjük és jobbra haladunk. A szám legelső jegye a 2, így a permutáció legelső eleme is a 2 lesz.

243300 ! [ 2 , ? , ? , ? , ? , ? , ? ] .

A megmaradt faktoriális szám a 43300!, a permutációban még ki nem osztott elemek a {0,1,3,4,5,6}. A szám balról első jegye a 4, az a megmaradt elemek listájában (mindent 0-tól számítunk) a növekedési sorban az 5-nek felel meg:

243300 ! [ 2 , 5 , ? , ? , ? , ? , ? ] .

Most a 3300! szám és a {0,1,3,4,6} elemek maradtak meg. A következő lépésben:

243300 ! [ 2 , 5 , 4 , ? , ? , ? , ? ] ,

megmarad 300! és {0,1,3,6}, így

243300 ! [ 2 , 5 , 4 , 6 , ? , ? , ? ] ,

marad 00! és {0,1,3},

243300 ! [ 2 , 5 , 4 , 6 , 0 , ? , ? ] ,

marad 0! és {1,3},

243300 ! [ 2 , 5 , 4 , 6 , 0 , 1 , ? ] ,

marad semmi és {3},

243300 ! [ 2 , 5 , 4 , 6 , 0 , 1 , 3 ] .

Határozzuk meg az [1,0,5,4,3,2,6] permutációnak a Lehmer kód szerint megfelelő szám faktoriális alakját!

Problémák a 4.3.8 feladattal kapcsolatban

1. Miért létezik és egyértelmű a (10) alakú felírás minden pozitív egész számra?

2. Nem egész számok faktoriális számrendszerbeli alakja hogy értelmezhető?

3. Mutassuk meg, hogy bármely permutáció Lehmer kódjában a jegyek összege megegyezik a legkevesebb elemi transzpozíció számával, amellyel a permutáció előállítható. Elemi transzpozíción szomszédos elemek cseréjét értjük.

A 4.3.9 feladat megoldása

a) Vegyük a 2<3<5<7<11 prímeket. Egyszerű számolás mutatja, hogy az I1=[7,20] intervallum egészei előállnak mint ezen prímekből alkotott összegek és ahol egy prímet legfeljebb egyszer használunk. Adjuk hozzá I1 egészeihez a q1=13-at! Ekkor egyrészt a kapott összegekben minden prím legfeljebb egyszer szerepel (13 eddig nem szerepelt), másrészt az így előálló számok a [20,33] intervallum egészei. Ebből adódóan az I2=[7,33] egészei előállnak a kívánt módon. Adjuk hozzá I2 egészeihez a q2=17-et! Ezen összegben megint csak különböző összeadandók szerepelnek és lefedik a [7+17,33+17] egész pontjait, ezért tehát a [7,50] intervallum egészei előállnak a kívánt módon. Tekintsük a q2=13<q3=17<q4=19 egymást követő prímek sorozatát. Az előbbi eljárás akkor működik általánosan is, ha az Ik=[7,nk] intervallum egészeihez (amelynek előállításában csak a qk-nál kisebb prímek szerepelhettek) hozzadva a qk prímet a [7+qk,nk+qk]:=[7+qk,nk+1] egészeit kapjuk és nyilván akkor fedtük le az összes egészt az Ik+1=[7,nk+qk] intervallumban, ha bármely k-ra teljesül, hogy

7 + q k n k .

Mint láttuk, ez k=1 esetén igaz. Mindkét oldalhoz qk-t hozzáadva és használva a Bertrand posztulátumot, miszerint qk+12qk, azt kapjuk, hogy

7 + q k + 1 7 + 2 q k n k + q k = n k + 1 .

Teljes indukciót használva igazoltuk tehát, hogy minden hatnál nagyobb egész szám különböző prímek összegeként előállítható.

b) A bizonyítás alapgondolata azonos az a) bizonyítással.

12.5 Maradékok feladatok megoldása

A 4.4.1 feladat megoldása

Eladás előtt összesen 94 tojás volt a kosarakban. Egy kosár eladása után a megmaradt tojások összlétszáma 3-mal osztható kell, hogy legyen. Ez csak akkor teljesül, ha a 13 vagy a 19 tojást tartalmazó kosárból adja el a tojásokat. Az első esetben a megmaradt tojások száma 81, így 27 kacsatojásnak (és 54 tyúktojásnak) kell maradnia. Ez lehetséges is a 8+19=27, 15+18+21=54 csoportosítással. A második esetben 75 tojás maradt, amiből 25 kacsatojásnak kellene lennie, de az nem rakható össze teljes kosárnyi tojásadagokból.

A 4.4.2 feladat megoldásai

12.5.0.1 A 4.4.2 a) mego.

A

0 59 , 1 59 , 2 59 , 3 59 , , 999 59

mind különböző maradékot adnak 1000-rel osztva. Valóban, ha közülük kettő, mondjuk n59 és m59 (0n<m<1000) ugyanazt a maradékot adná, akkor különbségük, (m-n)59 osztható lenne 1000-rel, ami lehetetlen, mert (59,1000)=1 és 0<(m-n)<1000. A fenti 1000 szám 1000 különböző maradékot ad, tehát kiadja az összes maradékot. a 111-et is.

12.5.0.2 A 4.4.2 b) fel. I. megoldása

Ahhoz, hogy x-szel szorozva az 59-et, a szorzat 1-re végződjön, 9-re végződő számmal kell szoroznunk. Az írásbeli szorzás eljárását követve megkaphatjuk x további számjegyeit, melyből x=629.

12.5.0.3 A 4.4.2 b) fel. II. megoldása

Alkalmazzuk az Euklideszi algoritmust 1000 és 59 legnagyobb közös osztójának meghatározására! Ismeretes, hogy az algoritmus elő is állítja a legnagyobb közös osztót a két szám egész kombinációjaként, így lehetőséget ad a legnagyobb közös osztó bármely többszörösének ilyetén előállítására is.

1000 = 16 59 + 56 , 56 = 1000 - 16 59 , 59 = 1 56 + 3 , 3 = 59 - 1 56 = 17 59 - 1000 .

Az Euklideszi algoritmus nincs kész, de megállhatunk, mert 373=111, így 111=37(1759-1000)=62959-37000. Mivel az 59 ezer egymást követő többszöröse mind különböző maradékot ad (mod1000), így a 629-szeres a legkisebb olyan pozitív többszörös, ami 111re végződik.

A 4.4.3 feladat megoldása

Ha q a p szám fordítottja, akkor a p0q¯, p1q¯, p2q¯, p6q¯ számok között mind palindrom számok és van köztük héttel osztható, hiszen hetes maradékuk páronként különböző.

A 4.4.4 feladat megoldása

A köbre emelés megtartja a paritást, azaz páros számok köbe páros, páratlanoké páratlan. Azaz a köbeik összege is osztható 2-vel. Egy szám 0,1 vagy 2 maradékot ad 3-mal osztva. Köbeik 0,1 vagy 82 maradékokat adnak rendre. Azaz, ha az eredeti összegben a maradékok összege 0 volt, akkor a köbeinek az összegében is 0 lesz a maradék. A köbeik összege tehát osztható lesz 23=6-tal.

A 4.4.5 feladat megoldása

A négyzetszámok 3-as maradéka 0 vagy 1, míg 2010-nek a 3-as maradéka 0. Ha egy négyzetszám 3-as maradéka 0, akkor az a négyzetszám 9-cel is osztható. Ezért 2010 nem négyzetszám és két négyzetszám összegeként sem állítható elő. Három négyzetszámból csak úgy állítható elő, ha mind a három 1 maradékot ad 3-mal osztva.

A számok paritását is figyelembe véve (a 8-as maradék miatt két páratlan és egy páros szám kell) gyorsítható a keresés. Egy megoldás:

2010 = 16 2 + 23 2 + 35 2 .

12.5.0.4 Megjegyzések a 4.4.5 feladathoz

Két kérdés is felmerül.

I. Lehetséges-e, hogy egy egész szám kétféleképpen (többféleképpen) is felírható legkevesebb darab négyzetszám összegére?

II. Van-e olyan n pozitív egész korlát, hogy legfeljebb n négyzetszám összegére már minden pozitív egész felírható?

Az I. kérdésre a válasz: igen. Az alábbi táblázat tartalmazza a 2010 összes előállítását három négyzet összegére. Bármelyik oszlopban a három szám négyzetösszege 2010.

53. táblázat

A II. kérdésre is igen a válasz. Bármely pozitív egész előáll legfeljebb négy négyzetszám összegeként.

A 4.4.6 feladat megoldásai

12.5.0.5 A 4.4.6 fel. I. megoldása

Ha x prím, akkor 24-hez relatív prím, kivéve, ha x=2 vagy x=3. Tehát a prímszámok 24-es maradékai a 24-hez relatív prím maradékok valamint a 2 és a 3. Alább felsoroljuk ezeket a maradékokat és négyzetük 24-es maradékát is.

54. táblázat

Ennek alapján x2-124-es maradéka 0, 3 vagy 8, tehát {x2-124} értékei 0, 18 és 13.

12.5.0.6 A 4.4.6 fel. II. megoldása

Tekintük az x2-1 kifejezés (x-1)(x+1) szorzat alakját.

Ha x nem páros szám, akkor szomszédai az (x-1), (x+1) számok párosak, sőt, ezek egymást követő páros számok, így egyikük 4-gyel is osztható. Ebben az esetben tehát x2-1 osztható 8-cal.

Mivel x-1, x és x+1 három egymást követő egész szám, így egyikük osztható hárommal. Ha x nem osztható hárommal, akkor x-1 vagy x+1 osztható hárommal, így x2-1 osztható 3-mal.

Azt kaptuk, hogy ha x nem páros és hárommal sem osztható, akkor x2-1 osztható nyolccal és hárommal is, tehát 24-gyel is. A prímek közül így csak a 2-t és a 3-at kell még figyelembe vennünk, kapjuk, hogy az x{x2-124} függvény értékkészlete a {0,18,13} három elemből álló halmaz.

Segítség a 4.4.7 feladathoz

Koncentráljunk az ismeretlenek paritására! Milyen maradékot ad néggyel osztva egy pártalan szám négyzete? Alkalmazzuk következtetéseinket rekurzív módon!

A 4.4.8 feladat megoldása

Nem lehet mind a három prímszám páratlan. Mind a három nem lehet a 2, mert 416+3=45 nem prím. Tehát csak az egyik, mondjuk p=2. Tehát keressük q-t és r-et, melyre q4+r4+13 prím.

Tegyük fel, hogy q és r egyike sem a 3. Ekkor a negyedik hatványuk 1-et ad maradékul 3-mal osztva, és így q4+r4+13>3 osztható 3-mal ami ellentmond annak, hogy ez a szám prím. Tehát q és r valamelyike 3. Ha q és r egyike sem az 5, akkor a negyedik hatványuk 1-et ad maradékul 5-tel osztva, ám q4+r4+13>5 osztható 5-tel, ami megint csak ellentmond annak, hogy ez a szám prím. Tehát q és r valamelyike az 5.

Összefoglalva {p,q,r}={2,3,5} és a pozitív prímek között ez az egyetlen megoldás.

A 4.4.9 feladat megoldása

Tehát bizonyítanunk kell, hogy ha 9|a2+b2+c2+d2a,b,c,dZ, akkor 9|a2b2c2d2, más szóval az a,b,c,d egészek között van 3-mal osztható. Egy szám 9-cel osztva 0,1,4,7 maradékot ad. Ha az a2,b2,c2,d2 közül egy sem adna 0 maradékot, akkor 1x+4y+7z0(mod9);x+y+z=4;x,y,zN kongruenciának kellene megoldhatónak lennie, aminek könnyen láthatóan nincs megoldása.

A 4.4.10 feladat megoldása

Nyilván d1=1. Ha d22, akkor n páratlan, így d2, d3 és d4 is páratlan, tehát négyzetösszegük, ami n, páros. Az ellentmondás mutatja, hogy d2=2 és n páros.

Mivel d12+d22=5 páratlan, így d32+d42 is páratlan, tehát d3 és d4 egyike páros, a másik páratlan. Mivel páros szám négyzete osztható néggyel, páratlan szám négyzetének négyes maradéka 1, így d12+d22+d32+d42 nem osztható néggyel.

Ebből következik, hogy d3=p páratlan prím és d4=2p, azaz n=5+5p2. Látható, hogy 5|n, láttuk, hogy 4/|n, így a d3 és d4 egyike 5, azaz d3=5 és d4=10. Erre n=130, melynek osztói: 1, 2, 5, 10, 13, 26, 65, 130, tehát valóban teljesül rá az előírt összefüggés.

Segítség a 4.4.11 feladathoz

Legyen x=XZ, y=YZ és térjünk át az 5X2+3Y2=Z2 diofantikus egyenletre. Vizsgáljuk ezt mod 3.

A 4.4.12 feladat megoldása

A megadott

5 x 2 - 14 y 2 = 11 z 2

egyenlet együtthatóiról az 5-ös 11-es, 7-es maradékok használatára gondolhatunk. Végül az utóbbi vezet célhoz. A megadott összefüggés (mod7):

5 x 2 ( 2 z ) 3 .

A jobb oldalon a mod 7 kvadratikus maradékok szerepelhetnek, tehát a 0-n kívül az 1, 2 és a 4. A bal oldalon ezek ötszörösei, tehát a 0, valamint az 3, a 3 és a 6. A (132) kongruencia egyetlen megoldása: xz0(mod7), azaz (131)-ben x=7x1, z=7z1, ahol x1 és z1 is egészek. A (131) egyenletet átírhatjuk:

5 7 2 x 1 2 - 14 y 2 = 11 7 2 z 1 2 ,

azaz

5 7 x 2 - 2 y 2 = 11 7 z 2 .

Mivel (133)-ben 7|57x2 és 7|11z2, így z|2y2, azaz valamely egész y1 számmal y=7y1. Ezt (133)-be írva majd egyszerűsítve 7-tel a

5 x 1 2 - 14 y 1 2 = 11 z 1 2

egyenlethez jutunk, azaz visszajutottunk az eredeti (131) egyenlethez. Az eljárást akármeddig folytathatjuk, (131) megoldásainak olyan (x,y,z), (x1,y1,z1), (x2,y2,z2), sorozatához jutunk, amelyben mindegyik számhármast az előző számhármas számainak egyhetedeiből áll. A 0-tól különböző egész számokat azonban nem lehet akárhányszor héttel osztani úgy, hogy a hányados is mindig egész legyen. Tehát csak x=y=z=0 lehet megoldás, ami tényleg az is.

A 4.4.13 feladat megoldásai

12.5.0.7 A 4.4.13 fel. I. megoldása

Ha a x2+xy+y2 kifejezés értéke 0-ra végződik, akkor a

( x - y ) ( x 2 + x y + y 2 ) = x 3 - y 3

kifejezés értéke is 0-ra végződik. Vegyük sorra a számok 10 lehetséges végződését és köbük 10 lehetséges végződését.

55. táblázat

Látható, hogy különböző 10-es maradékú (végződésű) köbének is különböző a 10-es maradéka (végződése). Így a kifejezés 10-es maradéka csak akkor lehet 0, ha az x és az y szám 10-es maradékai megegyeznek. Azaz 10-es maradék szempontjából (x2+xy+y2) helyett elég a 3x2 kifejezést vizsgálni. Ez azonban csak akkor osztható 10-zel, ha x-is osztható vele, akkor viszont 3x2 már 100-zal is osztható, két 0-ra végződik.

12.5.0.8 A 4.4.13 fel. II. megoldása

Egy szám pontosan akkor osztható 10-zel, ha 2-vel és 5-tel is osztható. Ezért külön vizsgáljuk a 2-vel és 5-tel való oszthatóság esetét.

x és y kettes maradéka összesen négyféle lehet. A négyféle esetet egy 2×2-es táblázatba gyűjthetjük össze. A első sorban x kettes maradéka 0, a másodikban 1, az első oszlopban y kettes maradéka 0, a másodikban 1. A táblázat mezőibe beírtuk, hogy mennyi lesz az x2+xy+y2 kifejezés kettes maradéka.

56. táblázat

Látható, hogy a vizsgált kifejezés akkor és csakis akkor osztható 2-vel, ha x és y is osztható 2-vel, ekkor viszont x2+xy+y2 nyilvánvalóan osztható 4-gyel.

x és y ötös maradéka összesen huszonötféle lehet. Az eseteket most egy 5×5-es táblázatba gyűjthetjük össze. Az egyes sorokban x ötös maradéka állandó: az első sorban 0, a másodikban 1 stb. Az egyes oszlopokban y ötös maradéka konstans, az elsőben 0, a másodikban 1, stb. A táblázat mezőiben itt is az x2+xy+y2 kifejezés ötös maradéka szerepel.

57. táblázat

A kifejezés csak akkor osztható 5-tel, ha x és y is osztható 5-tel. Ilyenkor természetesen x2+xy+y2 25-tel is osztható.

A vizsgált kifejezés 4-gyel és 25-tel is osztható, ezért 100-zal is.

12.5.0.9 Megjegyzés

A táblázatról előre tudható, hogy szimmetrikus (x és y felcserélhető a kifejezésben, értéke közben nem változik). Így nem 25, hanem csak 15 mezőt kell kitölteni.

12.5.0.10 A 4.4.13 fel. III. megoldása

Ha x nem osztható a p prímmel, akkor van inverze mod p, azaz olyan c egész szám, amelyre

c x 1 ( mod p ) .

Vizsgáljuk a

x 2 + x y + y 2 0 ( mod p )

kongruenciát. Szorozzuk meg c-vel!

( c x ) 2 + ( c x ) ( c y ) + ( c y ) 2 0 ( mod p ) ,

azaz

1 2 + c y + ( c y ) 2 0 ( mod p ) ,

ami a cy=y jelöléssel így írható:

1 + y + y 2 0 ( mod p ) .

Jelölje q az 1/2 számot (tehát az 2t1(modp) kongruencia megoldását). Ez p=2 esetén nem létezik, akkor mást kell csinálni, de p>2-re már van ilyen q. Így elvégezhető a teljes négyzetté alakítás:

( y + q ) 2 q 2 - 1 ( mod p ) .

Pontosan akkor találunk megfelelő y maradékot, ha q2-1 kvadratikus maradék mod p. A p=5 esetben 12=3, hiszen 321(mod5). Mivel 3 nem kvadratikus maradék mod 5, így a (137, 136) kongruenciáknak p=5 esetén nincs megoldása, míg a (136) kongruenciának p=5-re csak xy0(mod5) a megoldása.

Könnyű ellenőrizni, hogy (135)-nek p=2 esetén is csak a xy0(mod2) a megoldása, ami igazolja a feladat állítását.

12.5.0.11 Megjegyzés a 4.4.13 feladat III. megoldásához

A fenti megoldásból kiderül, hogy ha p prím, de p2, akkor a

a x 2 + b x + c 0 ( mod p ) .

kongruencia (a=b=0 kizárva) megoldhatóságának szükséges és elégséges feltétele az, hogy a D=b2-4ac diszkrimináns kvadratikus maradék legyen mod p.

A 4.4.14 feladat megoldása

a) A számok hárommal osztva 0,1,2 maradékot adhatnak. Ha valamely maradékból az adott öt szám közül három is azonos, akkor ezek összege nyilván 3-mal osztható. Ha egy r maradék az öt szám maradékai között legfeljebb csak kétszer szerepel, akkor viszont mind a három maradék előfordul. Ekkor válasszunk ki egyet-egyet ezek közül. Ezek összege a 0+1+2 maradékot adja, azaz az összeg hárommal osztható.

b) A válasz nem: legyen n-1 szám osztható n-nel, n-1 szám pedig adjon 1 maradékot. Könnyű látni hogy ezen 2n-2 szám közül nem választható ki n melyek összege n-nel osztható.

12.5.0.12 Megjegyzés a 4.4.14 feladathoz

Az a) és b) feladat speciális esete az Erdős-Ginzburg-Zív tételnek, mely azt mondja ki, hogy 2n-1 egész közül ki lehet választani n-et, melyeknek összege osztható n-nel és az állítás éles. Az olvasó megpróbálkozhat ennek a (nem egészen könnyű) állításnak a bizonyításával is.

A 4.4.15 feladat megoldása

Legyen p prímszám és jelölje G={x1=0,x2,,xk} a nullával kiegészített négyzetes maradékok halmazát. Itt k=p-12+1=p+12.

Jelölje x-G:={x-xi:xiG} halmazt, ahol x egy tetszőleges p-vel vett osztási maradék. A szita-formula legegyszerűbb formájából

| G ( x - G ) | = | G | + | x - G | - | G ( x - G ) | | G | + | x - G | - p = p + 1 2 + p + 1 2 - p = 1 ,

azaz bármely x-re G-nek és x-G halmaznak van közös eleme. Tehát van olyan i,j, hogy xi=x-xj, azaz x=xi+xj.

12.6 Egy kis algebrával feladatok megoldása

A 4.5.1 feladat megoldása

Ha a 3 jegyű szám abc, akkor a 6 jegyű abcabc=1000abc+abc=1001abc, és 1001=71113.

A 4.5.2 feladat megoldása

A végeredmény csak 0, 198 vagy 1089 lehet.

Ha egy 3 jegyű számból kivonjuk a fordítottját, vagy 0-t kapunk (ha első és utolsó számjegye megegyezett), vagy 99-et (ha az első és utolsó jegyének különbsége 1 volt), vagy egy olyan háromjegyű számot, melynek középső számjegye 9-es és a két szélső jegyének összege is 9.

A 4.5.3 feladat megoldása

Az ötjegyű szám: n=104a+103b+102c+10d+e.

Ha n utolsó számjegyét a szám végéről az elejére tesszük, a k=104e+103a+102b+10c+d számot kapjuk.

Ekkor 10k-n=105e+104a+103b+102c+10d-(104a+103b+102c+10d+e)=100000e-e=99999e

Mivel 10k és n különbsége (99999=271369) osztható 271-gyel, 10k és n ugyanazt a maradékot adja 271-gyel osztva. Vagyis, ha n osztható 271-gyel, akkor 10k is, és mivel 10 és 271 relatív prímek így k is osztható 271-gyel. Ha pedig k osztható 271-gyel akkor 10k is, így n is.

Ha nem egyetlen számjegyet teszünk át a szám végéről az elejére, akkor ez több lépésben számjegyenként elvégezhető, ahol minden lépésben öröklődik a 271-gyel való oszthatóság.

A 4.5.4 feladat megoldásai

A 4.5.4 fel. I. megoldása

Ha egy 6-ra végződő számot 4-gyel szorzunk, a szorzat 4-re végződik, ezért az eredeti szám ötödik (utolsó előtti) számjegye 4-es. Ha egy 46-ra végződő számot 4-gyel szorzunk, akkor a szorzat utolsó előtti számjegye 8, így az eredeti szám negyedik számjegye 8. Így haladva tovább számjegyről számjegyre megkapjuk az eredeti számot: 153846.

12.6.0.1 A 4.5.4 fel. II. megoldása

Ha a jelöli a hatjegyű szám (balról) első öt jegyéből álló ötjegyű számot, akkor az eredeti szám 10a+6, a hatos áttételével kapott szám pedig 6105+a, tehát az egyenlet

6 10 5 + a = 40 a + 24 .

Ebből

a = 6 10 5 - 24 39 = 2 ( 10 5 - 4 ) 13 = 2 99996 13 = 15 384 ,

azaz az eredeti hatjegyű szám 153846.

12.6.0.2 Megjegyzés a 4.5.4 feladathoz

A téma a 4.10.2 feladatban folytatódik.

A 4.5.5 feladat megoldásai

12.6.0.3 A 4.5.5 fel. I. megoldása

Az első néhány n értéket kipróbálva világossá válik, hogy a 120-szal való oszthatóságot kell igazolni. Ezt a modulo 3, 5, 8 vizsgálatokkal végezzük el:

58. táblázat

59. táblázat

60. táblázat

Az n5-5n3+4n kifejezés értéke tehát modulo 3, 5 és 8 is zérus minden n-re, tehát mivel 3, 5 és 8 páronként relatív prímek a kifejezés értéke minden egész n-re osztható 358=120-szal. n=3-ra épp ennyit kapunk, tehát erősebb állítás nem fogalmazható meg.

12.6.0.4 A 4.5.5 fel. II. megoldása

Vegyük észre, hogy

n 5 - 5 n 3 + 4 n = n ( n 4 - 5 n 2 + 4 ) = n ( n 2 - 4 ) ( n 2 - 1 ) = n ( n - 2 ) ( n + 2 ) ( n - 1 ) ( n + 1 ) =

= ( n - 2 ) ( n - 1 ) n ( n + 1 ) ( n + 2 ) ,

azaz a vizsgált kifejezés öt egymást követő egész szám szorzata. Ennek értéke n=3 esetén 5!=120, tehát nincs olyan 120-nál nagyobb szám, amivel a kifejezés minden pozitív egész n-re osztható.

Állítjuk viszont, hogy a kifejezés minden n-re osztható 120=2335-tel. Valóban az öt egymást követő szám között biztosan van 3-mal és 5-tel osztható is, sőt két páros is, amelyek közül az egyik néggyel s osztható, így a 35222-nel való oszthatóság biztosítva van.

A 4.5.6 feladat megoldásai

12.6.0.5 A 4.5.6 a) fel. I. megoldása

a) n egymást követő egész szám összege megfelelő a egésszel

( a + 1 ) + ( a + 2 ) + + ( a + n ) = n a + n ( n + 1 ) 2

alakban írható. Mivel n|na és mivel az n, (n+1) számok relatív prímek, így az összeg pontosan akkor osztható n-nel, ha n páratlan (és így n+1 a páros).

12.6.0.6 A 4.5.6 a) fel. II. megoldása

Az összeg n-ed része az egymást követő számok átlaga, ennek kell egésznek lennie. Páratlan számnál az átlag épp a középső szám, tehát egész, páros darab egymást követő számnál pedig a két középső átlaga, tehát nem egész.

12.6.0.7 A 4.5.6 b) mego.

Az (a+1)2+(a+2)2++(a+n)2 összegben (aZ) elvégezve a négyzetre emeléseket azt kapjuk, hogy

n a 2 + ( 2 a + 4 a + 6 a + + 2 n a ) + 1 2 + 2 2 + 3 2 + n 2 = n a 2 + n a ( n + 1 ) + n ( n + 1 ) ( 2 n + 1 ) 6 .

A fenti összeg első két tagja nyilván bármely a esetén osztható n-nel. Az n, n+1, 2n+1 tényezők páronként relatív prímek, így a n(n+1)(2n+1)6 egész szám pontosan osztható 6-tal, ha n relatív prím a 6-hoz.

A 4.5.7 feladat megoldása

Számoljunk az ab¯=10a+b, ba¯=10b+a számok összegével és különbségével! Feltehető, hogy itt b<a. Ekkor

( a - b ) ( a + b ) = a 2 - b 2 | ( 10 a + b ) + ( 10 b + a ) = 11 ( a + b ) , azaz (a-b)|11, tehát a-b=1. (a-b)(a+b)=a2-b2|(10a+b)-(10b+a)=9(a-b), azaz (a+b)|9, tehát a+b=3 vagy 9.

Mindezekből az ab¯=21 és az ab¯=54 számok adódnak, mindkettő jó is.

12.7 Diofantikus egyenletek feladatok megoldása

A 4.6.1 feladat megoldásai

12.7.0.1 A 4.6.1 fel. I. megoldása

Vegyük észre, hogy n2+4n-5=(n-1)(n+5). Az (n-1), (n+5) tényezők különbsége 6, a szorzata pedig négyzetszám, k2. A két szám legnagyobb közös osztója a továbbiakban d osztja a két szám különbségét is, azaz d értéke 1, 2, 3 vagy 6.

Az n-1d, n+5d számok szorzata is négyzetszám, jelesül k2d2=(kd)2, de ők már relatív prímek, így maguk is négyzetszámok, olyan négyzetszámok, melyek különbsége 6d.

A legkisebb négyzetszámok: 0, 1, 4, 9. Az ennél nagyobb négyzetek közül már a szomszédosak különbsége is nagyobb 6-nál, pl 16-9=7. Vegyük sorra d lehetséges értékei alapján az eseteket!

d = 1 : nem lehet, nincs két olyan négyzetszám, melyek különbsége 6.

d = 2 : egyféleképpen lehet 4-1=62, n-12=1 és n+52=4, azaz n=3. Ez valóban jó megoldás 32+43-5=16.

d = 3 : nem lehet, nincs két olyan négyzetszám, melyek különbsége 2=63.

d = 6 : egyféleképpen lehet 1-0=66, n-16=0 és n+56=1, azaz n=1. Ez valóban jó megoldás 12+41-5=0.

Tehát n-nek két megfelelő pozitív egész értéke van, az 1 és a 3.

12.7.0.2 A 4.6.1 fel. II. megoldása

Alakítsunk teljes négyzetté!

n 2 + 4 n - 5 = ( n + 2 ) 2 - 9 ,

tehát két olyan négyzetszámot keresünk, amelyek különbsége 9, és közülük a nagyobbik lesz az (n+2)2. A négyzetszámok:

0 , 1 , 4 , 9 , 16 , 25

Tovább nem érdemes mennünk, mert 25-16=9 és a szomszédos négyzetszámok közti különbség (k+1)2-k2=2k+1, tehát szigorúan monoton nő. A fenti listában két 9-es különbség van, 25-16 és 9-0, azaz n+2=5, n=3 vagy n+2=3, tehát n=1. Ezek valóban megoldások.

12.7.0.3 A 4.6.1 fel. III. megoldása

Olyan n pozitív és k nemnegatív egész számot keresünk, amelyre

n 2 + 4 n - 5 = k 2 ,

azaz

( n + 2 ) 2 - 9 = k 2 ,

tehát

( n + 2 ) 2 - k 2 = 9 ,

vagy szorzat alakban

( n + 2 + k ) ( n + 2 - k ) = 9 .

Az (n+2+k) tényező pozitív, legalább akkora, mint a másik tényező és mind a két tényező egész, így csak két eset van:

n + 2 + k = 9 , s ( n + 2 - k ) = 1

vagy

n + 2 + k = 3 , s ( n + 2 - k ) = 3 .

Az első eset pontosan akkor teljesül, ha n=3 és k=4, míg a második pontosan akkor, ha n=1 és k=0. Tehát két megoldás van:

3 2 + 4 3 - 5 = 16 = 4 2 , 1 2 + 4 1 - 5 = 0 = 0 2 .

A 4.6.2 feladat megoldásai

12.7.0.4 A 4.6.2 fel. I. megoldása

Vegyük észre, hogy

x 2 + 19 x + 95 = ( x + 9 ) 2 + ( x + 14 ) = ( x + 10 ) 2 - ( x + 5 ) .

Így -4x esetén a vizsgált kifejezés értéke két szomszédos négyzetszám között van:

( x + 9 ) 2 < ( x + 9 ) 2 + ( x + 14 ) = x 2 + 19 x + 95 = ( x + 10 ) 2 - ( x + 5 ) < ( x + 10 ) 2 ,

és hasonló a helyzet, ha x-15:

( x + 10 ) 2 < ( x + 10 ) 2 - ( x + 5 ) = x 2 + 19 x + 95 = ( x + 9 ) 2 + ( x + 14 ) < ( x + 9 ) 2 .

Ha x=-14 vagy x=-5, akkor a kifejezés értéke négyzetszám, jelesül mindkétszer 25. A -13x-6 eseteket végignézve látjuk, hogy nem kapunk máskor négyzetszámot.

12.7.0.5 A 4.6.2 fel. II. megoldása

Tekintsük az x2+19x+95=y2 egyenletet, ahol y nemnegatív egész, x-re nézve másodfokú egyenletnek. A megoldóképletből:

x 1 , 2 = - 19 ± 19 2 - 4 ( 95 - y 2 ) 2 = - 19 ± 4 y 2 - 19 ) 2 .

Ez pontosan akkor lesz egész, ha 4y2-19 négyzetszám, hiszen, ha nem az, akkor nem is racionális az x1,2-re kapott kifejezés értéke, ha pedig négyzetszám, akkor páratlan is és x1,2-re is egész számot kapunk.

Tehát valamely D nemnegatív egésszel 4y2-19=D2, azaz (2y)2-D2=19, tehát (2y-D)(2y+D)=19. Itt (2y+D)0, így 02y-D2y+D, tehát 2y-D=1 és 2y+D=19, azaz y=5, D=9 és így x1=-5 és x2=-14.

A 4.6.3 feladat megoldása

16 ilyen számpár van, hiszen egyenletünk így is írható: (2x+1)(y+1)=2013 és 2013-nak 16 egész osztója van, mind páratlan.

A 4.6.4 feladat megoldása

Ismeretes, hogy ha az n egész szám prímtényezős alakja

n = p 1 α 1 p 2 α 2 p k α k ,

akkor pozitív osztóinak száma

d ( n ) = ( α 1 + 1 ) ( α 2 + 1 ) ( α k + 1 ) .

Így két lényegesen különböző módon lehet az osztók száma 4: I. n=p3; II. n=p1p2.

Az I. esetben az osztók összege 1+p+p2+p3, ami p=3 esetén kisebb, p=5 esetén nagyobb 108-nál és p monoton függvénye, tehát nincs ilyen megoldás.

A II. esetben az osztók összege

108 = 1 + p 1 + p 2 + p 1 p 2 = ( 1 + p 1 ) ( 1 + p 2 ) .

A 108 osztópárjaiból egy megfelelőt találunk: a 108=618 felbontáshoz az 5, 17 prímek tartoznak, tehát n=517=85 az egyetlen megoldás.

A 4.6.5 feladat megoldásai

12.7.0.6 A 4.6.5 fel. I. megoldása

Ha a téglalap oldalai a és b, akkor az ab=2(a+b) egyenlőségnek kell teljesülnie.

Ezt az egyenletet átalakítva az (a-2)(b-2)=4 egyenlethez jutunk, melynek pozitív (egész) megoldásai a (4;4), valamint (6;3) (illetve (3;6)) számpárok.

12.7.0.7 A 4.6.5 fel. II. megoldása

A téglalap sarkaiban levő mezők kétszeresen járulnak hozzá a kerülethez és egyszeresen a területhez, így a téglalap belsejében 4 rácsnégyzetnek kell lennie. Ezek vagy egy 1×4-es, vagy egy 2×2-es téglalapot alkotnak. Ezeket a lehetséges belső téglalapokat körberakva egységnégyzetekkel, kapjuk a kérdésben szereplő lehetséges téglalapok méreteit.

A 4.6.6 feladat megoldása

Ha a az egyik irányban x a másik irányban y részre vágtuk a sütit, akkor összesen xy szeletre vágtuk, amiből a belsejében (x-2)(y-2) van. Egyenletünk:

x y = 2 ( x - 2 ) ( y - 2 ) ,

azaz

x y = 2 x y - 4 x - 4 y + 8 ,

tehát

0 = x y - 4 x - 4 y + 8 .

Mivel (x-4)(y-4)=xy-4x-4y+16, így egyenletünket a

8 = x y - 4 x - 4 y + 16

alakra rendezzük, amelyben szorzattá alakíthatunk:

8 = ( x - 4 ) ( y - 4 ) .

A lehetséges egész tényezők (x és y szerepe szimmetrikus, így az osztópárokat csak egyszer soroljuk fel): 8=81 vagy 8=42, (a többi lehetséges egész tényezős szorzatban valamelyik tényező negatív) így az értelmes megoldások: x1=12 és y1=5, valamint x2=8 és y2=6. Vagyis a darabok száma vagy 60, vagy 48.

12.7.0.8 Megjegyzés a 4.6.6 fel. megoldásához

A feladat a 4.6.5 feladat II. megoldásához hasonlóan is megoldható.

előzetes megjegyzés a 4.6.7 feladathoz A törzstörtek az 1 számlálójú pozitív törtek. Az egyiptomi aritmetikában játszottak fontos szerepet. Az egyiptomi papiruszok tanulsága szerint ugyanis az akkori írnokok minden törtet különböző nevezőjű törtek segítségével írtak fel (lásd pl Sain Márton Nincs királyi út című könyvét.).

A 4.6.7 feladat megoldásai

12.7.0.9 A 4.6.7 fel. I. megoldása

(Az egyik változót tekintjük ismeretlennek)

Az

2 9 = 1 n + 1 m

egyenlet megoldásait keressük, ahol m és n pozitív egészek. Tekintsük n-et ismeretlennek, míg m-re nézzünk úgy, mint paraméterre, tehát képzeljük azt, hogy mindjárt megmondja nekünk valaki az értékét.

Átszorzás után n-re lineáris egyenletet kapunk:

2 n m = 9 m + 9 n ,

n ( 2 m - 9 ) = 9 m ,

azaz

n = 9 m 2 m - 9 .

Most lényegében polinomosztást csinálunk, de előzőleg szorzunk kettővel, hogy ne jöjjenek be törtek:

2 n = 18 m 2 m - 9 = 9 ( 2 m - 9 ) + 81 2 m - 9 = 9 + 81 2 m - 9 .

Mivel 2n és 9 egészek, így 812m-9 is az, tehát azt kaptuk, hogy 2m-9 a 81 osztója. A lehetőségek:

61. táblázat

amiből a pozitív megoldások a tagok felcserélésével kapható változatokat nem felsorolva:

2 9 = 1 9 + 1 9 = 1 6 + 1 18 = 1 5 + 1 45 .

12.7.0.10 A 4.6.7 fel. II. megoldása

(Szimmetrikus algebrai kezelés)

2 9 = 1 n + 1 m

2 m n = 9 m + 9 n

4 m n - 18 m - 18 n = 0

( 2 m - 9 ) ( 2 n - 9 ) = 81

Ennek osztópárjaira 2m-9=1,2n-9=81, stb...

12.7.0.11 A 4.6.7 fel. III. megoldása

(Becslés)

Tegyük fel, hogy mn, azaz 1n1m. Mivel az 1n, 1m törtek átlaga 19, így közülük a nagyobbik legalább 19, azaz reciproka, m értéke, legfeljebb 9.

Másrészt 1m<29, így m>92=4,5.

Ezek alapján m-re csak az 5, 6, 7, 8, 9 értékek maradtak, amelyeket gyorsan kipróbálhatunk és kapjuk a fentebb már látott megoldásokat.

A 4.6.8 feladat megoldásai

12.7.0.12 A 4.6.8 fel. I. megoldása

A szabályos n szög egy belső szöge n-2n180=180-360n-os. Pontosan akkor kerülhet egy szabályos k-szög és egy szabályos n-szög a szabályos háromszög mellé az előírt módon, ha

60 + ( 180 - 360 k ) + ( 180 - 360 n ) = 360 ,

1 k + 1 n = 1 6 .

Itt k és n közül a kisebbik legfeljebb 12, mert ha mindkettő nagyobb lenne ennél, akkor reciprokösszegük nem érné el a 112+112=16 összeget. Ez a kisebbik érték nagyobb 6-nál, tehát csak hat esetet kell megnézni. A (139) egyenlet összes pozitív egész megoldásai:

1 6 = 1 12 + 1 12 = 1 10 + 1 15 = 1 9 + 1 18 = 1 8 + 24 18 = 1 7 + 1 42 ,

így tehát öt különböző megoldás is van, ahol a szabályos sokszögek oldalszámai a fenti törtek nevezői.

12.7.0.13 A 4.6.8 fel. II. megoldása

A (139) egyenletet szorozzuk át 6nk-val!

6 ( n + k ) = n k ,

azaz

36 = n k - 6 ( n + k ) + 36 ,

tehát

36 = ( n - 6 ) ( k - 6 ) .

A 36 az alábbi módokon írható fel (-6)-nál nagyobb tényezők szorzataként:

36 = 6 6 = 4 9 = 3 12 = 2 18 = 1 36 ,

tehát öt különböző megoldás is. A szabályos sokszögeknek hattal-hattal több oldala van, mint fent a 36 osztópárjainak.

A 4.6.9 feladat megoldása

( p 2 ) ( q 2 ) = 2 ( ( p 2 ) q + ( q 2 ) p )

( p - 5 ) ( q - 5 ) = 16 , p=7, q=13 vagy fordítva. A válasz tehát 6.

A 4.6.10 feladat megoldása

Legyen a találkozón résztvevő emberek száma x, a marslakók ujjainak száma 10+a, ahol x és a természetes számok. Ekkor 20x-1=(10+a)(x+6), amiből rendezés és szorzattá alakítás után (10-a)(x+6)=121, ahol 10-a10, így 10-a=1 és x+6=121. A találkozón tehát x+(x+6)=236 résztvevő volt.

A 4.6.11 feladat megoldása

Vegyük észre, hogy

( x ( x + 3 ) ) ( ( x + 1 ) ( x + 2 ) ) = ( x 2 + 3 x ) ( x 2 + 3 x + 2 ) = ( x 2 + 3 x + 1 ) 2 - 1 .

Ezzel egyenletünk az

( x 2 + 3 x + 1 ) 2 = y 2 + y + 1

alakba írható át. Vegyük észre, hogy ha 1y, akkor

y 2 < y 2 + y + 1 < y 2 + 2 y + 1 = ( y + 1 ) 2 ,

míg y-2 esetén

( y + 1 ) 2 = y 2 + 2 y + 1 < y 2 + y + 1 < y 2 ,

tehát a két fenti esetben y2+y+1 nem lehet négyzetszám, mert két szomszédos négyzetszám közé esik. A kimaradt y{0,-1} esetek annak felelnek meg, hogy a megadott egyenlet jobb oldala zérus. Ez pontosan akkor ad megoldást, ha a bal oldal is zérus, azaz, ha x{-3,-2,-1,0}.

A 4.6.12 feladat megoldása

Vegyük észre, hogy

( x + 2 ) 4 - x 4 = ( 2 x + 2 ) 3 + 8 ( x + 1 ) = ( 2 x + 3 ) 3 - ( 24 x 2 + 22 x + 11 ) = ( 2 x + 1 ) 3 + ( x + 1 ) ( 12 x + 14 ) + 1 .

Így 0x esetén (x+2)4-x4 két szomszédos köb közé esik:

( 2 x + 2 ) 3 < ( 2 x + 2 ) 3 + 8 ( x + 1 ) = ( x + 2 ) 4 - x 4 = ( 2 x + 3 ) 3 - ( 24 x 2 + 22 x + 11 ) < ( 2 x + 3 ) 3 ,

és hasonló a helyzet x-2 esetén is:

( 2 x + 1 ) 3 < ( 2 x + 1 ) 3 + ( x + 1 ) ( 12 x + 14 ) + 1 = ( x + 2 ) 4 - x 4 = ( 2 x + 2 ) 3 + 8 ( x + 1 ) < ( 2 x + 2 ) 3 .

Így csak x=-1 esetén kaphatunk köbszámot, és valóban, x=-1, y=0 megoldás.

12.8 Számhalmazok feladatok megoldása

A 4.7.1 feladat megoldása

a) Mivel b3-hoz relatív prím, ezért {b,2b}={1,2}(mod3). A 3x+by alakú számok nyilván tartalmazzák a 3xx=0,1,2,, számtani sorozatot, a 3x+bx=0,1,2,, és a 3xx=0,1,2,, számtani sorozatokat. Mivel minden maradékot lefedtünk, ezért 2b-2-től kezdve minden szám előáll ilyen alakban.

b) Teljesen hasonló gondolattal adódik, hogy minden (a-1)(b-1)-1-nél nagyobb szám előáll ax+by,a,bN,x,y nem negatív egészek. Ezt Sylvester 1884-ben igazolta. Ha több tagú összeget nézünk, annak a küszöbszámnak az értéke, amelytől kezdve minden egész előáll, nem ismert pontosan. Ezt a kérdést pénzváltási problémának vagy Frobenius problémának is nevezik.

A 4.7.2 feladat megoldása

a) Az A+B halmazban nyilván legfeljebb annyi elem lehet, ahány összeget képeztünk, azaz |A+B|kn. Továbbá az

a 1 + b 1 < a 1 + b 2 < < a 1 + b n < a 2 + b n < < a k + b n

sorozatban minden elem különböző, ezek elemei A+B-nek és e sorozat k+n-1 elemből áll.

b) |A+B|=kn teljesül, ha minden ai+bj összeg különbözik egymástól. Ekkor az ai+bj(i,j) leképezés bijekció, és ilyen (i,j) párból kn darab van. Ez például teljesül, ha A={2<22<<2k}; és B={2k+1<2k+2<<2k+n}. (Valóban a kettes számrendszerben egy 2i+2j szám felírása egyértelmű.)

| A + B | = k + n - 1 teljesül, ha mind A, mind B egy-egy számtani sorozat, melyeknek differenciája azonos. Megmutatjuk, hogy másként nem lehet. Ehhez tekintsük a következő mátrixot (csak a jobb érthetőség kedvéért rendeztük mátrixba az összeg elemeit)

62. táblázat

E mátrixban bármely elemtől jobbra illetve a felette levő elemek nagyobbak. Közlekedjünk a bal alsó saroktól (a1+b1 elemtől) a jobb felső sarokba (ak+bn) jobbra-felfelé lépésekkel. Jegyezzük meg, hogy k+n-1 különböző elemet érintettünk tehát nem csak az a) részben feltüntetett sorozat ilyen. Közlekedjünk most úgy, hogy az utunkban az ai+bj<ai+1+bj<ai+1+bj+1 elemek legyenek. Cseréljük ki az ai+1+bj elemet az ai+bj+1 elemre. Ekkor nyilván teljesül az is, hogy ai+bj<ai+bj+1<ai+1+bj+1. Azaz az ai+bj és az ai+1+bj+1 elemek között van az ai+1+bj és az ai+bj+1 elem, és mivel mindkét esetben k+n-1 különböző összeget kaptunk, azt kapjuk, hogy ai+1+bj=ai+bj+1 teljesül minden i,j párra. Átrendezve és i-t egynek választva azt kapjuk, hogy

b j + 1 - b j = a 2 - a 1 : = d

teljesül minden j-re. Így B egy számtani sorozat. A szerepeket megcserélve kiderül, hogy A is egy ugyanakkora differenciájú számtani sorozat.

A 4.7.3 feladat megoldásai

12.8.0.1 A 4.7.3 a) mego.

A 2 hatványai: 1, 2, 4 64. (7 db)

12.8.0.2 A 4.7.3 b) mego.

50 -et ki lehet: a páros számokat. 50-nél több szám között azonban mindig lesznek szomszédos pozitív egészek, amelyek relatív prímek.

12.8.0.3 A 4.7.3 c) fel. I. megoldása

50 szám megadható, pld. az 50--99 vagy az 51--100 számok.

Ennél több nem adható meg. Alább először egy Turán Páltól származó teljes indukciós gondolatmenetet közlünk.

Állítjuk, hogy ha 2n-ig megadunk n+1 természetes számot, akkor lesz közöttük kettő, hogy az egyik osztja a másikat. Ez n=1-re triviális. Ha tudjuk, hogy ha 2n-ig megadunk n+1 természetes számot, akkor lesz közöttük kettő, hogy az egyik osztja a másikat, akkor ha 2n+2-ig adott n+2 egész és 2n+1,2n+2 közül csak az egyik tartozik a halmazunkba, akkor készen vagyunk (mivel használhatjuk az indukciós feltevést). Tehát most feltehetjük, hogy 2n+2 benne van halmazunkba. Ha n+1 is benne van halmazunkba, akkor n+1|2n+2. Ha nem, vegyük most hozzá a halmazunkhoz n+1-et! Ekkor 2n-ig n+1 számunk van, az indukciós feltevés alapján van kettő, hogy az egyik osztja a másikat. Ha ez nem a k|n+1 pár, készen vagyunk. Ha ez a k|n+1, akkor k|2n+2 is teljesül.

12.8.0.4 A 4.7.3 c) fel. II. megoldása

A A 4.7.3 I. megoldásban már láttunk példát 50 megfelelő számra. Itt csak megmutatjuk, hogy 50-nél több szám nem lehet egy ilyen halmazban. Legyen adva tehát 1a<a2<<an+1100 sorozat. Minden számot írjunk fel ai=2sibi alakba, ahol 1i100, és bi páratlan szám. Mivel 2n-ig n páratlan szám van, van olyan i<j, hogy bi=bj:=b. Ekkor azonban

a i = 2 s i b | 2 s j b = a j .

12.8.0.5 A 4.7.3 d) mego.

Páros számot csak egyet választhatunk. Hasonlóan, minden 100 alatti prím többszörösei közül csak egyet választhatunk, így maximum annyi számot választhatunk, ahány 100 alatti prím van. Maguk a prímek például megfelelnek (25 db).

A 4.7.4 feladat megoldása

Egy ilyen összetett szám felírható ab alakban, ahol 1<ab és teljesül, hogy a2ab1200. Ezért a120034,64. Azaz a 12 szám felbontásaiban a kisebbik faktor 34.34-ig a prímek sorban 2,3,5,7,11,13,17,19,23,29,31,11 darab, azaz e kisebbik faktorok között van olyan, amelyik ugyanazzal a prímmmel osztható.

12.9 Számsorozatok feladatok megoldása

A 4.8.1 feladat megoldása

a) a, a+2, a+4 közül az egyik biztos osztható 3-mal, ez csak a lehet, így az egyetlen megfelelő sorozat: 3, 5, 7.

b) Könnyen meggondolható, hogy a differenciának párosnak és 3-mal oszthatónak kell lennie. A legkisebb megfelelő sorozat az 5, 11, 17, 23, 29.

c) Valójában azt fogjuk megmutatni, hogy a differencia osztható minden 15 alatti prímszámmal, azaz 23571113=30.030-cal.

Legyen p1<p2<<p15, egy 15 tagú d differenciájú számtani sorozat, melynek tagjai prímszámok. Legyen 2p13 egy prímszám. A b) feladat miatt tudjuk, hogy d6, ezért p213.p|d; ha dp-vel vett osztási maradéka r0 lenne, akkor r,2r,,14r halmazban minden p-vel vett osztási maradék előfordulna, ami azt jelenti, hogy valamely j-re p2+jr=p2+j osztható p-vel ellentmondásként, mert csak egy p13-mal osztható prímszám van.

A 4.8.2 feladat megoldása

a) Először az fogjuk igazolni, hogy ha k<n, akkor Fk|Fn-2.

A bizonyításához mindössze azt kell észrevennünk, hogy

F k ( F k - 2 ) = ( 2 2 k + 1 ) ( 2 2 k - 1 ) = ( 2 2 k ) 2 - 1 = 2 2 k + 1 - 1 = F k + 1 - 2 .

Ezért

F k + 1 F k ( F k - 2 ) = F k + 1 ( F k + 1 - 2 ) = F k + 2 - 2 ,

innen indukcióval

F k + s F k + 1 F k ( F k - 2 ) = F k + s + 1 - 2 ,

azaz minden s>1 esetén Fk|Fk+s+1-2, ami s:=n-k-1 választással éppen az állítás.

b) Valóban ha d|Fk akkor az a.) állítás miatt d|Fn-2 is teljesül és ha d|Fn akkor d|Fn-(Fn-2)=2. Tehát a legnagyobb közös osztó d|2; a Fermat számok páratlanok, azaz d=1.

c) Mivel (Fk,Fn)=1, ezért ebből következik, hogy végtelen sok prím van, hiszen végtelen sok Fermat-számunk van és mindegyik prímtényezős felbontásában az előzőek felbontásában szereplő prímektől különböző prím szerepel.

12.9.0.1 Megjegyzés a 4.8.2 fel. megoldásához

Máig megoldatlan probléma, hogy a Fermat számok között van-e végtelen sok prímszám. Az első öt Fermat szám prím; azonban F5=225+1=6416700417.

A 4.8.3 feladat megoldása

Pontosan akkor lesz an=k, ha

( k - 1 2 ) 2 < k 2 - k + 1 n k 2 + k < ( k + 1 2 ) 2 .

Tehát épp 2k db n értékre teljesül az an=k összefüggés, ilyen n-ekre az 1an értékek összege 2. A teljes összeg 21999=3998.

A 4.8.4 feladat megoldása

Legyen az n egymást követő szám a+1, a+2, a+3, , a+n.

Ekkor (a+nn)=(a+n)!a!n!.

Ez nyilván egész szám, így a!-ral való egyszerűsítés után is egész lesz.

A 4.8.5 feladat megoldásai

12.9.0.2 A 4.8.5 a-b-c) mego.

a) 2|F3,F6, 2|Fn3|n.

b) 3|F4,F8, 3|Fn4|n.

c) 10|F15,F30, 10|Fn15|n.

Mindezt csak a c) esetben igazoljuk, a másik kettőben hasonló a gondolatmenet. Vizsgáljuk a Fibonacci sorozat elemeit modulo 10. Az elemek számolhatók az eredeti képzési szabállyal, az összeadást modulo 10 végezve.

63. táblázat

64. táblázat

Látható, hogy F150(mod10) és F167(mod10). A sorozat innentől kezdve ugyanaz, mint az elejétől, azaz F00(mod10) és F11(mod10)-től kezdve, csak minden elem meg van szorozva 7-tel pmod10. Mivel (7,10)=1, így 0-t csak akkor kaphatunk, ha az eredeti 15 indexszel visszatolt sorozatban is az volt. Tehát valóban minden tizenötödik elem lesz 10-tel osztható a Fibonacci sorozatban.

12.9.0.3 Megjegyzés a 4.8.5 a-b-c) fel. megoldásához

A fenti bizonyításban szerencsének tűnt a (7,10)=1 reláció. Teljes indukcióval könnyen igazolható, hogy a Fibonacci sorozat szomszédos tagjai relatív prímek, így két szomszédos tag bármelyike mindig relatív prím lesz a másik egy osztójához is. Tehát a fenti szerencse valójában általános törvényszerűség. Szerencsére.

12.9.0.4 A 4.8.5 d-e) mego.

k -val osztva egy szám k-féle maradékot adhat. Két egymást követő eleme a sorozatnak k2-féle (rendezett) maradékpárt adhat. Mivel a sorozat végtelen hosszú, így van olyan maradékpár, amely ismétlődik, kétszer is előfordul benne. Induljunk ki egy ilyen maradékpár kisebb indexű tagjaiból és lépegessünk visszafelé. A sorozat képzési szabálya ebben az irányban is egyértelmű és eljutunk az F0-hoz, tehát a 0 maradékhoz, egy k-val osztható számhoz. Ha az azonos maradékú nagyobbik párból indulunk ki, akkor ugyanezekkel e lépésekkel a k szám egy pozitív többszöröséhez jutunk.

Az e) állítás a c) feladatrész megoldása és az ahhoz fűzött megjegyzés alapján igazolható.

12.9.0.5 A 4.8.5 f) mego.

Először alkalmazzuk a 4.8.5 e) feladat állítását a k=F(a,b) számra. Mivel a Fibonacci sorozat legkisebb F(a,b)-vel osztható pozitív tagja nyilvánvalóan maga F(a,b) és (a,b)|a, (a,b)|b, így az e) állítás szerint F(a,b)|Fa, F(a,b)|Fb, tehát F(a,b)|(Fa,Fb).

Most alkalmazzuk a 4.8.5 d) feladat állítását az (Fa,Fb) számra! Legyen Fc a Fibonacci sorozat legkisebb (Fa,Fb)-vel osztható pozitív tagja. Mivel Fa is osztható (Fa,Fb)-vel, így a 4.8.5 e) feladat állítása szerint c|a és ehhez hasonlóan c|b, tehát c|(a,b), amiből Fc|F(a,b). Kaptuk, hogy (Fa,Fb)|F(a,b) és korábban láttuk, hogy F(a,b)|(Fa,Fb), tehát F(a,b)=(Fa,Fb), ahogy a feladat állította.

A 4.8.6 feladat megoldása

Ha n összetett, akkor xn=2n-1 is összetett; valóban, ha n=km,k,m>1 akkor 1<(2k-1)|(2k)m-1. Így, ha n=(k+1)!+1, akkor n+1,n+1,n+k mindegyike összetett. (vö. Mersenne-prímek)

A 4.8.7 feladat megoldása

Megmutatjuk, hogy minden második tagja az yk=22k+3 sorozatnak 7-tel osztható. y1=4+3,y2=16+35(mod7),y3=28+3=259=737. Teljes indukcióval igazolható, hogy y2k+10(mod7), és y2k5(mod7). (vö. Fermat-prímek)

A 4.8.8 feladat megoldása

Legyen d a számtani sorozat differenciája és legyen n>a1+(k+2)d.

Az n!+i:i=2,3,n sorozat minden eleme összetett és nyilván van olyan j, hogy n!+2ajn!+d+2. Ekkor viszont aj+sn!+ns=1,2,k, amely számok összetettek.

A 4.8.9 feladat megoldása

A számtani sorozat nyilván növekvő, és egy N-ig N-a1d-1 eleme van. Négyzetszám N, köbszám N3, ... k-adik hatvány Nk van. Ekkor persze 2kN, azaz klog2N. Így N-ig legfeljebb

N + N 3 + + N k < N log 2 N

hatványszám van. Ám ha N>2a1+2d, akkor

N log 2 N < N 2 d < N - a 1 d - 1 ,

mivel

N 2 d > log 2 N , ( * )

ha N elég nagy (pl. a LHospital szabályból következően).Ez viszont azt jelenti, hogy a számtani sorozatnak több eleme van, mint hatványszám; nem lehet mindegyik eleme hatványszám.

A teljesség kedvéért mutatunk a (*)-ra egy, a LHospital szabályt elkerülő indoklást:

Az igazolandó (*) egyenlőtlenség ekvivalens a

2 N > N 2 d

egyenlőtlenséggel.

Legyen k az a természetes szám, melyre

k 2 N < ( k + 1 ) 2 .

Így 2N2k2 és (k+1)4d>N2d. Tehát elegendő a

2 k 2 > ( k + 1 ) 4 d

becslést k>k0 esetén igazolni. 24d=1+a>1, ezért kell, hogy

( 1 + a ) k 2 > ( k + 1 ) .

Felbontva a bal oldalon levő zárójelet a k2 tényezős szorzatban ( (1+a)k2=(1+a)(1+a)(1+a)-ban ) az 1-eseket szorozzuk össze, valamint egy zárójelből a-t, a többiből az 1-eseket és további pozitív tagokat. Tehát

( 1 + a ) k 2 > 1 + k 2 a .

Ha most az

1 + k 2 a > k + 1

egyenlőtlenséget igazoljuk, készen vagyunk. Ez pedig k>1a esetén teljesül. Vagyis

k > 1 1 - 2 4 d

esetén teljesül (*).

12.10 A harmonikus sor feladatok megoldása

A 4.9.1 feladat megoldásai

12.10.0.1 A 4.9.1 a) mego.

Tekintsük az x-tengelyen az 1, 2, 3, 4, n osztópontokat (lásd a 119 ábrát). Ezek a pontok az x-tengely [1,n] zárt intervallumát (n-1) darab egységnyi hosszúságú szakaszra osztják. Emeljünk mindegyik szakaszra egy-egy téglalapot, mégpedig olyanokat, amelyek erre merőleges oldala rendre 1, 12, 13, 14,, 1n-1 hosszúságú. Mivel az x1x függvény a pozitív számok halmazán szigorúan monoton fogy, így ezek a téglalapok lefedik a görbét.

119. ábra

A téglalapok összterülete nagyobb, mint a hiperbola alatti terület:

I ( n ) < 1 1 + 1 2 + + 1 n - 1 .

Az x-tengely 1, 2, 3, 4, n osztópontjai közti intervallumokra most rendre 12, 13, 14,, 1n magasságú téglalapokat emelünk (lásd a 120. ábrát). A monotonitás miatt ezek most mind a görbe alatt lesznek, a görbe alatti terület lefedi az összes téglalapot.

120. ábra

A téglalapok összterülete kisebb, mint a hiperbola alatti terület:

1 2 + 1 3 + + 1 n < I ( n ) ,

amiből

1 1 + 1 2 + 1 3 + + 1 n < 1 + I ( n ) .

12.10.0.2 A 4.9.1 b) mego.

Tekintsünk két merőleges tengelyes affinitást. Az első tengelye legyen az x-tengely, aránya 1q, a második tengelye legyen az y-tengely, aránya pedig q. Ez a leképezés tehát az (x,y) pontot a (qx,yq) pontba képezi. Az xy=1 hiperbola képe önmaga lesz, hiszen xy=qxyq. Az egyik affinitás az alakzatok területét az 1q-szorosára, a másik a q-szorosára változtatja, így végeredményben a területet nem változtatja az összetett leképezés. Az (1,1) pont képe valóban a (q,1q) pont, ahogy a feladat kívánta. Q.E.D.

12.10.0.3 A 4.9.1 c) mego.

A b)-ben megadott leképezésnél q=b esetén a hiperbola x=1 és x=a közti ívének, illetve az alatta fekvő tartománynak a képe az x=b és x=ab közti ív, illetve tartomány. Ez utóbbi tartományhoz az x=1, x=b értékek közti tartományt hozzávéve kapjuk az x=1 és x=ab közti részt, azaz I(ab)=I(a)+I(b). Q.E.D.

12.10.0.4 A 4.9.1 d) mego.

Tekintsük az f(t)=I(et) függvényt. Ez a függvény minden t valós számra értelmezett és monoton nő, t=0 esetén értéke zérus és

f ( t 1 + t 2 ) = I ( e t 1 + t 2 ) = I ( e t 1 e t 2 ) = I ( e t 1 ) + I ( e t 2 ) = f ( t 1 ) + f ( t 2 ) .

Ha f(1)=c, akkor f(-1)=-c, hiszen 0=f(0)=f(1+(-1))=f(1)+f(-1).

Másrészt, ha f(u)=d, akkor pozitív egész n esetén

f ( n u ) = f ( u ) + f ( u ) + + f ( u ) = n f ( u ) = n d .

Ez u=1 illetve u=-1 esetén n=m-mel adja, hogy minden egész m-re f(m)=mc. Ráadásul (141)-ben u=mn-re

m c = f ( m ) = m n + m n + + m n = n f ( m n ) ,

amiből f(mn)=cmn, tehát racionális t-re f(t)=ct. A függvény monotonitásából következik, hogy f(t)=ct minden valós számra teljesül.

Mivel I(et)=f(t)=ct, így pozitív z-re I(z)=clnz. Alább megmutatjuk, hogy I(e)=1, azaz c=1.

Tekintsük az an=I((1+1n)n) sorozatot! Az I területfüggvény tulajdonsága miatt an=nI(1+1n), míg az (1+1n)n sorozat tulajdonsága és az I függvény folytonossága miatt limnan=I(e).

Becsülni szeretnénk az I(1+1n) értéket, tehát kis pozitív Δ esetén az 1x alatti területet x=1 és x=1+Δ között.

Vegyük észre, hogy az x1x függvény grafikonja pozitív x-ekre az x2-x függvény grafikonja fölött helyezkedik el (lásd a 121 ábrát)! Valóban, pozitív x-re a 2-x1x egyenlőtlenség x-szel átszorozható és a kapott 2x-x21 reláció az ismert 0(x-1)2 összefüggéssé rendezhető át.

Másrészt az 1x függvény grafikonja konvex, tehát pld x=1 és x=2 között a görbe a húr alatt helyezkedik el: 1x32-12x. Valóban átszorzás és rendezés után az (x-1)(x-2)0 relációhoz jutunk, ami épp itt teljesül.

121. ábra

A görbe alatti területet egy-egy trapéz területével alulról illetve felülről becsülhetjük:

Δ 1 + ( 1 - Δ ) 2 < I ( 1 + Δ ) < Δ 1 + ( 1 - 1 2 Δ ) 2 ,

azaz

Δ - 1 2 Δ 2 < I ( 1 + Δ ) < Δ - 1 4 Δ 2 .

Ebből Δ=1n-et írva és n-nel szorozva kapjuk, hogy

1 - 1 2 n < a n = n I ( 1 + 1 n ) < 1 - 1 4 n ,

így limnan=1.

Fentebb ugyanerre a határértékre I(e) adódott, tehát I(e)=1 és így I(z)=lnz. Q.E.D.

A 4.9.2 feladat megoldása

Az [nk] mennyiség azt mondja meg, hogy 1-től n-ig hány szám osztható k-val. A k=1n[nk] mennyiség, tehát 1-től n-ig a számok osztói számának összege, így an azt mondja meg, hogy az 1, 2, , n számoknak átlagosan hány osztója van.

a) Az első szám, amelynek két osztója van a 2. Az első, amelynek három, a 4. A számoknak akármilyen sok osztója lehet (s!-nak pld legalább s osztója van), így újra és újra lesz rekorder, azaz olyan szám, amelynek több osztója van, mint bármelyik nála kisebb pozitív egésznek. Az ilyen számok biztosan növelik az átlagot, tehát ar>ar-1, ha r rekorder.

b) Alább látható az első néhány pozitív egész, alattuk az osztóik száma:

65. táblázat

Az 1-en kívül a számoknak legalább két osztója van, és pontosan azoknak a számoknak van két osztója, amelyek prímek. Az osztók számának átlaga egytől négyig és ötig is épp 2, de egytől hatig már több, mint 2 és így az átlag már mindig több lesz 2-nél. Ebből következik, hogy minden 6-nál nagyobb p prím lefelé viszi az átlagot, azaz ap<ap-1. Mivel végtelen sok prímszám van, így végtelen sokszor csökken a sorozat.

12.10.0.5 I. megjegyzés a 4.9.2 feladathoz

Ismeretes (lásd a 4.9.1 feladatot), hogy a

H n = 1 1 + 1 2 + 1 3 + + 1 n

harmonikus sort nagyon jól közelíti a logaritmusfüggvény. Nevezetesen

ln n < H n < 1 + ln n .

Mivel nk-1<[nk]nk, így

- n + k = 1 n n k < k = 1 n [ n k ] k = 1 n n k ,

azaz

H n - 1 < a n H n ,

és így

( ln n ) - 1 < a n ( ln n ) + 1 .

A (142) összefüggésből nyilvánvaló, hogy az an sorozat végtelen sokszor nő.

12.10.0.6 II. megjegyzés a 4.9.2 feladathoz

Az eddigi eredmények alapján azt mondhatjuk, hogy az 1-től n-ig terjedő egész számoknak átlagosan kb lnn osztója van.

A 4.9.3 feladat megoldása

Azok a pozitív egészek, amelyeknek csak a 2 és a 3 a prímosztója és mindkét prímtényező legfeljebb az n-edik hatványon szerepel bennük itt láthatók:

2 0 3 0 2 1 3 0 2 2 3 0 2 n 3 0 2 0 3 1 2 1 3 1 2 2 3 1 2 n 3 1 2 0 3 2 2 1 3 2 2 2 3 2 2 n 3 2 2 0 3 n 2 1 3 n 2 2 3 n 2 n 3 n

Kellően nagy n-re ez a táblázat már tartalmazza a vizsgált véges halmaz összes elemét. Az első sor elemeinek reciprokösszege 130(2-12n), a második sor elemeié 130(2-12n), az utolsó soré 13n(2-12n). Mivel a

1 3 0 + 1 3 1 + + 1 3 n = 3 2 - 1 2 3 n ,

így a teljes összeg

( 2 - 1 2 n ) ( 3 2 - 1 2 3 n ) < 2 3 2 = 3 .

12.10.0.7 Megjegyzés a 4.9.3 feladathoz

Lásd még az Analízis fejezet 6.6.1 feladatát.

A 4.9.4 feladat megoldása

Közös nevezőre hozva

1 2 + 1 3 + + 1 10 = a 2 3 3 2 5 7 = a b .

Az a számláló a közös nevezőre hozás után 9 összeadandóból áll, az első 223257, stb. és vegyük észre, hogy két tag nem osztható 5-tel amikor az 1/5 és amikor az 1/10 törteket bővitjük. E két tag 23327 és 22327. Az első 4-et, a második 2-t ad 5-tel osztva. Így a1-et ad 5-tel való osztási maradékként.

A 4.9.5 feladat megoldásai

12.10.0.8 A 4.9.5 a) fel. I. megoldása

Hozzuk közös nevezőre a törteket

( p - 1 ) ! 1 + ( p - 1 ) ! 2 + + ( p - 1 ) ! p - 1 ( p - 1 ) ! .

Ha ez a tört egyszerűsíthető valamivel, akkor az p-nél kisebb, tehát állításunk szempontjából érdektelen. Amit tehát igazolnunk kell, az az (használva a (modp) jelölést), hogy

( p - 1 ) ! 1 + ( p - 1 ) ! 2 + + ( p - 1 ) ! p - 1 0 ( m o d p ) .

Jelölésünk korrekt, mivel 1ip-1 számra (i,p)=1, tehát oszthattunk i-vel. Hogy pontosabban értsük a fenti kongruenciát, azt is meg kell jegyeznünk, hogy bármely fenti i-re létezik i*, hogy ii*1(modp), továbbá, hogy

( p - 1 ) ! i ( p - 1 ) ! i * ( m o d p ) ,

(pl. megszorozva mindkét oldalt i-vel.) Így

( p - 1 ) ! ( 1 1 + 1 2 + + 1 p - 1 ) 0 ( m o d p )

a bizonyítandó állítás. Mivel ((p-1)!,p)=1, így amit bizonyítani kell, az az, hogy

1 1 + 1 2 + + 1 p - 1 0 ( m o d p ) .

Utolsó lépésként nem nehéz látni, hogy amint i végig fut az 1,2,,p-1 számokon, akkor 1i is ugyanezeken a számokon (más sorrenben) fut végig. Pl. p=5, akkor {11,12,13,14}={1,3,2,4}. Tehát azt kaptuk, hogy

1 1 + 1 2 + + 1 p - 1 1 + 2 + + p - 1 ( m o d p ) .

Ám

1 + 2 + + p - 1 = p ( p - 1 ) 2 ,

ami pedig nyilván osztható p-vel.

12.10.0.9 A 4.9.5 a) fel. II. megoldása

Azt kell igazolnunk, hogy

( p - 1 ) ! 1 + ( p - 1 ) ! 2 + + ( p - 1 ) ! p - 1 0 ( mod p ) .

A bal oldalon a (modp) redukált maradékok (p-2) tényezős szorzatainak összege, tehát a maradékok egyik elemi szimmetrikus polinomja áll. Így a probléma a 3.4.6 feladat egyik kérdésének felel meg. A problémát ott p=7 esetén tűztük ki, de a megoldás minden p>2 prímre használható.

12.10.0.10 A 4.9.5 b) mego.

Az állítás igaz. Belátjuk, hogy ha p5, akkor

1 1 + 1 2 + + 1 p - 1 0 mod p 2 .

Elõször vegyük észre, hogy

1 p - i - p + i i 2 mod p 2 .

Adjuk ezt össze, ha i 1-tõl (p-1)-ig fut:

1 1 + 1 2 + + 1 p - 1 - p + 1 1 2 - p + 2 2 2 - - p + ( p - 1 ) ( p - 1 ) 2 mod p 2 .

Az egyenlet jobb oldalát alakítva:

1 1 + 1 2 + + 1 p - 1 - p ( 1 1 + 1 4 + + 1 ( p - 1 ) 2 ) - - ( 1 1 + 1 2 + + 1 p - 1 ) mod p 2 .

Ebbõl azonnal következik, hogy

2 ( 1 1 + 1 2 + + 1 p - 1 ) - p ( 1 1 + 1 4 + + 1 ( p - 1 ) 2 ) mod p 2 .

Azaz elég belátni, hogy

1 1 + 1 4 + + 1 ( p - 1 ) 2 0 mod p .

Vegyük észre, hogy a kvadratikus maradékok reciprokai is kvadratikus maradékok (hiszen az 1 is az), és itt minden kvadratikus maradék pontosan kétszer szerepel, tehát az a bizonyítandó, hogy

1 + 4 + + ( p - 1 ) 2 0 mod p .

Ez viszont világos, hiszen a bal oldalon szereplõ összegrõl jól ismert, hogy (p-1)p(2p-1)6, amirõl azonnal látszik, hogy osztható p-vel, ha p5

A 4.9.6 feladat megoldásai

12.10.0.11 Segítség a 4.9.6 feladathoz

Használhatjuk a Bertrand-Csebisev tételt, miszerint bármely k természetes számra k és 2k között van prímszám.

12.10.0.12 A 4.9.6 feladat megoldása

Az állításunkkal szemben tegyük fel, hogy van olyan n, amelyre a

H n = 1 + 1 2 + 1 3 + + 1 n

egész szám.

A Bertrand-Csebisev tétel miatt tehát tudjuk, hogy van olyan p prímszám, amelyre pn<2p. Szorozzuk be az egyenlőség mindkét oldalát n!-sal! Jegyezzük meg, hogy p|n!, de p2n!. Ekkor mind a bal, mind a jobb oldalon egész szám áll, p|n!Hn, a jobb oldal minden tagja is osztható p-vel, kivéve az n!/p tagot. Ebből az ellentmondásból következik, hogy Hn nem egész szám.

12.11 Hatványozás moduláris aritmetikában feladatok megoldása

A 4.10.1 feladat megoldásai

12.11.0.1 A 4.10.1 a) mego.

Lásd a 122., 123., 124., 125. ábrákat!

122. ábra

123. ábra

124. ábra

125. ábra

12.11.0.2 A 4.10.1 b) mego.

3 7 tizedestört alakjának kiszámolására három módszert is adunk:

I. módszer Számoljuk ki fejben a szorzat eredményét az írásbeli szorzás mintájára. Felhasználhatjuk, hogy a periódusok között nincs átmenet.

II. módszer Vegyük észre, hogy

3 7 = 10 7 - 7 7 = 10 1 7 - 1 .

III. módszer Ugyanazt az osztást kell elvégeznünk, mint 17 kiszámolásakor, csak most a 30-as maradékkal kezdünk.

Az eredmény mindhárom módszerrel: 0,4·28571·.

A 313 tört tizedestört alakja 0,2·30769·. Ez az előző I. és III. módszerrel is adódik. A II. módszer alkalmazására most nehezebb rálelni. Esetleg alkalmazhatjuk a

- 3 13 = 10 13 - 13 13 = 10 1 13 - 1

összefüggést.

13 17 = 0 , 7647058823529411 . Ez fejben talán csak a III. módszerrel jön ki.

12.11.0.3 A 4.10.1 c) mego.

A két tört tizedestört alakja periodikus (lásd a 4.10.6 a) feladatot).

12.11.0.4 A 4.10.1 d) mego.

1 18 = 0 , 05 · , ami 16 vagy 19 tizedestört alakjából is megkapható az 118<