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
Tartalomjegyzék
1. Bevezetés
3
2. Oszthatósági feladatok
4
2.1.
De níciók
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.
Tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3.
Feladatok
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Kongruenciák
12
18
3.1.
De ní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
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 de ní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
2. fejezet
Oszthatósági feladatok
2.1. De níciók 1. De ní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. De ní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. De ní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.
De ní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
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. De níciót, más szám viszont nem.
4. De ní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 De ní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 de ní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. De ní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. De níció:
Az
böz® közös osztójuk,
6. De ní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,
7. De ní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. De ní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 de níció további részében megfogalmazott
tulajdonság:
0 | ab =⇒ ab = 0 =⇒ a = 0
vagy
b = 0 =⇒ 0 | a
vagy
0 | b.
A de ní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. De ní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
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
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
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-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
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
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
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
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
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
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
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
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
2
tartalmaz páratlan kitev®j¶ hatványt, emiatt pedig az osztóinak a száma páros lesz.
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
3. fejezet
Kongruenciák
3.1. De níciók a
A kongruencia fogalma: Legyenek mondjuk, hogy
Jelölés: mot
a
és
kongruens b-vel modulo
a ≡ b (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 (mod 1),
az érdekes eset, s legfeljebb kényelmesebb meg-
fogalmazás céljából fordulhat el® más modulus.
Mivel
m | a − b ⇐⇒ m | b − a,
hiszen
ezért
a ≡ b (mod m) ⇐⇒ b ≡ a (mod m).
18
De ní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
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 ca ≡ cb (mod m), akkor a ≡ b (mod ). d Legyenek
Bizonyítás:
ami tovább ekvivalens az
m c | (a − b) d d
(a, m) = 1.
m c | (a − b) d d
pontosan akkor teljesül, ha
5. Tétel:
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:
ca ≡ cb (mod m) m | (a−b)c, m⇐⇒ c oszthatósággal. Mivel , = 1, ezért d d m m | (a − b), azaz a ≡ b (mod ). d d
A kongruencia de níciója alapján
Legyenek
teljes maradékrendszer
teljes maradékrendszer
m.
Ha
aci ≡ acj
a, b, c
(a, b) | b
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:
(mod m),
(mod m), a ∈ Z (mod m).
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
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
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
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)
mivel (10,21)=1
−2 ≡ 5x (mod 21) 40 ≡ 5x (mod 21) 8 ≡ x (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
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:
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
8. Tétel felhasználásával felírható,
(26 )16 ≡ 1
(mod 7)
296 ≡ 1
(mod 7)
ebb®l:
24 ≡ x (mod 7) 16 ≡ x (mod 7) 2 ≡ x (mod 7) Tehát
2100
7-tel való osztási maradéka
3. Feladat (Forrás: [2.]):
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
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
É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
Ö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
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
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
