Mathematics | Discrete mathematics » Nagy Orsolya - Számelmélet feladatok szakkörre

http://www.doksihu Eötvös Loránd Tudományegyetem Természettudományi Kar Szakdolgozat Számelmélet feladatok szakkörre Nagy Orsolya Matematikai elemz® szakirány Témavezet®: Szalay Mihály egyetemi docens Algebra és Számelmélet Tanszék Budapest 2010 http://www.doksihu Tartalomjegyzék 1. Bevezetés 3 2. Oszthatósági feladatok 4 2.1 Deníciók . 4 2.2 Tételek . 7 2.3 Feladatok . 3. Kongruenciák 12 18 3.1 Deníciók . 18 3.2 Tételek . 19 3.3 Feladatok 22 . 4. Gyorsabb megoldás kongruenciákkal 24 Összefoglalás 28 Köszönetnyilvánítás 29 Felhasznált irodalom 30 2 http://www.doksihu 1. fejezet Bevezetés Szakdolgozatom témájául azért a számelmélet feladatokat választottam, mert középiskolai tanulmányaim

során ez volt az egyik kedvenc témaköröm. Egyetemi éveim alatt sikerült egy sokkal gyorsabb, átláthatóbb megoldási módszerrel is megismerkednem, ez pedig a kongruencia volt. Dolgozatom célja, hogy bemutassam hatékonyságát a gimnáziumban tanultakkal szemben. Arra törekedtem, hogy az olvasó kis bemutatást nyerjen a számelmélet világába. Egyel®re csak a kongruencia alapjaival ismerkedhet meg, de már ebb®l is látszik hasznossága. A második, harmadik fejezet elején lév® tételeim és denícióim nagy részét témavezet®m, Szalay Mihály [1.] valamint Freud Róbert  Gyarmati Edit [2] könyveib®l merítettem. A feladványaimat az irodalomjegyzékben található írások közül válogattam. Igyekeztem alappéldáktól kezdve a versenyfeladatokig mindegyikb®l feldolgozni 3 http://www.doksihu 2. fejezet Oszthatósági feladatok 2.1 Deníciók 1. Deníció: olyan q A b egész számot az egész szám, amelyre Jelölés: b | a. Szavakkal: Ha

nem létezik olyan q egész szám osztójának nevezzük, ha létezik a = bq . a osztható b-vel, illetve a többszöröse a a = q · b, akkor bármely b-re 0 = b · 0. egész, amelyre minden számmal osztható, hiszen 2. Deníció: a a b b-nek. nem osztója Ha egy egész szám minden egész számnak osztója, akkor a-nak. A 0 egységnek nevezzük. 3. Deníció: (1) Ha a d | a, d | b; (2) ha egy Jelölés: Az egész számok legnagyobb közös osztója d, ha és c-re c | a, c | b d = (a, b) a = b = 0, b és vagy teljesül, akkor d=lnko(a, b) vagy |c| ≤ |d|. d=lnko{a, b}. akkor nem létezik legnagyobb közös osztójuk, hiszen minden egész szám közös osztó, és ezek között nincs legnagyobb abszolút érték¶. Minden más esetben a 3. egymás ellentettjei. Deníciót pontosan két d szám elégíti ki, amelyek Mivel egy szám és a negatívja oszthatósági szempontból telje- sen egyenérték¶, ezért a és b összes

közös osztóját úgy kapjuk meg, hogy a pozitív 4 http://www.doksihu közös osztók mellé vesszük azok negatívjait. A pozítív közös osztók az üres halmaz, hiszen az 1 biztosan közös osztó, továbbá P -nek lehet, mert egy nemnulla számnak csak véges sok oszója van. között létezik egy legnagyobb, jelöljük h-val. Ekkor nyilván P halmaza nem csak véges sok eleme Ennélfogva d=h és d = −h P elemei kielégítik a 3. Deníciót, más szám viszont nem 4. Deníció: (1) Az a δ | a, δ | b, és b számok és c-re c | a, c | b (2) ha egy kitüntetett közös osztója δ, ha teljesül, akkor c | δ. A Denícióból következik, hogy ha két számnak létezik kitüntetett közös osztója, akkor az egységszerest®l eltekintve egyértelm¶. Ez részletesen kifejtve azt jelenti, hogy egyrészt egy kitüntetett közös osztó bármely egységszerese is az, másrészt két kitüntetett közös osztó szükségképpen egymás

egységszerese. Ha a = b = 0, akkor a kitüntetett közös osztójuk a deníció szerint 0. A továbbiakban ezzel az esettel egyáltalán nem foglalkozunk, azaz mindig eleve feltesszük, hogy az a és b közül legalább az egyik nem nulla. Megmutatjuk, hogy ha egyáltalán létezik a δ kitüntetett közös osztó, akkor legnagyobb közös osztó (valamelyik értéke lehet). Jelöljük d-vel legnagyobb közös osztót. Ekkor egyrészt (3 Deníció (2)) (2) alapján |d| = |δ|, d | δ, amib®l |d| ≤ |δ| δ csak a δ -val azonos el®jel¶ miatt |δ| ≤ |d|, másrészt a következik. A két egyenl®tlenségb®l kapjuk, hogy és így az azonos el®ljel miatt d = δ. Egyáltalán nem magától éret®d® azonban, hogy a legnagyobb közös osztó valóban rendelkezik a (2) kitüntetett tulajdonsággal is, vagyis hogy bármely két egész számnak létezik kitüntetett közös osztója. 5. Deníció: Az böz® közös osztójuk, 6. Deníció: a1 , a2 , .

, ak számok relatív azaz (a1 , a2 , . , ak ) = 1 Az a1 , a2 , . , ak számok prímek, ha nincs egységt®l külön- páronként relatív prímek, semelyik kett®nek sincs egységt®l különböz® közös osztója, azaz minden esetén ha közülük 1 ≤ i 6= j ≤ k (ai , aj ) = 1. Nyilvánvaló, hogy a páronként relatív prím számok egyúttal relatív prímek is, de ez (k > 2 habár esetén) megfordítva nem igaz. Például a (3, 11) = 1 és (3, 22) = 1 relatív prímek. 5 (3, 11, 22) = 1. Viszont (11, 22) = 11, http://www.doksihu 7. Deníció: A p egységt®l (és nullától) különböz® számot felbonthatatlan számnak nevezzük, ha csak úgy bontható fel két egész szám szorzatára, hogy valamelyik tényez® egység. Azaz p = ab =⇒ a vagy A 0 nemtriviálisan is szorzattá bontható, pl. hogy b egység. 0 · 11 = 0, ezért nem szükséges kikötni, p 6= 0. Továbbá a szorzatban nem lehet Összetett számnak a is, b is

egység, mert akkor p is egység lenne. nevezzük azt a nemnulla számot, amelynek triviálistól külön- böz® osztója is van. 8. Deníció: A p egységt®l és nullától különböz® számot prímszámnak (vagy röviden prímnek) nevezzük, ha csak úgy lehet osztója két egész szám szorzatának, ha legalább az egyik tényez®nek osztója. Azaz p | ab =⇒ p | a El®fordulhat, hogy a kötnünk, hogy p 6= 0, p vagy p | b. a szorzat mindkét tényez®jét osztja. Mindenképpen ki kell mivel a 0-ra teljesül a deníció további részében megfogalmazott tulajdonság: 0 | ab =⇒ ab = 0 =⇒ a = 0 vagy b = 0 =⇒ 0 | a vagy 0 | b. A denícióból következik, hogy egy prímszám egy több tényez®s szorzatnak is csak úgy lehet osztója, ha legalább az egyik tényez®nek az osztója. 9. Deníció: Az a és b pozitív egészek legkisebb közös többszöröse a k pozitív egész, ha (1) (2) Az a és b a | k, b | k ; és ha egy c > 0-ra a |

c, b | c legkisebb közös többszörösét a két szám szorzata, ab a és b [a, b]-vel c ≥ k. (vagy lkkt(a, b)-vel) jelöljük. Mivel nyilvánvalóan közös többszöröse meghatározásához elég az keresni az teljesül, akkor ab-nél a-nak és b-nek, így [a, b] nem nagyobb véges sok pozitív egész között meg- közös többszörösei közül a legkisebbet. A legkisebb közös többszörös létezése és egyértelm¶sége tehát nyilvánvaló. 6 http://www.doksihu 2.2 Tételek Ebben a fejezetben az oszthatóság megértéséhez összegy¶jtöttem az alkalmazott tételeket. Néhányat közülük nem bizonyítottam, mivel vagy triviális, vagy túl hosszú lett volna, a szakdolgozatom célja pedig nem ez. 1. Tétel: Az egész számok körében két egység van, az 1 és a Bizonyítás: Az 1 és 2. Tétel: ε −1. −1 valóban egységek: bármely a-ra ±1 | a, hiszen a = (±1)(±a). Megfordítva, ha ε egység, akkor az ε az 1-nek is

osztója, azaz alkalmas q -val 1 = εq . Mivel |ε| ≥ 1 és |q| ≥ 1, így csak |ε| = 1, azaz ε = ±1 Ha és δ egységek és a, b egész számok, valamint b | a, akkor εb | δa is teljesül. Bizonyítás: ε az 1-nek is osztója, δa = (εb)(δqr), tehát valóban εb | δa. Az azaz alkalmas r-rel 1 = εr. Ha a = bq , akkor A 2. Tétel azt fejezi ki, hogy egy szám és az egységszerese oszthatósági szempontból teljesen azonosan viselkednek; az egységek az oszthatóság szempontjából nem számítanak. Ennek alapján nem jelent megszorítást, ha az egész számok oszthatósági vizsgálatát lesz¶kítjük a nemnegatív egészekre, s®t csak a pozitív egészekkel foglalkozunk 3. Tétel: a, b, c egész számok esetén: a-ra a | a. (1) Minden (2) Ha c|b és b | a, (3) Az a|b és b|a akkor oszthatóságok egyszerre akkor és csak akkor teljesülnek, ha az (4) c | a. a a b-nek egységszerese. c | a és c | b, akkor c | a + b, c | a

− b, tetsz®leges c | ka, és tetsz®leges (egész) r, s-re c | ra + sb. Ha (egész) k -ra (5) a − b | an − bn = (a − b) · (an−1 + an−2 · b + . + bn−1 ) (6) a + b | a2k − b2k = (a + b) · (a2k−1 − a2k−2 · b + . + a · b2k−1 − b2k ) (7) a + b | a2k−1 + b2k−1 = (a + b) · (a2k−2 − a2k−3 · b + . − a · b2k−3 + b2k−2 ) 7 http://www.doksihu 4. Tétel (Oszthatósági szabályok tízes számrendszerben):  Egy szám pontosan akkor osztható 2-vel (5-tel, 10-zel), ha az utolsó számjegye osztható 2-vel (5-tel, 10-zel).  Egy szám pontosan akkor osztható 3-mal, ha számjegyeinek összege osztható 3-mal.  Egy szám pontosan akkor osztható 4-gyel (25-tel, 100-zal), ha az utolsó két számjegyéb®l alkotott szám osztható 4-gyel (25-tel, 100-zal).  Egy szám pontosan akkor osztható 6-tal, ha osztható 2-vel és 3-mal, azaz páros és számjegyeinek összege osztható 3-mal.  Egy szám akkor és csakis akkor osztható 7-tel,

ha a szám utolsó számjegyét®l kezdve a számjegyeit rendre az 1, 3, 2, −1, −3, −2, 1, 3, 2, −1, −3 − 2 . sorozat elemeivel megszorozva, és a szorzatok összegét véve az összeg osztható 7-tel.  Egy szám pontosan akkor osztható 8-cal (125-tel, 1000-rel), ha az utolsó három számjegyb®l alkotott szám osztható 8-cal (125-tel, 1000-rel).  Egy szám pontosan akkor osztható 9-cel, ha számjegyeinek összege osztható 9-cel.  Egy szám akkor és csakis akkor osztható 11-gyel, ha váltakozó el®jellel vett számjegyeinek összege osztható 11-gyel.  Egy szám pontosan akkor osztható 16-tal (625-tel, 10000-rel), ha az utolsó négy számjegyéb®l alkotott szám osztható 16-tal (625-tel, 10000-rel). 5. Tétel: Tetsz®leges meghatározott q és r a és b 6= 0 egész számokhoz léteznek olyan egyértelm¶en egész számok, melyekre a = bq + r Bizonyítás: Legyen el®ször b > 0. és 0 ≤ r < |b|. A 0 ≤ r = a − bq < b

feltétel pontosan akkor teljesül, ha bq ≤ a < b(q + 1), 8 http://www.doksihu azaz q≤ Ilyen q a < q + 1. b egész szám pedig nyilván pontosan egy létezik; olyan egész szám, amely még kisebb vagy egyenl®, mint   a q = , azaz a legnagyobb b a . Ha b < 0, akkor a b 0 ≤ r = a − bq < |b| = −b feltétel q≥ a >q−1 b teljesülésével ekvivalens, ami ismét pontosan egy nál kapott q hányadosnak, az r-et pedig (legkisebb nemnegatív) maradéknak számot nevezzük. A b|a 6. Tétel: oszthatóság (b Tetsz®leges meghatározott q és q egészre áll fenn. A maradékos osztás- r a és 6= 0 esetén) pontosan akkor teljesül, ha a maradék 0. b 6= 0 egész számokhoz léteznek olyan egyértelm¶en egész számok, melyekre a = bq + r − és |b| |b| <r≤ . 2 2 r-et legkisebb abszolút érték¶ maradéknak nevezzük. Például legyen a = 22, b = −6, ekkor 22 = (−6)(−3) + 4 = (−6)(−4) − 2, tehát a

legkisebb nemnegatív maradék a 4, a legkisebb abszolút érték¶ maradék pedig a −2. Ebben az esetben az 7. Tétel: Bármelyik két egész számnak létezik kitüntetett közös osztója. Bizonyítás: A kitüntetett közös osztó létezését az euklideszi algoritmussal iga- zoljuk. Az egyik számot maradékosan elosztjuk a másikkal (feltéve, hogy nem 0), utóbbit a maradékkal és így tovább, mindig az osztót a maradékkal, amíg 0 maradékhoz nem jutunk. Megmutatjuk, hogy az eljárás véges, és az utolsó nemnulla maradék lesz a két szám (egyik) kitüntetett közös osztója. Nézzük mindezt részletesen. megfelel. Ha b nem osztja Tegyük fel, hogy (pl.) a-t, akkor alkalmas qi , ri b 6= 0. Ha egészekkel a = bq1 + r1 , ahol 0 < r1 < |b|, b = r1 q2 + r2 , ahol 0 < r2 < r1 , r1 = r2 q3 + r3 , ahol 0 < r3 < r2 , . . . rn−2 = rn−1 qn + rn , ahol 0 < rn < rn−1 , rn−1 = rn qn+1 rn+1 = 0 9 b | a, akkor δ = b

http://www.doksihu Az eljárás biztosan befejez®dik véges sok lépésben, ugyanis a maradékok nemnegatív egészekb®l álló szigorúan csökken® sorozatot alkotnak: |b| > r1 > r2 > . Most belátjuk, hogy rn valóban az a és b számok (egyik) kitüntetett közös osztója. Az algoritmus egyenl®ségein alulról felfelé haladva el®ször azt igazoljuk, hogy osztója a-nak és b-nek. Az utolsó egyenl®ségb®l rn | rn−1 . rn közös Az utolsó egyenl®ségb®l megkapjuk, hogy rn | rn−1 , rn | rn =⇒ rn | rn−1 qn + rn = rn−2 , ezután rekurzív módon visszahelyettesítünk. felülr®l lefelé haladunk. Legyen c | a, c | b, A kitüntetett tulajdonság igazolásához ekkor az els® egyenl®ségb®l c | a − bq = r1 . A második egyenl®séget nézve c | b, c | r1 =⇒ c | b − r1 q2 = r2 . Ugyanígy folytatva az utolsó el®tti egyenl®ségb®l kapjuk, hogy 8. Tétel: Ha 9. Tétel: Az kifejezhet® c > 0, akkor (ca, cb) =

c(a, b). a és b számok legnagyobb (a, b) = au + bv alakban. 10. Tétel: Ha 11. Tétel: Az egész számok körében c | ab és c | rn . (c, a) = 1, akkor p közös osztója alkalmas u és v egészekkel c | b. akkor és csak akkor prím, ha felbonthatat- lan. Ezért jogosult a felbonthatatlan vagy prím elnevezések bármelyikének a használata, és az is, hogy a középiskolában az egészekre a felbonthatatlan számnak megfelel® tulajdonsággal értelmezik a prímszámot. A két fogalom azonban sok más számkörben nem ekvivalens. 12. Tétel (A számelmélet alaptétele): Minden, a 0-tól és egységt®l különböz® egész szám felbontható véges sok felbonthatatlan szám szorzatára, és ez a felbontás a tényez®k sorrendjét®l és egységszeresekt®l eltekintve egyértelm¶. (Az egyértelm¶ség azt jelenti, hogy ha a = p1 p2 . pr = q1 q2 qs , 10 http://www.doksihu ahol a pi és qj számok párba állíthatók úgy, 13. Tétel: r =

s, és a pi és qj hogy mindegyik pi a hozzá tartozó qj -nek egységszerese.) számok valamennyien felbonthatatlanok, akkor Minden n>1 egész szám felírható n= pα1 1 pα2 2 . pαr r = r Y pαi i i=1 alakban, ahol p1 , . pr különböz® (pozitív) prímek és ai > 0 egész. Ez a felírás a pαi i prímhatványtényez®k sorrendjét®l eltekintve egyértelm¶. Ezt az el®állítást az n szám kanonikus alakjának nevezzük. Bizonyos esetekben megengedhetjük, hogy a kanonikus alakban egyes prímek kitev®je 0 lehessen, ekkor az egyértelm¶ség természetesen ezekt®l a tényez®kt®l eltekintve értend®. Ily módon az 1 számnak is beszélhetünk kanonikus alakjáról 14. Tétel: A n = pα1 1 pα2 2 . pαr r kanonikus alakú n számnak egy d pozitív egész akkor és csak akkor osztója, ha d kanonikus alakja d = pβ1 1 pβ2 2 . pβr r , ahol 0 ≤ βi ≤ αi , i = 1, 2, . r Az osztók esetében a 0 kitev®t is megenged®

módosított kanonikus alakot használtunk. n triviális osztókat abban a két speciális esetben (minden i-re) βi = 0, illetve βi = αi . Egy n > 0 egész pozitív osztóinak a számát d(n)-nel jelöljük. Például d(1) = 1, d(8) = 4, d(n) = 2 ⇐⇒ n prím. Az 1, illetve 15. Tétel: Az n = pα1 1 pα2 2 . pαr r kanonikus alakú n szám pozitív osztóinak a száma d(n) = (α1 + 1)(α2 + 1) . (αr + 1) 11 kapjuk meg, amikor http://www.doksihu 2.3 Feladatok 1. Feladat: Bizonyítsa be, hogy minden n∈N számra 6 | n3 + 11n. I.Megoldás : Egy szám osztható 6-tal, ha páros és számjegyeinek összege osztható 3-mal. n3 + 11n = (n − 1)n(n + 1) + 12n vizsgalatából láthatjuk, hogy mindenképpen osztható lesz hárommal, mivel az els® tag 3 egymást követ® egész szám szorzata és 3 | 12. Kett®vel is osztható, mert két páratlan és egy páros szorzata, valamint két páros és egy páratlan szorzata is páros lesz és 2 | 12. 6 | n3 + 11n =

n(n2 + 11). n = 1 esetén 13 + 11 · 1 = 12 6 | 12 igaz. Tegyük fel, hogy n-re igaz, bizonyítjuk, hogy akkor (n + 1)-re is 6 | (n + 1)3 + 11(n + 1). (n + 1)3 + 11(n + 1) = (n3 + 11n) + 12 + 3n(n + 1). II.Megoldás : Teljes indukcióval: igaz, hogy Mindegyik tag osztható 6-tal: n3 + 11n a feltétel miatt, 3n(n + 1) pedig azért, mert az a az n(n + 1) két egymást követ® egész szám szorzata, vagyis páros és hármas tényez® is megtalálható a szorzatban. Mivel az örökl®dést is beláttuk, ezért igaz az állítás. 2. Feladat: Bizonyítsa be, hogy 19 | 3123 − 2123 és 19 | 3124 − 11 · 2124 . 19 | 3123 − 2123 : = (33 )41 − (23 )41 = 2741 − 841 =⇒ 27 − 8 | 2741 − 841 , vagyis Megoldás : 3123 − 2123 19 | 2741 − 841 19 | 3124 − 11 · 2124 : 3124 − 11 · 2124 = 3124 − 3 · 2123 + 3 · 2123 − 11 · 2124 = 3(3123 − 2123 ) + 2123 (3 − 22). 123 Az el®z® példából: 19 | 3 − 2123 és a másik tag is osztható 19-cel. 3.

Feladat (Forrás: [4]): Egy tányérban cseresznye van. Felszólítunk valakit, hogy a cseresznyét távollétünkben szedje ki ötösével, és minden 5 cseresznyéb®l tegyen egyet a következ® tányérba, 4-et egy tálba. Ha már csak 5-nél kevesebb cseresznye van, azt hagyja az els® tányérban, a második tányérból pedig rakja tovább ugyanilyen eljárással a cseresznyét. Ezt ismételje addig, amíg az utolsó tányérba 5-nél kevesebb cseresznye nem kerül. Ezután csak a tányérokban lev® cseresznyéket nézve meg tudjuk állapítani, hány szem cseresznye volt összesen. Hogyan? Mennyi cseresznye volt, ha a négy tányérba sorra 2, 4, 1, 3 cseresznye került és több tányérra nem volt szükség? 12 http://www.doksihu Hogyan alakul a helyzet, ha nem ötösével, hanem kettesével, ill. tízesével szedjük ki a cseresznyét? Megoldás : a) Jelöljük a-val az 1. tányérban eredetileg lév® cseresznyék számát, amit keresünk. Nevezzük el:

b-nek az 1. c-nek az 2. d-nek az 3. tányérból a 2.-ba tett cseresznyék számát, tányérból a 3.-ba tett cseresznyék számát, tányérból a 4.-be tett cseresznyék számát Tudjuk, hogy az öttel való osztási maradékok az a, b, c, d-nek rendre 2, 4, 1, 3. Ebb®l következik, hogy: a = 5b + 2 b = 5c + 4 c = 5d + 1 d=3 Behelyettesítéssel megkapjuk, hogy Vagyis b) a = 2 + 5(4 + 5(1 + 3 · 5)) = 422. 422 db cseresznye volt a tányérban eredetileg. Ha kettesével szedjük ki a cseresznyéket: A kett®vel való osztás adja meg, hogy hányszor tettünk át cseresznyét a következ® tányérba, az osztási maradékok pedig azt, hogy a végén mennyi cseresznye maradt bennük. 422 = 221 · 2 + 0 221 = 105 · 2 + 1 105 = 52 · 2 + 1 52 = 26 · 2 + 0 26 = 13 · 2 + 0 13 = 6 · 2 + 1 6 = 3·2+0 3 = 1·2+1 1 = 0·2+1 13 http://www.doksihu Tehát 9 darab tányérra lenne szükségünk, amikben rendre 0, 1, 1, 0, 0, 1, 0, 1, 1 darab cseresznye maradna. c) Ha

tízesével szedjük ki a cseresznyéket: A tízesével való osztás adja meg, hogy hányszor tettünk át cseresznyét a következ® tányérba, az osztási maradékok pedig azt, hogy a végén mennyi cseresznye maradt bennük. 422 = 42 · 10 + 2 42 = 4 · 10 + 2 4 = 0 · 10 + 4 Tehát 3 darab tányérra lenne szükségünk, amikben rendre 2, 2, 4 darab cseresznye maradna. 4. Feladat (KÖMaL, 1996 szeptember): Legfeljebb hány olyan hónap lehet egy évben, amelyben öt vasárnap van? Megoldás : Egy hónap napjainak száma 28 és 31 között változik, vagyis minden hónapban legalább 4 vasárnap van, 5-nél több viszont egyetlen hónapban sincsen. Egy év 365 = 52 · 7 + 1 napból áll, vagy pedig - szök®év esetén - 366 = 52 · 7 + 2 nap- ból, így egy évben 52 vagy 53 vasárnap van. A tizenkét hónap mindegyike tartalmaz tehát legalább 4 vasárnapot. Az így adódó 48-on túl fennmaradó 4, illetve 5 vasárnap feltétlenül különböz® hónapokra esik,

mert 6 vasárnap nem lehet egy hónapban. Ez azt jelenti, hogy legfeljebb öt olyan hónap lehet egy évben, amelyben öt vasárnap van. Ez éppen azokban az években fordul el®, amelyekben 53 vasárnap van, vagyis, ha az év els® napja vasárnap, illetve szök®év esetén, ha az els® nap szombat, vagy vasárnap. 5. Feladat (Forrás: [2]): a) egyiken egy-egy mókus. Egy kör alakú tisztás mentén m fa áll, mind- A mókusok össze szeretnének gy¶lni egy fán, de csak úgy változtathatják a helyüket, hogy két tetsz®leges mókus egyidej¶leg átugorhat egy-egy szomszédos fára. Ezt a lépest akárhányszor megismételhetik Milyen m esetén tudnak összegy¶lni a mókusok? b) Mi a helyzet akkor, ha a megengedett lépést a következ®képpen módosítjuk: két tetsz®leges mókus egyidej¶leg átugorhat egy-egy szomszédos fára, azonban ellenkez® körüljárási irányban kell ugorniuk. 14 http://www.doksihu Megoldás : a) Pontosan akkor tudnak

összegy¶lni, ha Ha m páratlan, vagyis 4k ± 1 m páratlan vagy osztható 4-gyel. alakú, akkor a legnagyobb fán lev® mókus maradjon ott, a két szomszédja egy lépésben odaugrik, a két másodszomszédja két lépésben odaugrik és így tovább. Ha m osztható 4-gyel, vagyis 4k alakú, akkor a fenti lépések után csak a legnagyobb fával szemközti fán marad egy mókus, amely páros sok ugrással eljut a többiekhez, miközben egy másik ide-oda ugrál a legnagyobb fa és valamelyik szomszédja között. Végül, ha m páros, de 4-gyel nem osztható, vagyis 4k + 2 alakú, akkor a mókusok nem tudnak összegy¶lni. Tekintsük ugyanis, hány ugrással juthat el egy-egy mókus a kijelölt fára. Ezeknek az ugrásszámoknak az összege mindenképpen páratlan, tehát a feladat feltételei szerint nem valósítható meg. Megoldás : b) Pontosan a páratlan Az a)-beli m-ekre lesz mókusgy¶lés. gondolatmenetek továbbra is érvényesek, ha A 4-gyel

osztható (illetve tetsz®leges páros) 1-t®l m-ig. m-ekre m nem osztható 4-gyel. számozzuk meg a fákat sorban Minden helyzetben adjuk össze azoknak a fáknak a sorszámait, amely fákon mókus ül, mégpedig minden sorszámot annyiszor, ahány mókus található az adott fán. Ennek az összegnek az m-mel vett maradéka nem változik az ugrálás során. A kiin- dulási helyzetben ez a maradék maradéka, ami m/2. 1 + 2 + 3 + ··· + m = m(m+1) 2 = m · (m/2) + m/2 Ha miden mókus ugyanazon a fán tanyázik, akkor a maradék nyilván 0, tehát ez az állapot nem jöhet létre. 6. Feladat (Forrás: [6]): Írjunk fel olyan, az 1, 2, . , 6 számjegyek valamilyen sorrendjéb®l álló 6-jegy¶ számot, melynek els® két jegyéb®l álló szám osztható 2-vel, az els® 3 jegyéb®l álló szám osztható 3-mal, az els® 4 jegyéb®l álló szám osztható 4-gyel, az els® 5 jegyéb®l álló szám osztható 5-tel és maga a szám osztható 6-tal. 15

http://www.doksihu Megoldás : Oszthatósági szabályok felhasználásával.1 Az 5. helyre mindenképpen 5-öt kell írnunk,mert csak akkor lesz osztható 5-tel (mivel nincs 0). A 2., 4, 6 helyre mindenképpen páros szám kerül, mivel csak akkor lehet osztható 2-vel, 4-gyel, 6-tal. Így az 1. és 3 helyre marad az 1 és a 3 helyiérték 1. 2. 3. 4. 5. 6. lehetséges számok 1, 3 2, 4, 6 1, 3 2, 4, 6 5 2, 4, 6 Az els® 3 jegyéb®l álló szám akkor lesz osztható 3-mal, ha a 2. helyen 2 áll, mert csak akkor teljesül rá, hogy 3 | 1 + 3 + 2 = 6. Az els® 4 jegyéb®l álló szám akkor lesz osztható 4-gyel, ha a 4. helyen nem 4 áll, mivel a 3.-4 hely csak ilyen formájú lehet: 12, 16, 32, 36. Emiatt a 6. helyen mindenképpen a 4-nek kell állnia és a 4 helyen mindenképpen a 6-nak. Tehát a következ® megoldások lehetségesek: 7. Feladat (Forrás: [3]): ha n 123654, 321654. Bizonyítsuk be, hogy 33n+3 −26n−27 osztható 169-cel, nemnegatív

egész szám. Megoldás : Kell: 169 | 33n+3 − 26n − 27 Bizonyítás teljes indukcióval: n=1 Tegyük fel, hogy (n + 1)-re 169 | 33·1+3 − 26 · 1 − 27 = 676. 3n+3 igaz, vagyis 169 | 3 − 26n − 27, esetén igaz, mert n-re bizonyítjuk, hogy akkor is igaz. 33(n+1)+3 − 26(n + 1) − 27 = 33n+6 − 26n − 26 − 27 = 33 · (33n+3 − 26n − 27) + 676n + 676 = 33 · (33n+3 − 26n − 27) + 4 · 169(n + 1) Az els® tag az indukciós feltevés miatt osztható 169-cel, a második tagban pedig szorzótényez®ként szerepel, tehát osztható vele. 1 Lásd 2. fejezet 4 Tétel 16 http://www.doksihu 8. Feladat (Forrás: [2]): Egy kegyetlen várúr börtönének 400 sz¶k cellájában egy-egy rab sínyl®dik. A cellák ajtaján lév® zár úgy m¶ködik, hogy egy elfordítás esetén nyílik, még egy elfordítás esetén ismét bezárul Jelenleg természetesen minden ajtó zárva van. A várúr a születésnapján elhatározza, hogy nagylelk¶ lesz, és

megparancsolja az egyik ®rnek, hogy fordítson egyet valamennyi záron Közben azonban meggondolja magát, és utánaküld egy másik ®rt, akit azzal bíz meg, hogy minden második záron fordítson egyet. Ezt követi a harmadik ®r, aki minden harmadik záron változtat és így tovább, végül a négyszázadik ®r a négyszázadik cella zárjának az állását módosítja. Azok a rabok szabadulnak ki, akiknek most nyitva van az ajtaja. Hány rabot bocsátott szabadon a várúr? Megoldás : Az ®rök annyiszor fordítanak az n. számú záron, amennyi osztója van az adott cellának. Meggondolva tehát, csak akkor szabadul ki egy rab, ha d(n) páratlan d(n) = 2k +1 alakú. Ez viszont csak akkor lehetséges, ha n négyzetszám esetben d(n) páros számú lesz, ugyanis a többi esetben a kanonikus alak számú, vagyis Minden más tartalmaz páratlan kitev®j¶ hatványt, emiatt pedig az osztóinak a száma páros lesz. 2 Tehát 1-t®l 400-ig kell csak megkeresnünk a

négyzetszámokat. A feltételeknek megfelel®en az 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400 lesznek a jó cellák. Tehát összesen 2 Lásd 20 rab lesz szabad a várúr nagylelk¶sége miatt. 2. fejezet 15 Tétel 17 http://www.doksihu 3. fejezet Kongruenciák 3.1 Deníciók a A kongruencia fogalma: Legyenek mondjuk, hogy Jelölés: mot a a≡b és kongruens b-vel modulo (mod m) vagy röviden b egész számok m, ha m | a − b. a ≡ b (m). és m pozitív egész. Az (általában rögzített) m Azt szá- modulusnak nevezzük. Ha a és b m, akkor azt mondjuk, a inkongruens b-vel modulo m). nem kongruensek modulo ensnek modulo m (vagy hogy a és b inkongru- El®ször érdemes megjegyezni, hogy a modulus lehet ugyan negatív, de (mod m) ⇐⇒ a ≡ b (mod |m|) A modulus lehet 0 is : a ≡ b miatt elég nemnegatív modulusokra szorítkozni. a, b ∈ Z-re a ≡ b (mod 0) ⇐⇒ 0 | a − b ⇐⇒ a

= b. Az egyenl®ség tehát ott van a kongruenciák között, de jól ismerjük a tulajdonságait, így elég m ≥ 1-re szorítkozni. m = 1 eset viszont érdektelen, 1 | a − b. Az Következtetéseinknél tehát m≥2 mert minden a, b ∈ Z-re a ≡ b m | a − b ⇐⇒ m | b − a, a≡b hiszen az érdekes eset, s legfeljebb kényelmesebb meg- fogalmazás céljából fordulhat el® más modulus. Mivel (mod 1), ezért (mod m) ⇐⇒ b ≡ a 18 (mod m). http://www.doksihu Deníció: Legyen m ≥ 2 egész. Azt mondjuk, hogy a c1 , c2 , · · · , ck (mod m) teljes maradékrendszert alkotnak, ha egész számok a) k = m. és b) páronként inkongruensek (mod m). 3.2 Tételek Ebben a fejezetben gy¶jtöttem össze a kongruenciák megértéséhez az alkalmazott tételeket. 1. Tétel: a, b, c, m egész számok, akkor érvényesek a következ®k: (i) a ≡ a (mod m) (refexivitás); (ii) a ≡ b (mod m) =⇒ b ≡ a (mod m) (szimmetria); (iii) a ≡ b (mod m)

és b ≡ c (mod m) =⇒ a ≡ c (mod m). (tranzitivitás) Ha Bizonyítás: m | 0 = a − a miatt a ≡ a (mod m). a ≡ b (mod m) =⇒ m | a − b, így m | b − a, tehát b ≡ a (mod m). Ha a ≡ b (mod m) és ha b ≡ c (mod m) =⇒ m | a − b és m | b − c, m | (a − b) + (b − c) = a − c, tehát a ≡ c (mod m). Ha 2. Tétel: Legyenek a, b, c, d, m, u, v egészek. Ha a ≡ b (m) és c ≡ d (m), ezért akkor tejesülnek a következ®k: a) a + c ≡ b + d (mod m); b) a − c ≡ b − d (mod m); c) au + cv ≡ bu + dv d) ac ≡ bd Bizonyítás: (mod m); (mod m). m | a−b és m | c−d. Ezért m | u(a−b)+v(c−d) = (au + cv) − (bu + dv) adja a c) állítást; ebb®l u = 1; v = 1 az a) állítást; u = 1; v = −1 a b) állítást; végül u = c; v = b esetén m | (ac+cb)−(bc+bd) = ac−bd adja a d) állítást. A feltételek szerint 19 http://www.doksihu 3. Tétel: a, b, k, n Ha egészek, k ≥ 1, n ≥ 1, akkor teljesülnek rá a

következ®k: a) a − b | an − bn ; b) a + b | a2k − b2k ; c) a + b | a2k−1 + b2k−1 ; Bizonyítás: a) a − b | a − b révén a ≡ b (mod a − b), tehát an ≡ bn (mod a − b). b) és c) a + b | a + b miatt a ≡ −b (mod a + b), tehát an ≡ (−1)n bn (mod a + b), 2k így a ≡ b2k (mod a + b) és a2k−1 ≡ −b2k−1 (mod a + b). 4. Tétel: Ha a, b, c, m egészek, m 6= 0, valamint d = (c, m). m (mod m), akkor a ≡ b (mod ). d Legyenek ca ≡ cb Bizonyítás: A kongruencia deníciója alapján ami tovább ekvivalens az m c | (a − b) d d pontosan akkor teljesül, ha 5. Tétel: (a, m) = 1. m c | (a − b) d d c1 , c2 , · · · , cm ac1 , ac2 , · · · , acm is Legyen Ekkor Bizonyítás: Számuk láthatóan a-val egyszer¶síthetünk (mod m), tehát i = j . att 6. Tétel: Legyenek ca ≡ cb oszthatósággal. m | (a − b), d teljes maradékrendszer teljes maradékrendszer m. Ha aci ≡ acj (a, b) | b (mod m), (mod m), a ∈ Z

(mod m). a, b, c El®ször tegyük fel, hogy létezik (a, m) = 1 miTétel,) így ci ≡ cj ax + by = c (a, b) | c. rögzített egész számok. x0 , y0 és akkor a modulus változtatása nélkül (lásd 4. egyenletnek akkor és csak akkor létezik megoldása, ha Bizonyítás: azaz (mod m) m | (a−b)c,  m⇐⇒ c Mivel , = 1, ezért d d m a ≡ b (mod ). d Az megoldás.Ekkor diofantikus (a, b) | a és alapján szükségképpen (a, b) | ax0 + by0 = c. (a, b) | c, vagyis van olyan t egész, amelyre (a, b)t = c. A korábbiak alapján (a, b) = au+bv teljesül alkalmas u, v egészekkel. Ezt az egyenl®séget t-vel beszorozva megkapjuk, hogy c = a(ut) + b(vt), azaz x = ut, y = vt megoldása az ax + by = c diofantikus egyenletnek. Megfordítva tegyük fel, hogy 1 1 Lásd 2. Fejezet 9 Tétel 20 http://www.doksihu 7. Tétel: ax ≡ b (mod m) kongruencia megoldhatóságának szükséges és elégséges feltétele: (a, m) | b. Ha ez a feltétel teljesül és x1 ∈ Z

egy rögzített megoldás: ax1 ≡ b (mod m), akkor az ax ≡ b (mod m) m k alakban, ahol k egész; végül ez minden x egész megoldása felírható x = x1 + (a, m) a kifejezés minden k egészre valóban megoldást szolgáltat. m Érdemes még kiemelni, hogy az x ≡ x1 (mod ). (a, m) Legyenek a, b, m egészek, 8. Tétel ("kis" Fermat-tétel): m 6= 0. Tetsz®leges Az p pozitív prímszám esetén érvényesek a következ®k: a) ha a ∈ Z, akkor ap ≡ a (mod p), b) ha a ∈ Z és (a, p) = 1, akkor ap−1 ≡ 1 Bizonyítás: (mod p). b) állítást bizonyítjuk. Mivel 0, 1, 2, , p − 1 teljes maradékrendszer mod p, azért a ∈ Z, (a, p) = 1 esetén 0a, 1a, 2a, , (p − 1)a is teljes maradékrendszer az 5 Tétel szerint Így az utóbbi számok mod p legkisebb nemnegatív maradékai sorrendt®l eltekintve éppen 0, 1, 2, . , p − 1, s pontosan az els®é a 0, tehát 1a, 2a, 3a, . , (p − 1)a maradékai 1, 2, , p − 1 Így El®ször a

(1a)(2a)(3a) . ((p − 1)a) ≡ 1 · 2 · · · (p − 1) hiszen itt már a sorrend nem okoz bajt. Mivel a (p − 1)! (mod p), relatív prím p-hez, így lehet vele egyszer¶síteni. a-val szorozva, adódik ap ≡ a (mod p), ami éppen az a) állítás, de most még csak (a, p) = 1 esetére jött ki. Ha (a, p) 6= 1, akkor - mivel p prím - (a, p) = p, vagyis p | a, a ≡ 0 mod p, amikor viszont nyilvánvaló az a) állítás. Még 21 http://www.doksihu 3.3 Feladatok 1. Feladat: Egy szám háromszorosa 25-tel osztva 4 maradékot ad. Milyen maradékot adhat 25-tel osztva a szám kétszerese? Megoldás : a számot nevezzük el Tudjuk, hogy x-nek. 3x = 25k + 4. Az el®z®ekben kimondott tételek alapján felírható: 3x ≡ 4 (mod 25) ∃ 3x ≡ 4 + 25 · 2 3x ≡ 54 x ≡ 18 x ≡ 18 x ≡ 18 (mod 25) 2x ≡ 36 ≡ 11 -b®l a 2. Tétel (mod 25) 1 = (3, 25) | 4 igaz. (mod 25) (mod 25) 25 ) (mod (3; 25) (mod 25) Vagyis a szám kétszerese 2. Feladat:

megoldás, mivel d) (25, 3) = 1 része alapján [c = d = 2-vel] adódik. 11 maradékot ad 25-tel osztva. 135x126 − 90x62 − 42x24 + 34x6 ≡ 0 (mod 13) az összes olyan x egész számot, amelyre teljesül a Oldjuk meg a gruenciát, azaz keressük meg kongruencia. Megoldás : Mivel a konstans 0, ezért az A továbbaiakban feltesszük, hogy x ≡ 0 (mod 13) x 6= 0 + 13t. 5x126 + x62 − 3x24 + 8x6 ≡ 0 (mod 13) x13−1 ≡ 1 (mod 13) 5x6 + x2 − 3 − 5x6 ≡ 0 (mod 13) x2 ≡ 3 (mod 13) x2 ≡ 16 (mod 13) x = 4 + 13t x = −4 + 13t x = 0 + 13t. 22 megoldás. 8. Tétel miatt, konfenti http://www.doksihu 3. Feladat: Állítsa el® 983-at egy 21-gyel osztható háromjegy¶ természetes szám és egy 31-gyel osztható háromjegy¶ természetes szám összegeként. Megoldás : a, b háromjegy¶ természetes szám. 99 < a < 1000, 99 < b < 1000. a = 21y, b = 31x, tehát 983 = 21y + 31x. Ebb®l 21y = 983 − 31x =⇒ 21 | 983 − 31x. A

háromjegy¶ség miatti korlátok: 983 ≡ 31x (mod 21) 17 ≡ 10x (mod 21) −4 ≡ 10x (mod 21) −2 ≡ 5x (mod 21) 40 ≡ 5x (mod 21) 8 ≡ x mivel (10,21)=1 (mod 21) x = 8 + 21t Visszahelyettesítve: 21y = 983 − 31 · (8 + 21t) = 735 − 31 · 21t y = 35 − 31t t > 1 esetén az a = 21y negatív lesz. t = 1 esetén csak kétjegy¶ lesz. t ≤ −1 esetén legalább négyjegy¶ lesz. t = 0 esetén lesz csak háromjegy¶, vagyis y = 35, x = 8 =⇒ a = 31 · 8 = 248, b = 21 · 35 = 735 A megoldás: a=248, b=735. 23 http://www.doksihu 4. fejezet Gyorsabb megoldás kongruenciákkal 1. Feladat (Forrás [5]): x 11-gyel osztva 7, y pedig 9 maradékot ad meg x ± y, illetve xy Állapítsuk 11-gyel való osztási maradékát! I.Megoldás (oszthatósággal) : x = 11a + 7, y = 11a + 9 (a, b egész) x + y = 11a + 11b + 16 = (11a + 11b + 11) + 5. A maradék 5 x − y = 11a + 7 − 11b − 9 = 11a − 11b − 2 = (11a − 11b − 11) + 9. A maradék 9 xy = (11a +

7)(11b + 9) = 121ab + 77b + 99a + 63 = (121a + 77b + 99a + 55) + 8. A maradék 8. II.Megoldás (kongruenciával) : Felírható: x≡7 x + y ≡ 7 + 9 = 16 x+y ≡ 5 (mod 11) (mod 11) xy ≡ 7 · 9 = 63 xy ≡ 8 2. Feladat (Forrás [5]): (mod 11) (mod 11) A maradék x − y ≡ (7 + 11) − 9 x−y ≡ 9 (mod 11), y ≡ 9 5. (mod 11) A maradék 9. (mod 11) (mod 11) A maradék Mi a maradék, ha 2100 -t 8. osztjuk 7-tel? I.Megoldás (oszthatósággal) : Nézzük meg az els® néhány hatvány maradékát! a szám 20 21 22 23 24 25 26 27 a 7-tel való osztási maradék 1 2 4 1 2 4 1 2 Ez így megy tovább periodikusan, mert: n 2 2n maradéka 1 maradéka 2 n+1 =⇒ 2 =⇒ 2n+1 maradéka 2, maradéka 4, 24 2n+1 = 2n · 2, tehát: http://www.doksihu 2n maradéka 4 =⇒ 2n+1 maradéka 8, vagyis 1. Szóval 1 után 2, 2 után 4, 4 után ismét 1 következik. Mi történik 2100 -nál? Mivel a maradékok hármasával ismétl®dnek,

ezért 100-nál ugyanaz van, mint (100 − 3n)-nél, tehát például (100 − 99)-nél, vagyis 1-nél. 21 osztási maradéka 2, így 2100 maradéka is 2. n Jegyezzük meg, hogy a fentiek szerint 2 7-tel való osztási attól függ, hogy n 3-mal osztva milyen maradékot ad. maradéka 2100 ≡ x (mod 7) 6 hogy: 2 ≡ 1 (mod 7), kizárólag II. Megoldás (kongruenciával) : Felírható: A Tehát 8. Tétel felhasználásával felírható, 2100 (26 )16 ≡ 1 (mod 7) 296 ≡ 1 (mod 7) 24 ≡ x (mod 7) 16 ≡ x (mod 7) 2 ≡ x (mod 7) 7-tel való osztási maradéka 3. Feladat (Forrás: [2]): ebb®l: 2. 23 + 46 + 12 + 18 = 99 és 99 osztója 23461218-nak. Tényleg a véletlen játékával Érdekes módon a számok egymás mellé írásával keletkez® állunk szemben? Megoldás (oszthatósággal) : Egy szám csak akkor osztható 99-cel, ha 11-gyel és 9-el is 1 2+3+4+6+1+2+1+8 = 27. +2 − 3 + 4 − 6 + 1 − 2 + 1 − 8 = −11. Bárhogy osztható. A vizsgálandó

számunk osztható lesz 9-cel , mert Egyúttal 11-gyel 2 is osztható, mert variálhatom ezeket a kétjegy¶ számokat, a kapott nyolcjegy¶ szám mindig teljesíteni fogja a 11-gyel való oszthatósági szabályt. Ennek hátterében az a feltétel teljesül, hogy a kétjegy¶ számok és a nyolcjegy¶ szám azonos számjegyei megegyeznek -helyiértéknek megfelel®en - a 10 kitev®iben (mod 2) felett. II.Megoldás (kongruenciával) : A feladat így is felírható: 1 Lásd 2 Lásd 18 · 1000 + 12 · 1001 + 46 · 1002 + 23 · 1003 ≡ 0 (mod 99) 18 + 12 · 1 + 46 · 12 + 23 · 13 ≡ 0 (mod 99) 99 ≡ 0 (mod 99) 2. fejezet, 4 Tétel ugyanott. 25 http://www.doksihu Nem a véletlen játékával állunk szemben, ugyanis a 1000 , 1001 , 1002 , 1003 -nak mind 1 a 99-cel vett osztási maradéka. Így csak a 18-at, 12-t, 46-ot, 23-at kell összeadnunk és mivel az összeadás kommutatív, ezért bármelyik permutációja a számoknak osztható lesz 99-cel. 4. Feladat

(Forrás: [2]): k+1 23 | 61 k 2k + 11 · 7 3k ·3 Bizonyítsuk be, hogy bármilyen k természetes számra: 5k+3 ·2 Megoldás (oszthatósággal) : Teljes indukcióval: 23 | 612 + 111 · 72 · 33 · 28 = 3729289 igaz. k+1 Tegyük fel, hogy k -ra igaz, vagyis 23 | 61 + 11k · 72k · 33k · 25k+3 = 61 · 61k + 8 · (11 · 49 · 27 · 32)k , bizonyítjuk, hogy akkor (k + 1)-re is igaz. k=1 esetén 61k+2 + 11k+1 · 72(k+1) · 33(k+1) · 25(k+1)+3 = 612 · 61k + 11 · 11k · 49 · 49k · 27 · 27k · 256 · 32k = 612 · 61k + 3725568 · 465696k = 38(61 · 61k + 8 · 465696k ) + 23(61 · 61k + 161968 · 465696k ) Az els® tag osztható 23-mal az indukciós feltevés miatt, a második tag pedig azért, mert szorzótényez®ként szerepel benne. Megoldás (kongruenciával) : Azt kell belátni, hogy 61k+1 + 11k · 72k · 33k · 25k+3 ≡ 0 A bal oldalt a (mod 23) 2. Tétel felhasználásával vele kongruens kifejezésekké alakítjuk, amíg 0-t nem kapunk: 61k+1 + 11k · 72k

· 33k · 25k+3 ≡ 0 (mod 23) 61 · 61k + 11k · 49k · 27k · 8 · 32k ≡ 0 (mod 23) 61 · (−8)k + 8 · 11k · 3k · 4k · 9k ≡ 0 (mod 23) 61 · (−8)k + 8 · 22k · 54k ≡ 0 (mod 23) 61 · (−8)k + 8 · (−1)k · 8k ≡ 0 (mod 23) (−8)k · 69 ≡ 0 (mod 23) (−8)k · 23 · 3 ≡ 0 (mod 23) Beláttuk, hogy osztható 23-mal. 26 http://www.doksihu Észrevétel: Láthatjuk, hogy az I. megoldásnál nagy számokkal kell számolnunk, ezért nagyobb a tévesztési lehet®ség is, valamint sokkal hosszabb a bizonyítása, mint a kongruenciáé. A II megoldás során gyorsabban bizonyítható az oszthatóság 27 http://www.doksihu Összefoglalás Reményeim szerint sikerült rövid áttekintést nyerni a számelmélet egy kicsiny részéb®l. Szakdolgozatom második fejezetében olyan oszthatósági feladatokkal foglalkoztam, melyek felkeltik a gyerekek érdek®dését, próbáltam ezek közül minél több szövegeset, gondolkodtatót feldolgozni

Többféle megoldási módszert is felhasználtam: teljes indukciós bizonyítást, logikus következtetéseket és átalakításokat. A harmadik fejezetben olyan kongruenciával kapcsolatos problémák szerepelnek, melyeket középiskolai tudással nem, vagy csak nagyon nehezen tudnánk megoldani. Végül a negyedik fejezetbe gy¶jtöttem össze azokat a példákat, amelyek kongruenciával gyorsabb megoldást adnak, mint oszthatósággal. 28 http://www.doksihu Köszönetnyilvánítás Els®sorban Szalay Mihálynak, témavezet®mnek szeretném megköszönni precizitását, útmutatásait, ösztönz® leveleit és kitartását velem kapcsolatban. Továbbá családomnak mind az anyagi, mind a lelki támogatást. Nélkülük nem sikerült volna idáig eljutnom. Végül, de nem utolsó sorban szaktársamnak, Szalai Gábornak mondok köszönetet, aki id®t, fáradtságot nem kímélve mindig a segítségemre volt a technikai részletekben a szakdolgozat megírásakor. 29

http://www.doksihu Felhasznált irodalom [1.] Szalay Mihály : Számelmélet (középiskolai tankönyv és szakköri füzet). TYPOTEX, Nemzeti Tankönyvkiadó, 1998. [2.] Freud Róbert  Gyarmati Edit : Számelmélet Nemzeti Tankönyvkiadó, 2000 [3.] Sárközy András  Surányi János : Számelmélet feladatgy¶jtemény Tankönyvkiadó, 1974. [4.] Erd®s Pál  Surányi János : Válogatott fejezetek a számelméletb®l Tankönyvkiadó Vállalat, 1960. [5.] Pósa Lajos: Összefoglalás M¶szaki Könyvkiadó,1999 [6.] Róka Sándor: 2000 feladat az elemi matematika köréb®l TYPOTEX, 2000. 30