Ugrás a tartalomhoz

Számelmélet

dr. Freud Róbert kandidátus, dr. Gyarmati Edit PhD. (2014)

Nemzedékek Tudása Tankönyvkiadó Zrt.

1. fejezet - SZÁMELMÉLETI ALAPFOGALMAK

1. fejezet - SZÁMELMÉLETI ALAPFOGALMAK

Ebben a fejezetben az egész számok oszthatóságával kapcsolatos néhány alapvető fogalmat, tételt és módszert tekintünk át. A fogalmak bevezetésénél legtöbbször csak általános oszthatósági vonatkozásokra építünk, és minél kevesebbet támaszkodunk az egész számok speciális tulajdonságaira. A páros számok és más példák segítségével igyekszünk rámutatni arra is, hogy az egész számoknál „megszokott” tételek egy része, köztük az egyértelmű prímfelbontás (más néven a számelmélet alaptétele) egyáltalán nem magától értetődő.

A felépítés során úgy jutunk el a számelmélet alaptételéhez, hogy a maradékos osztásból kiindulva az euklideszi algoritmus segítségével megmutatjuk a legnagyobb közös osztó „kitüntetett” tulajdonságát, majd ennek alapján igazoljuk, hogy az egész számok körében a felbonthatatlan számok és a prímszámok egybeesnek. Az alaptételre egy, a maradékos osztástól független, közvetlen indukciós bizonyítást is adunk, majd az alaptétel néhány fontos következményét tárgyaljuk.

1.1 Oszthatóság

Ha a és b racionális számok és b0, akkor a-t b-vel elosztva ismét racionális számot kapunk. Hasonló állítás az egész számok körében nem érvényes. Ezért érdemes bevezetni a következő definíciót:

1.1.1 Definíció . D 1.1.1

A b egész számot az a egész szám osztójának nevezzük, ha létezik olyan q egész szám, amelyre a=bq.

Jelölés: ba. Ugyanezt a kapcsolatot fejezi ki más szavakkal, hogy az aoszthatób-vel, illetve az atöbbszöröse a b-nek. Ha nem létezik olyan q egész, amelyre a=bq, akkor a b nem osztója a-nak, ennek jelölése: ba.

A továbbiakban, ha egyéb kikötést nem teszünk, akkor számon mindig egész számot értünk.

A 0 minden számmal osztható (a 0-val is!), hiszen bármely b-re 0=b0. A másik „végletet” azok a számok alkotják, amelyek minden számnak osztói:

1.1.2 Definíció. D 1.1.2

Ha egy szám minden számnak osztója, akkor egységnek nevezzük.

1.1.3 Tétel. T 1.1.3

Az egész számok körében két egység van, az 1 és a 1.

Bizonyítás: Az 1 és a 1 valóban egységek: bármely a-ra ±1a, 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

lehetséges. ∎

Megjegyzés: Az oszthatóságot az egészektől különböző számkörökben (sőt általánosabban bármely integritási tartományban, lásd az 1.1.23 feladatot) be lehet vezetni. Tekintsük példaként a páros számokat. Itt ba azt jelenti, hogy létezik olyan qpáros szám, amelyre a=bq. Ennek megfelelően itt 220, de 210, sőt a 10-nek egyáltalán nincs is osztója. Ebből az is következik, hogy a páros számok körében egyáltalán nincsenek egységek. Ugyanakkor a c+d2 alakú (speciális valós) számok körében, ahol c és d tetszőleges egészek, végtelen sok egység található (lásd az 1.1.22 feladatot). Mindez azt jelenti, hogy az egységek változatos képet mutathatnak, és általában nem (csak) az előjelbeli eltéréssel hozhatók kapcsolatba, mint ahogy azt az T 1.1.3 Tétel esetleg tévesen sugallhatná.

1.1.4 Tétel . T 1.1.4

Ha ε és δ egységek és ba, akkor εbδa is teljesül.

Bizonyítás: Az ε az 1-nek is osztója, azaz alkalmas r-rel 1=εr. Ha a=bq, akkor δa=(εb)(δqr), tehát valóban εbδa. ∎

Az T 1.1.4 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 (majd) 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 (a 0 speciális szerepének tisztázása után) csak a pozitív egészekkel foglalkozunk.

A következő tételben az egész számok oszthatóságának néhány egyszerű, de fontos tulajdonságát foglaljuk össze.

1.1.5 Tétel . T 1.1.5

(i) Minden a-ra aa.

(ii) Ha cb és ba, akkor ca.

(iii) Az ab és ba oszthatóságok egyszerre akkor és csak akkor teljesülnek, ha az a a b-nek egységszerese.

(iv) Ha ca és cb, akkor ca+b, cab, tetszőleges (egész) k-ra cka, és tetszőleges (egész) r, s-re cra+sb.

Az (i)–(iii) tulajdonságok rendre azt fejezik ki, hogy az egész számok oszthatósága reflexív és tranzitív, de nem szimmetrikus reláció. A (iv)-beli állítások közül a legtöbbször az első hármat alkalmazzuk, ezek egyébként valamennyien az utolsónak speciális esetei (r=s=1; r=1, s=1; illetve r=k, s=0).

Bizonyítás: Csak (iii)-at igazoljuk, a többi könnyen bizonyítható az oszthatóság definíciójából.

Ha a=εb, ahol ε egység, akkor ba azonnal adódik. Továbbá 1=εr miatt ra=b, tehát ab is teljesül.

Megfordítva, ha ab és ba, azaz alkalmas q és s egészekkel b=aq és a=bs, akkor innen b=b(qs). Ha b=0, akkor szükségképpen a=0, tehát a=εb. Ha b0, akkor qs=1, azaz s (és q is) egység, tehát ekkor is a=εb. ∎

Feladatok

(Ha más kikötést nem teszünk, a feladatokban értelemszerűen egész számok szerepelnek, a hatványkitevők pedig nemnegatív egészek.)

1.1.1 Írjunk le egy háromjegyű számot kétszer egymás mellé. Mutassuk meg, hogy az így kapott hatjegyű szám osztható 91-gyel.

1.1.2 Lássuk be, hogy két páratlan szám négyzetének a különbsége mindig osztható 8-cal.

1.1.3 Tegyük fel, hogy az (a,b,c számjegyekből álló) abc¯ háromjegyű szám osztható 37-tel. Igazoljuk, hogy ekkor a bca¯ szám is osztható 37-tel.

1.1.4 Bizonyítsuk be, hogy ha 5a+9b osztható 23-mal, akkor 3a+10b is osztható 23-mal.

1.1.5 Melyek igazak az alábbi állítások közül?

(a) ca+bca,cb.

(b) ca+b,cacb.

(c) ca+b,cabca,cb.

(d) c2a+5b,c3a+7bca,cb.

(e) cabca vagy cb.

(f) ca,dbcdab.

(g) ca,dacda.

1.1.6  Igazoljuk az alábbi oszthatóságokat:

(i) abanbn;

(ii) a+ba2k+1+b2k+1;

(iii) a+ba2kb2k.

1.1.7  Mely c egészekre lesz (c63)(c2+2) is egész szám?

1.1.8  Igazoljuk, hogy minden n természetes számra 13311n+2+122n+1.

1.1.9  Adjunk meg végtelen sok olyan n-et, amelyre 292n+5n.

1.1.10  Mutassuk meg, hogy (b1)2bk1 akkor és csak akkor teljesül, ha b1k.

1.1.11  (*) Tegyük fel, hogy 2b12a+1. Lássuk be, hogy b=1 vagy 2.

1.1.12  Bizonyítsuk be az alábbi állításokat.

(a) Ha ba és a0, akkor |b||a|.

(b) Minden nemnulla egész számnak csak véges sok osztója van.

1.1.13  Melyek azok a számok, amelyek felírhatók (a) két; (b) három (nem feltétlenül különböző) pozitív osztójuk összegeként?

1.1.14  Igazoljuk, hogy egy (tízes számrendszerben felírt természetes) szám akkor és csak akkor osztható

(a) 3-mal, illetve 9-cel, ha a számjegyeinek az összege osztható 3-mal, illetve 9-cel;

(b) 4-gyel, illetve 25-tel, ha az utolsó két számjegyéből álló szám osztható 4-gyel, illetve 25-tel;

(c) 8-cal, illetve 125-tel, ha az utolsó három számjegyéből álló szám osztható 8-cal, illetve 125-tel;

(d) 11-gyel, ha a számjegyeinek váltakozó előjellel vett összege osztható 11-gyel.

1.1.15  Létezik-e 2-nek olyan pozitív egész kitevős hatványa, amelyben mind a tíz számjegy ugyanannyiszor fordul elő?

1.1.16  (*) Létezik-e olyan szám, amelyben csak az 1 és 2 számjegyek fordulnak elő, és amely osztható 21000-rel?

1.1.17  Mutassuk meg, hogy

(a) három szomszédos egész szám szorzata osztható 6-tal;

(b)k szomszédos egész szám szorzata osztható k!-sal.

1.1.18 (M) Legyen n>1 tetszőleges egész. Csongor megnevezi n-nek egy tetszőleges pozitív osztóját, legyen ez d1. Ezután Tünde választ egy d2 pozitív osztót, amely nem lehet osztója d1-nek. Ismét Csongor választ egy d3-at, amely nem osztója sem d1-nek, sem d2-nek stb. Az veszít, aki magát az n-et kénytelen választani. Kinek van nyerő stratégiája, ha n értéke

(a) 16;

(b) 31111;

(c) 10;

(d) 50;

(e)123456789101112131415?

1.1.19  (*) Válasszunk ki az 1,2,,2n számok közül tetszőlegesen n+1 darabot. Igazoljuk, hogy a kiválasztott számok között biztosan lesz két olyan, hogy az egyik a másiknak osztója.

1.1.20  Mi az oka annak, hogy noha a 00oszthatóság igaz, a 00osztásnak még sincs értelme?

1.1.21  A páros számok körében melyek azok az elemek, amelyeknek

(a) egyáltalán nincs osztója;

(b) pontosan két (pozitív vagy negatív) osztója van?

1.1.22  Tekintsük oszthatósági szempontból a c+d2 alakú (speciális valós) számokat, ahol c és d tetszőleges egészek.

(a) Döntsük el, hogy 1272 osztható-e 3+42-vel.

(b) Igazoljuk, hogy az 1+2 egység.

(c) Mutassuk meg, hogy végtelen sok egység van.

(d) Hány osztója van egy tetszőleges elemnek?

(e) Lássuk be, hogy c+d2 akkor és csak akkor egység, ha |c22d2|=1.

(f) M* Bizonyítsuk be, hogy az egységek éppen a ±(1+2)k alakú elemek, ahol k tetszőleges egész.

(g) Hányszor fordul elő az egész számok körében, hogy egy négyzetszám kétszerese eggyel nagyobb, illetve eggyel kisebb egy (másik) négyzetszámnál?

1.1.23  Integritási tartománynak a (legalább kételemű) kommutatív, nullosztómentes gyűrűket nevezzük, azaz amelyekben az összeadás és a szorzás kommutatív és asszociatív, van nullelem, minden elemnek van ellentettje, érvényes a disztributivitás, és két nemnulla elem szorzata sem lehet nulla. (Ez pongyolán fogalmazva azt jelenti, hogy az összeadás, kivonás és szorzás tekintetében az egész számoknál megszokott „szép” tulajdonságok teljesülnek.) Vezessük be az oszthatóságot és az egység fogalmát az D 1.1.1 és D 1.1.2 Definíciók szerint, és lássuk be az alábbiakat.

(a) M Akkor és csak akkor létezik egység, ha a szorzásnak létezik egységeleme (azaz olyan e elem, amelyre bármely a-val ea=a teljesül).

(b) Az egységek éppen az egységelem osztói, illetve más megfogalmazásban azok az elemek, amelyeknek (a szorzásra nézve) létezik inverze.

(c) Egy egység minden osztója és két egység szorzata is egység.

(d) Vizsgáljuk meg az T 1.1.5 Tétel állításait.