Matematika | Felsőoktatás » Farkas Mariann - Nevezetes számelméleti függvényekről

NEVEZETES SZÁMELMÉLETI FÜGGVÉNYEKRŐL SZAKDOLGOZAT Készítette: Farkas Mariann Matematika BSc Tanári szakirány Témavezető: Pappné Dr. Kovács Katalin, egyetemi docens Algebra és Számelmélet Tanszék Eötvös Loránd Tudományegyetem Természettudományi Kar Budapest, 2011 Tartalomjegyzék Bevezetés . 2 1. Alapfogalmak 3 2. A függvény . 5 A függvény néhány értéke . 6 Alkalmazása. 7 Feladatok . 9 3. A függvény . 13 A függvény néhány értéke . 15 Alkalmazása. 16 Feladatok . 17 4. A függvény . 22 A függvény néhány értéke . 24 Alkalmazása. 25 Feladatok . 26 5. A függvény . 29 A függvény néhány értéke . 30 Alkalmazása. 31 Feladatok . 31 6. Vegyes feladatok 33 7. Hegy- és völgytételek 35 Irodalomjegyzék . 38 1 Bevezetés Dolgozatomban négy nevezetes számelméleti függvényről lesz szó . Az ezekről tanult ismereteket foglalom össze, alkalmazással, és feladatokkal kibővítve. Leendő tanárként

fontosnak tartom a feladatmegoldást, ezzel sokszor kézzelfoghatóbbá válik az ismeretanyag, könnyebb az elsajátítása, továbbá gondolkodásra sarkall, gyarapodik ötlettárunk a problémamegoldás terén. Az utolsó fejezetben a fent említett függvények hegy- és völgytételeiből mutatok be egy részt a teljesség igénye nélkül. Célom, hogy dolgozatom jó kiindulópont legyen a téma iránt érdeklődőknek, felhasználható legyen középiskolában az emelt óraszámú matematika csoportok oktatásánál, illetve szakkörökön. Ezúton szeretném megköszönni témavezetőmnek, Pappné Dr. Kovács Katalinnak a sok segítséget, ötletet és támogatást, amelyet a szakdolgozatom megoldásához nyújtott. 2 1. Alapfogalmak 1.1 Definíció:[9] Függvényen halmazok közötti egyértelmű hozzárendelést értünk Az -hez hozzárendelt elemet -szel jelöljük. Ha és tetszőleges halmazok, akkor egy olyan függvény, melyre esetén az függvény értelmezési

tartomány, azaz hozzárendel valamit}, -hez ami az . egy részhalmaza. Az az függvény értékkészlete, mely -nak részhalmaza és { valamely -re}. A függvények egy részhalmazát alkotják a számelméleti függvények. Az alábbi definíciók és tételek a számelmélet jegyzetből és [3] könyvből valók. 1.2 Definíció: Számelméleti függvényeknek nevezzük azokat a függvényeket, amelyek értelmezési tartománya a pozitív egész számok halmaza, értékkészlete pedig a komplex számok egy részhalmaza. Jelöléssel: 1.3 Definíció: Az számelméleti függvény i. multiplikatív, ha ii. teljesen multiplikatív, ha 1.1 Tétel: Ha esetén esetén multiplikatív, és nem azonosan 0, akkor Bizonyítás: Legyen létezik olyan , melyre 1.4 Definíció: Az , . . , ahol egy tetszőleges pozitív egész szám. . Ezt -val egyszerűsítve kapjuk, hogy , akkor kész, és miatt . Ha nem azonosan 0. számelméleti függvény i. additív, ha ii.

teljesen additív, ha esetén esetén , . 3 1.2 Tétel: Ha additív, akkor Bizonyítás: Legyen . egy tetszőleges pozitív egész szám. Ekkor miatt . Mindkét oldalból . -t elvéve kapjuk, hogy 1.3 Tétel: Legyen i. multiplikatív, ii. additív számelméleti függvény, és az szám kanonikus alakja Ekkor i. ( ) ( ii. ( ) Bizonyítás: A ) ( ( ), ) . számok páronként relatív prímek, így a multiplikativitás és additivitás definíciójából következik a tétel. 1.4 Tétel: Legyen i. teljesen multiplikatív, ii. teljesen additív számelméleti függvény, és az szám kanonikus alakja Ekkor i. ii. . Bizonyítás: Az előző tételből a teljesen additív/multiplikatív definícióját felhasználva következik. 4 függvény 2. A 2.1 Definíció: 2.1 Tétel:[3] Legyen az i. Egy ,, Ekkor az Bizonyítás: Ha legfeljebb szám általánosított kanonikus alakja pozitív egész pontosan akkor osztja az ahol ii.

természetes szám pozitív osztóinak számát értjük. -en az számot, ha kanonikus alakja . szám pozitív osztóinak száma , tehát , akkor hatványon, prímek szerepelnek . Ha , akkor , így kanonikus alakjában csak a , tehát , és mivel miatt egész szám és . szám összes pozitív osztóját megkapjuk a Ahhoz, hogy az kifejezésben kell jól megválasztani a függetlenül felveszik a választhatok meg. A kitevőket. Minden -re igaz, hogy egymástól értékeket, tehát minden -t -képpen ezen számok szorzataként áll elő. Példa: , ekkor az osztói, az Legyen Képlettel: 3, számok, tehát . . Tulajdonságok:   esetén Ha . prím, vagyis , akkor , hiszen egy prímszámnak csak 2 osztója van, 1 és önmaga.  Ha prímhatvány, vagyis , akkor , mivel az osztói az . 2.2 Tétel: A függvény multiplikatív. Bizonyítás: Azt kell belátnunk, hogy ha , akkor . 5 és Legyen az prímtényezős felbontása a

következő: különböző prímek. ahol prímtényezős felbontása: Ekkor az A függvény képletét alkalmazva: Példa: -re Megjegyzés: A függvény nem teljesen multiplikatív. Ennek igazolásához elég egy példát mutatni. Példa: -ra függvény néhány értéke: A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 2 6 2 6 6 6 5 4 3 2 1 0 0 1 2 3 4 Értékkészlete: A 5 6 7 8 9 függvény minden pozitív egész számot felvesz végtelen sokszor, kivéve az -et, melyet csak egyszer az hogy 10 11 12 13 14 15 16 17 18 19 20 , ahol és helyen. Ez következik abból a tulajdonságából, prím tetszőlegesek. Alkalmazása: Diofantikus problémák függvény lesz a segítségünkre abban, hogy meghatározzuk, az alábbi diofantikus A egyenletnek hány megoldása van. Tekintsük a következő egyenletet: ahol egy rögzített pozitív egész szám. Az megoldásokat keressük.

nevezetes azonosság felírható Az alakban. Az kifejezések paritása megegyezik, mivel A kérdés, hogy milyen a) és . esetén lehet az egyenletnek megoldása? páratlan Hányféleképpen írható fel az szám számok? Két eset lehetséges, az elsőben alakban, ahol és és is páratlan pozitív egész számok, a másodikban azonban negatív egész számok, vagyis minden osztópár jó lesz. Bármelyik felírásnál megoldása van az egyenletnek, így összesen megoldás adódik. Példa: 7 1 15 8 7 15 1 8 -7 3 5 4 1 5 3 4 -1 -1 -15 -8 -7 -15 -1 -8 7 -3 -5 -4 -1 -5 -3 -4 1 b) Mivel pozitív egész szám, ezért megoldások száma vagyis összesen és is páros szám kell, hogy legyen. Ekkor a osztóinak a száma, a pozitív és negatív eseteket is számolva, ( ) Példa: 2 4 3 1 4 2 3 -1 -4 -2 -3 1 -2 -4 -3 -1 8 Feladatok: 2.1 Feladat:[7] Igazoljuk, hogy Megoldás: 〈 〉 〈 szám Az 〉 〈

összes osztójából párokat Ezek legyenek , ahonnan a . A √ . Vagyis a párok száma legfeljebb √ legfeljebb a párok számának kétszeres, azaz √ . Innen kapjuk, hogy négyzetmentes, akkor pontosan 2.2 Feladat: Mely alkotunk. 〉. Feltehetjük, hogy minden esetben -t alakítva kapjuk, hogy Megjegyzés: Ha √ ! darab osztója van, különben . természetes számokra teljesül, hogy a) , b) ? Megoldás: a) Először írjuk fel az , és a kanonikus alakját: , ahol Ezután a képlet segítségével megkapjuk -t és . -t: Ezeket helyettesítsük be az eredeti egyenletbe: Az egyszerűsítés után azt kapjuk, hogy: Vagyis a képletet azok a számok elégítik ki, amelyek prímtényezős felbontásában nem szerepel a 3. b) Hasonló módon járunk el itt is. A kanonikus alakok: Írjuk fel -t és -t, majd tegyük őket egyenlővé, és oldjuk meg az egyenletet: 9 Tehát az egyenlet gyökei azok a számok, amelyek prímtényezős

felbontásában a 2 és a 3 azonos hatványkitevőn szerepelnek. 2.3 Feladat:[7] Mely természetes számokra teljesül, hogy Megoldás: Az előbbi feladat mintájára írjuk fel az és az ? kanonikus alakjait: Innen kapjuk, hogy: Az egyenletünk: Átrendezve: , akkor a bal oldal 1 lenne, tehát létezik olyan Ha minden , mely nagyobb, mint 0. Ekkor az egyenlet bal oldalán minden tört értéke nagyobb vagy egyenlő, mint 1. Tehát lehet csak. Több oldalán legalább nem lehet 0-tól különböző, mert akkor az egyenlet bal szerepelne, a többi tényező pedig legalább 1, ami ellentmond a -nek. Tehát valamelyik és a többi 0, azaz prímszám. 10 2.4 Feladat: Milyen természetes számokra igaz, hogy Megoldás: Tudjuk, hogy ? √ , tehát rendezés után kapjuk, hogy √ . Négyzetre emelés és nullára . A másodfokú egyenletet megoldva kapjuk, . Ezekre az -ekre ellenőrizve kapjuk, hogy hogy 2.5 Feladat:[7] Keressük meg a legkisebb a) , b) ,

c) . Megoldás: Minden esetben az . természetes számot, melyre szám kibővített kanonikus alakja , és a) A képletbe helyettesítve: ezért valamelyik . Mivel 23 prímszám, tényező egyenlő 23-mal és , a többi 0. Azonos kitevőjű hatványok közül az a legkisebb, ahol a hatványalap is legkisebb. Így a legkisebb természetes szám, ami megoldást ad az . . Itt két esetet kell vizsgálnunk b) Az előző mintájára: a szorzattá alakítás szerint:  Ekkor az a) esethez hasonlóan járunk el, így -et kapunk.  Itt a legjobb eset, mikor , ahonnan és . A két eset közül az utóbbi adja a helyes megoldást. esetben c) Az szintén esetszétválasztást alkalmazunk. Az eredményeket táblázatba foglalom: Szorzatalak Kanonikus alak és konkrét érték 11 A megoldás: . 12 függvény 3. A 3.1 Definíció: szám pozitív osztóinak összegét értjük. -en az 3.1 Tétel:[3] Legyen az szám általánosított kanonikus alakja Ekkor

az szám pozitív osztóinak összege ( )( ) ( ) ∏ Bizonyítás: Már az előzőekben láttuk, hogy összes osztója előáll alakban, ahol egymástól függetlenül minden Másrészt -re felveszi a számokat. minden osztója előáll ilyen alakban, és mindegyik csak egyféleképpen, tehát ezen -k összege, az szám összes osztóinak összege, azaz . Ha a ∏ szorzást elvégezzük, akkor is az előbbi összeget kapjuk. Például a úgy keletkezik, ha ∏ -ket, ahol -ből minden szorzat tagból összeszorzom a . A ∏ úgy adódik, hogy az első képletre alkalmazzuk a mértani sorozat összegképletét. Példa: Legyen , ekkor az osztói, az számok. Ezek összege: . Képlettel: 13 Tulajdonságok:   esetén Ha . prím, vagyis , akkor ez következik a prímszám definíciójából.  Ha prímhatvány, vagyis 3.2 Tétel: A függvény multiplikatív. Bizonyítás: Azt kell belátnunk, hogy ha Legyen az és Ekkor az Példa: , akkor .

prímtényezős a felbontása a következő: különböző prímek. ahol A akkor prímtényezős felbontása: függvény képletét alkalmazva kapjuk, hogy: -re Megjegyzés: A függvény nem teljesen multiplikatív. 14 Példa: -ra függvény néhány értéke: A 1 2 3 4 5 6 7 1 3 4 7 6 12 8 8 9 10 11 12 13 14 15 16 17 18 19 20 15 13 18 12 28 14 24 24 31 18 39 20 42 45 40 35 30 25 20 15 10 5 0 0 2 4 6 8 10 12 14 16 18 20 15 Alkalmazása: A tökéletes számok 3.2 Definíció: Az pozitív egész számot tökéletes számnak nevezzük, ha egyenlő a nála kisebb pozitív osztóinak összegével, vagyis Például: esetén: esetén: 3.3 Tétel: Az szám pontosan akkor tökéletes, ha felírható prímszám és 3.4 Tétel: A osztható összetett szám. is nagyobbak 1-nél. Ekkor , ahol -gyel és Következmény: Ha 3.3 Definíció: Ha A is prímszám. nem prímszám, ha Bizonyítás: Mivel névadó Marin alakban, ahol miatt .

prím, akkor n is prím. prím, akkor azt Mersenne-prímnek hívjuk. Jelölése: Mersenne (1588-1648) megállapítása, hogy prím, de minden más ha számra összetett. Állítását nem igazolta. Az 1588-ig az első 7 eset már ismert volt A -et 1772-ben Euler igazolta. Az első hibát a listában 1876-ban Lucas fedezte fel, miszerint a összetett szám. Később további hibákat is felfedeztek 1883-ban Pervushin kiegészítette a felsorolást a számmal, majd Powers is még kettővel, a (1914). 1947-re derült ki, hogy -gyel (1911) és a -gyel is összetett szám, így a helyes lista Jelenleg 47 Mersenne-prímet ismerünk. A legújabb felfedezések: 16  A 45.-et 2008 augusztus 23-án találták meg Ez a alakú szám, mely 12 978 189 számjegyből áll. Ez a ma ismert legnagyobb prímszám is  A 46.-at nem sokkal az előző után, 2008 szeptember 6-án fedezték fel Ez, az előzőnél kisebb, 11 185 272 számjegyet számláló  szám. A 47.

megtalálására 2009 április 12-én került sor A szám 12 837 064 darab számjegyével a második legnagyobb jelenleg ismert prímszám.[10],[13] A páros tökéletes számok egy kettő hatvány és egy Mersenne-prím szorzataként állnak elő. A matematika egyik legrégebbi nyitott kérdése, hogy léteznek-e páratlan tökéletes számok. A témában számos eredmény született, de mindmáig nem sikerült ilyen számot találniuk és cáfolni a létezésüket. Bármelyik páratlan tökéletes számnak ki kell elégítenie a következő feltételeket:  . Egy kutatásban próbaképpen megmutatták, hogy , de bebizonyítani még nem tudták.  különböző prímek,és , ahol .  Az szám legnagyobb prímtényezője nagyobb, mint .  A második legnagyobb prímtényezője nagyobb, mint .  A harmadik legnagyobb prímtényezője nagyobb, mint 100.   -nek legalább 75 prímtényezőből áll, amiben van legalább 9 különböző. Ha a 3 nem

szerepel prímtényezős felbontásában, akkor -nek van legalább 12 különböző prímtényezője.[11] Feladatok: 3.1 Feladat: Bizonyítsuk be, hogy bármely páros tökéletes szám utolsó számjegye 6 vagy 8 Megoldás: A páros tökéletes számok táblázatot alakúak, ahol prímszám. Készítsünk különböző értékeihez. Mivel a 10-es számrendszerben vizsgálódunk, ezért nézzük az értékeket, hiszen ez adja meg a szám utolsó számjegyét. 17 1 1 1 1 2 2 3 6 3 4 7 8 4 8 5 0 5 6 1 6 6 2 3 6 7 4 7 8 8 8 5 0 9 6 1 6 10 2 3 6 11 4 7 8 , és átalakítva , ha , ugyanis . Mivel 2 és 5 relatív prímek, így , azaz , ha , tehát a értékei már ismétlődnek, A kettő hatványokhoz hasonlóképp ismétlődnek a eggyel kisebb számok azoknál. Emiatt esetén , -tól négyesével értékei is, mivel ezek utolsó számjegyei is periodikusak. Minden páratlan 6-ra vagy 8-ra végződik, így minden páratlan

prímszám esetén is. -re , tehát bebizonyítottuk, hogy minden páros tökéletes szám utolsó számjegye 6 vagy 8. 3.2 Feladat: Mennyi egy tökéletes szám pozitív osztóinak reciprokösszege? Megoldás: Az pozitív osztói: , ahol és osztópárok. A kérdés, hogy mennyi a következő összeg értéke: A kifejezést alakítsuk át úgy, hogy közös nevezőre hozzuk a törtet, mivel minden tört nevezője -nek egy osztója, és az összes pozitív osztót felsoroltuk, így a legkisebb közös többszörösük, az szám lesz a közös nevező. 18 A számlálóba ekkor minden szám osztópárja kerül. Amennyiben van, tehát létezik számlálóba , melynek nincs osztópárja, vagyis -nek páratlan sok osztója √ , akkor összes osztója kerül, amiről tudjuk, hogy az összege √ . Így a . Tehát a reciprokösszeg: 3.3 Feladat:[7] Mutassuk meg, hogy végtelen sok természetes számra a egyenletnek a) legalább 2, b) legalább 3 megoldása van!

Megoldás: A függvény multiplikatív tulajdonságát használjuk ki, azaz ha akkor , . és a) Ha . És mivel végtelen sok , akkor prímszám van, így létezik végtelen sok is, amely kielégíti az egyenletet. Például, a táblázatból látható, hogy . Legyen , ekkor a is egy jó megoldás. b) Az a) részhez hasonlóan járunk el. Ha és , akkor . Például, tudjuk, hogy . Legyen , ekkor a is jó megoldást ad. 3.4 Feladat: Mely természetes számokra páratlan értéke? Megoldás: A következő képletet használjuk fel: ∏ Ez akkor páratlan, ha minden tényezője is az. Esetszétválasztással vizsgáljuk a szorzat tényezőit. 1) Ha , akkor a 2) Ha . hányados páratlan. A képletet alakítsuk át a következő módon: 19 kifejezésben minden tag páratlan. Az összeg paritása A csak -tól függ. Ha páros, akkor az összeg páratlan tagú, így értéke is páratlan, ha, páratlan, akkor az összeg páros sok tagból áll, ezért az

értéke is páros. Ez alapján azok a számok elégítik ki a feladatot, amelyek négyzetszámok, vagy egy négyzetszám kétszeresei. 3.5 Feladat: Mely Megoldás: A Felírjuk és természetes számokra teljesül, hogy ? függvény képletét használjuk fel a megoldás során. kibővített kanonikus alakját, majd behelyettesítjük őket a képletbe: Ezek segítségével felírhatjuk az egyenletünket: Egyszerűsítés után: . Tehát azon -ekre teljesül az egyenlet, ahol ahonnan az eredmény 3.6 Feladat: Keressük meg azt az páratlan szám. természetes számot, melyre a) b) Megoldás: a) A b) , tehát miatt lehet, ahonnan jó. legfeljebb 9 lehet. 1-től 9-ig ellenőrizve -t arra jutunk, hogy a feladatnak nincs megoldása. 20 3.7 Feladat: Mely természetes számokra teljesül, hogy a) b) ? Megoldás: a) Mivel 1 és osztja -et, ∑ tehát ∑ , ez viszont ellentmondás, tehát nincs megoldás. b) Az a) feladathoz hasonlóan ∑ csak. Így , tehát

lehet 1-nél nagyobb természetes szám, mely nem prímszám, vagy prímszám négyzete, akkor hogy ahonnan . 3.8 Feladat:[7] Bizonyítsuk be, hogy ha Megoldás: Legyen osztói: 1, 2, √ . legkisebb prímosztója . Ekkor √ . Azt kell belátni, . Vizsgáljuk ezt az egyenlőtlenséget: √ √ √ Ez mindig igaz a számtani és mértani közép közti egyenlőtlenség miatt. Ezzel beláttuk a feladatot. 21 függvény 4. A 4.1 Definíció: -ban az -hez relatív prímek számát értjük. -en az 4.1 Tétel:[3] Legyen Ekkor az -hez relatív prímek kanonikus alakja száma ( )( ) ( ) A képlet egyéb formái: ∏( ) ∏ ∏( ) ∏ ( ) Bizonyítás: A logikai szitaformulát használjuk fel hozzá. A cél, hogy kiszámítsuk, hány olyan szám van az egészek között, amelyek relatív prímek az -hez. Ez azt jelenti, hogy nem oszthatók a Azoknak a számoknak a száma, amelyek egy rögzítetett prímek egyikével sem. -vel oszthatók: Vegyük most

azokat, amelyek több prímmel is oszthatóak. Egy egész pontosan akkor osztható adott prímek mindegyikével, ha a szorzatukkal is osztható. Például ha egy szám osztható -vel és -val is, akkor osztható a szorzatukkal, vagyis -val is. Ezek alapján felírhatjuk a logikai szitaformulát: A képlet jobb oldala egyenlő ∏( ) szorzattal, mely számolással ellenőrizhető, és ez a tételben szereplő képlet egy formája. Példa: Legyen Képlettel: , ekkor a hozzá relatív prímek, az számok. . 22 Tulajdonságok:  esetén .  Ha prím, vagyis  Ha prímhatvány, vagyis 4.2 Tétel: A , akkor . akkor . függvény multiplikatív. Bizonyítás: [5] A következő képletet kell belátni: ha Táblázatba írjuk az 1 és . közti számokat a következőképpen: 1 2 Azoknak a számoknak a száma, amelyek -hez relatív prímek: Egy szám akkor és csak akkor relatív prím az . -hez, ha külön az -hoz és külön a -hez is relatív prím.

Így azokat az elemeket kell kikeresni a táblázatból, amelyek -hoz is és -hez is relatív prímek. A táblázat minden egyes oszlopa ugyanabba a maradékosztályba tartozik , és minden egyes sora teljes maradékrendszert alkot oszlopoknak a száma, amelyek elemei relatív prímek -hoz: , tehát azoknak az . Például egy ilyen oszlop: Azt kell még belátni, hogy ez teljes maradékrendszert alkot A számok teljes maradékrendszert alkotnak szerint is. -re nézve. Feltettük, hogy , így az előbbi számokat -val szorozva, majd mindegyikhez -t hozzáadva, újfent teljes maradékrendszert kapunk -hez relatív prímek száma: ([3] 2.24 Tétele alapján) Tehát minden oszlopban a . Ezek alapján az -hoz is és -hez is relatív prímek száma: , ez az érték a fentiek alapján egyenlő -vel, tehát a függvény multiplikatív. 23 Példa: -re függvény nem teljesen multiplikatív. Megjegyzés: A Példa: -ra függvény néhány értéke: A 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 20 18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18 20 24 Alkalmazása: Maradékosztályok, maradékrendszerek, az Euler – Fermat-tétel 4.2 Definíció: Adott modulusra azonos maradékot adó számok halmaza egy maradékosztály. Jelölése az -val kongruens elemek halmazára modulus mellett: . } Példa: 4.3 Definíció: Adott modulusra a teljes maradékrendszer olyan számhalmaz, amely minden maradékosztályból pontosan egy elemet tartalmaz. } teljes maradékrendszer Példa: 4.4 Definíció: Adott . modulusra a redukált maradékosztály olyan maradékosztály, amelynek elemei -hez relatív prímek. 4.5 Definíció: Adott modulusra a redukált maradékrendszer olyan számhalmaz, amely minden redukált maradékosztályból pontosan egy elemet tartalmaz. } redukált maradékosztály Példa: 4.3 Tétel: Az . számok pontosan akkor alkotnak redukált

maradékrendszert , ha (1) (2) , páronként inkongruensek, (3) Minden -re, ahol 4.5 Tétel (Euler – Fermat-tétel): Ha . , és , akkor 25 Feladatok: 4.1 Feladat:[7] Milyen Megoldás: Az pozitív egészekre igaz a kibővített kanonikus alakja és vizsgálunk, mivel  egyenlet? , másképp , ahol . A megoldás menete során különböző eseteket kiszámításánál a kanonikus alak használható csak. Tegyük fel, hogy A multiplikatív tulajdonsága miatt ez átalakítható a következőképp: Ezt Ebből -szel egyszerűsítve, és a képletbe behelyettesítve kapjuk, hogy: -at kapunk eredményül, ami ellentmondás, tehát az esetben nincs megoldása az egyenletnek.   Legyen Ekkor , ahol Legyen . Ekkor tehát  , ami ellentmondás. , azaz , ahol , vagyis , ami ellentmondás. Legyen Ekkor , ahol , azaz ami igaz. Tehát ebben az esetben van az egyenletnek megoldása, és azon számok elégítik ki, ahol , ahol 4.2 Feladat:[7]

Oldjuk meg a Megoldás: A feladat megoldásához a és egyenletet! következő képletét használjuk fel: ∏( ahol . ) prím. Ezt behelyettesítjük az eredeti egyenletbe 26 ∏( ) ∏( ) ∏( ) Ez pontosan akkor teljesül, ha a prímtényezős felbontásban csak a 2 szerepel. Vagyis az alakú számok lesznek jók, ahol . 4.3 Feladat:[3] Bizonyítsuk be, hogy Megoldás: A feladat menete során esetén értéke páros szám! egyik képletét használjuk: ∏(  Ha az ) prímtényezős felbontásában van páratlan , akkor annak hatványai is páratlanok. Két páratlan szám különbsége páros, tehát  Ha nincs páratlan alakú, ahol , akkor ami páros, mert . Ekkor . 4.4 Feladat:[7] Melyek azok a természetes számok, amelyekre Megoldás: Az előző feladatban láthattuk, hogy ellenőrizni az   és is páros. értéke páratlan? esetén páros lesz. Így elég esetet. A függvény tulajdonsága, hogy esetén , tehát páratlan.

-t helyettesítve: ez szintén páratlan. Így mindkét eset jó megoldást ad. 4.5 Feladat:[7] Oldjuk meg a Megoldás: Mivel szám lehet. Legyen az egyenletet! , vagyis nem prímszám, és legkisebb prímosztója . Ekkor biztosan , ezért csak összetett √ . 27 Indirekt tegyük fel, hogy √ és mivel √ , vagyis √ , továbbá relatív prím -ig, tehát . Ebben az esetben , . Így -hez van három nem , ahol , ami ellentmondás. és összetett szám, azaz csak a 4, 6 vagy 8 lehet. Ezeket behelyettesítve A fentiek miatt képletébe kapjuk, hogy az egyetlen jó megoldás az 4.6 Feladat: Mely . természetes számokra lesz a) , b) ? Megoldás: ∏ a) Ha alapján , mely sosem egyenlő 9-cel, tehát nincs ilyen , akkor ∏ b) A csak 2 lehet, hogy a szorzat páratlan legyen. -ből következik, hogy és , így -ból kitevői rendre . lehet. Legyenek ezek alapján . A szám. . Mivel 4 nem osztja 18-at ezért -nek nem lehet két

különböző páratlan prímosztója. Tegyük fel, hogy ∏ . Mivel nem mind 0. Ekkor szorzatban van legalább két páros tényező, ami azt jelentené, hogy , ami ellentmondás, tehát sem az nem jó, ezért , sem az . Tegyük fel, hogy nem jó, tehát . Ezek közül a 27 és a 19 ad jó megoldást . . Ekkor azonban esetén esetén vagy vagy , amelyekből 54 és 38 lesz jó. 28 függvény 5. A 5.1 Definíció:[3] A  függvényen az alábbi számelméleti függvényt értjük: , ha  , , ha az  ha 5.1 Tétel: A , vagyis az , melyre szám négyzetmentes, , vagyis az szám nem négyzetmentes. ha . függvény multiplikatív. Bizonyítás: A következő képletet kell belátni: Esetszétválasztással dolgozunk. 1. : Triviális. 2. , : Ekkor a , tehát , igaz. Szimmetria okok miatt ugyanígy igaz, ha 3. , , így , Ugyanez igaz, a , . esetre is. , 4. : Definíció szerint , ezért , Az miatt 5. , , . : Vagyis ,

nem négyzetmentes, így Ugyanez igaz a 6. . : Tehát Mivel és , Tehát sem lesz az, tehát , . esetre is. : . És mivel sem az szorzatuk sem lesz az, vagyis sem a nem négyzetmentes, így a . Ezzel az a tételt beláttuk. 29 Példa: -re függvény nem teljesen multiplikatív. Megjegyzés: A Példa: -ra függvény néhány értéke: A 1 2 3 4 5 6 7 8 9 10 1 -1 -1 0 -1 1 -1 0 0 1 11 12 13 14 15 16 17 18 19 20 -1 0 -1 1 1 0 -1 0 -1 0 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 -1 30 Alkalmazása: A primitív -edik egységgyökök összege 5.2 Tétel: A primitív -edik egységgyökök összege . Bizonyítása:[8] A tétel igazolásához a gyökök és együtthatók közti összefüggést használjuk fel. Jelöljük -nel a primitív -edik egységgyökök összegét, melyek a , az -edik körosztási polinom gyökei. A gyökök és együtthatók összefüggése miatt egyenlő az

együtthatójának ellentettjével. Továbbá [4] 395 lemma szerint, ha ∏ . Az -es tag együtthatóját vizsgáljuk mindkét oldalon. A jobb oldalon ez az érték 0, kivéve, ha meg az , mert abban az esetben . A bal oldalon úgy kapjuk -es tagot, ha egy polinomból a második legmagasabb fokút, a többiből pedig a legmagasabb fokút vesszük. így , akkor -ben a második legmagasabb fokú tag együtthatója együtthatója az összes , összege lesz. Ezek alapján felírható, hogy ∑ { ∑ { A [3] 6.24 Tétele alapján: A 6.52 Tétele szerint a számelméleti függvényekre a függvény – összegzési függvény kölcsönösen egyértelmű megfeleltetés, így . Feladatok: 5.1 Feladat:[3] Hány egymást követő szám adható meg, hogy Megoldás: A függvény abban az esetben 0, ha azok egyikén sem nulla? nem négyzetmentes. Mivel bármelyik négy szomszédos szám között található egy, amelyik osztható 4-gyel, ezért legfeljebb három szám

adható meg. 5.2 Feladat:[3] Hány egymást követő szám adható meg, hogy azok mindegyikén nulla legyen? Megoldás: Azt kell belátni, hogy tetszőleges nagy természetes szám, hogy természetes számhoz található olyan . 31 Tekintsük a következő szimultán kongruenciarendszert, ahol jelölje az . prímszámot: A kínai maradéktétel ([3] 2.62 Tétel) miatt ez megoldható, tehát meg tudunk adni akármilyen hosszú nulla sorozatot. 32 6. Vegyes feladatok 6.1 Feladat: Oldjuk meg az alábbi egyenleteket: a) b) . Megoldás: . Ezért elég két esetet vizsgálni: a) Tudjuk, hogy  és Ha vagy 2, ezek viszont nem megoldások. , akkor  és , ezekre a számokra ellenőrizve a feladatot sem kapunk helyes Ekkor megoldást. b) , tehát ez jó megoldás. -re ∏ , akkor felírható Ha ∏ Mivel ∏ Tehát ∏ és ∏ Másrészt alakban, ahol ( ∏ , ezért ) ( ∏( ) ), így . ez egyetlen megoldás. 6.2 Feladat:[7] Bizonyítsuk be, hogy

tetszőleges Megoldás: 2-től osztója . természetes számra . -ig minden szám legfeljebb az egyik tulajdonsággal rendelkezik: vagy -nek, vagy relatív prím hozzá, és lehetnek még egyéb számok is. Egyedül az 1 rendelkezik mindkét tulajdonsággal, így őt kétszer számoljuk. 6.3 Feladat: Mely természetes számokra igaz, hogy ? Megoldás: Az előző feladatot felhasználva elég azt vizsgálnunk, hogy mely . Ha ellentmondás. Ha , akkor , ekkor viszont , akkor ez azt jelenti, hogy -ekre lesz , ami prím, ekkor , tehát az egyenlet megoldásai a prímszámok. 33 6.4 Feladat:[7] Oldjuk meg az ( természetes szám) egyenletet! Megoldás: Két korábban belátott állításra fogunk támaszkodni: √ , illetve ha 1-nél nagyobb természetes szám, mely nem prím és nem egy prím négyzete, akkor (√ vagyis ) . Eszerint √ (√ ) √ , , ami viszont ellentmondás. Így megoldás csak abban az esetben lehetséges, ha , prím vagy

prímnégyzet. helyére prímet helyettesítünk, akkor akkor a következő egyenletet kapjuk: -re -et kapunk, mely szintén ellentmondás. Ha újfent ellentmondás. Ha , ahonnan prímnégyzet, , tehát az egyetlen jó megoldás. 34 7. Hegy- és völgytételek 7.1 Tétel:[3] (A olyan függvény hegytétele): Tetszőleges pozitív egészhez végtelen sok található, amelyre egyszerre teljesül, hogy és Bizonyítás: Legyen az első . prímszám szorzata, azaz . Ekkor -re vonatkozó egyenlőtlenséget bizonyítjuk, a ugyanígy történik. Az prímek szorzataként .A -es eset igazolása is a következő alakba írható: , ahol előfordulhat, hogy nem mindegyik prímtényező különböző. Mivel , és -et az első -re. Az prímszám szorzatának választottuk, ezért osztóit úgy képezzük, hogy a összeszorozzuk. Mivel a bármely számokból választunk néhányat, és ezeket -k között egyformák is lehetnek, ezért előfordulhat olyan eset,

mikor egy osztót többféleképpen megkapunk, emiatt . Tegyük fel, hogy , ekkor ami ellentmondás, tehát . Így . Ebből következik, hogy , azaz esetén teljesül a tétel. 7.2 Tétel:[3],[7] (A végtelen sok olyan függvény hegytétele): Tetszőlegesen nagy található, amelyre egyszerre teljesül, hogy és Bizonyítás: Legyen . A amiből . elég nagy prímszám. Ekkor és páros számok lesznek, és -re vonatkozó egyenlőtlenséget bizonyítjuk, a igazolása is ugyanígy történik. Mivel képlet alapján pozitív egészhez . Tehát adódik, és végtelen sok olyan -es eset ∏ alakú, ezért a , azaz ( ) , prím van, amire ez igaz. 35 7.3 Tétel:[3] (A olyan függvény völgytétele): Tetszőleges pozitív egészhez végtelen sok található, amelyre egyszerre teljesül, hogy és Bizonyítás: Legyen . prímszám, ekkor , tehát . Ez azt jelenti, hogy -nek és -nek is van legalább és abban az esetben, ha , osztója. Ez teljesül

megoldása a következő , vagyis, ha szimultán kongruenciarendszernek: Ez a kínai maradéktétel miatt biztosan megoldható, így az összes megoldás: Kell még, hogy az számtani sorozatban végtelen sok prím legyen. Mivel ezért , is igaz, így a Dirichlet-tétel ([3] 5.31 Tétel) miatt teljesül. 7.4 Tétel:[3],[7] (A végtelen sok olyan függvény völgytétele): Tetszőlegesen nagy található, amelyre egyszerre teljesül, hogy és Bizonyítás: Legyen . A . elég nagy prímszám, így összetett számok lesznek és , -re vonatkozó egyenlőtlenséget bizonyítjuk, a √ igazolása is ugyanígy történik. -nél kisebb, de √ szám, így van pozitív egészhez -es eset összetett , mivel -nél nem kisebb osztója, tehát √ Másrészt √ √ miatt adódik, és végtelen sok olyan 7.5 Tétel:[3],[7] (A végtelen sok olyan , prím van, amire ez igaz. függvény völgytétele): Tetszőlegesen nagy pozitív egészhez található, amelyre egyszerre

teljesül, hogy és Bizonyítás: Legyen ahonnan az első ( . prímszám szorzata, azaz )( ) ( . Ekkor ) ( ) 36 -re vonatkozó egyenlőtlenséget bizonyítjuk, a A ugyanígy történik. Az és az első prímtényezős felbontása prímszám szorzata, ezért ( Tegyük fel, hogy -es eset igazolása is . Mivel , bármely -re. Ekkor )( ) ( ) ( ) , ekkor ( .Tehát ami ellentmondás, tehát ) . Ezekből következik, hogy: ) ( ( ami elég nagy ) ( ( ) ( ) ( ) ) esetén nagyobb, mint . 7.6 Tétel: [3],[7] (A függvény völgytétele): A található, azaz létezik végtelen sok olyan függvényben végtelen sok 1 mélységű völgy , melyre és . Bizonyítás: Legyenek prímek, ekkor definíció szerint , és írjuk fel a következő szimultán kongruenciarendszert: Ez a kínai maradéktétel miatt megoldható, és az összes megoldás hozható. Mivel kielégíti a szimultán kongruenciarendszert, ezért miatt alakra , is teljesül,

így a Dirichlet-tétel alapján az számtani sorozatban végtelen sok prímszám van. 37 Irodalomjegyzék [1] BEGE ANTAL: Bevezetés a számelméletbe Scientia Kiadó, Kolozsvár, 2002. [2] BEGE ANTAL, DEMETER ALBERT, LUKÁCS ANDOR: Számelméleti feladatgyűjtemány Scientia Kiadó, Kolozsvár, 2002. [3] FREUD RÓBERT, GYARMATI EDIT: Számelmélet Nemzeti Tankönyvkiadó, Budapest [4] KISS EMIL: Bevezetés az algebrába TYPOTEX, Budapest, 2007 [5] LÁNG CSABÁNÉ: Számelmélet – Példák és feladatok ELTE Eötvös Kiadó, Budapest [6] RUZSA Z. IMRE: Különlenyomat Matematika Lapok 27 évfolyam 1-2 számából Bolyai János Matematikai Társulat, Budapest, 1976-1979. [7] SÁRKÖZY – SURÁNYI: Számelmélet feladatgyűjtemény Tankönyvkiadó, Budapest, 1979. Internetes oldalak: [8] http://www.cseltehu/~ewkiss/bboard/algebrabook/Kiss Algebra megoldasokpdf [9] http://www.cseltehu/~seszter [10] http://www.mersenneorg [11] http://www.oddperfectorg [12]

http://www.ttkptehu/matek/ltoth [13] http://hu.wikipediaorg/wiki 38