fbpx

Prímszámok – elméleti ismeretek, érdekességek, valamint 10 feladat a legegyszerűbbtől az emelt szintig

A prímszámok a matematika egyik legegyszerűbben megadható, ugyanakkor legizgalmasabb halmazát alkotják. Már több, mint 2000 éve tudjuk, hogy végtelen sok prímszám van, hisz Eukleidész ezt Kr. e. 300-ban bizonyította az Elemek című művében. Ugyanakkor számos megoldatlan probléma létezik ebben a témakörben. Az alábbi cikkben a prímszám definíciója után bemutatunk néhányat közülük. Foglalkozunk a Mersenne- és a Fermat-prímekkel, valamint ismertetünk velük kapcsolatban egy-két fontos tételt. Szó lesz a titkosírásról és a nagy prímszámok kereséséről is. A cikk végén ismertetjük 10 feladat megoldását legegyszerűbbtől az emelt szintig.

Kinek hasznos az alábbi cikkünk?

Neked, ha általános iskolás vagy, és most ismerkedsz a prímszámokkal.

Neked, ha érettségire készülsz, és el szeretnéd mélyíteni a prímszámokkal kapcsolatos ismereteket.

Neked, ha már régebben voltál iskolás, ugyanakkor érdekelnek a prímszámokkal kapcsolatos ismeretek.

A prímszám fogalma

A természetes számokat (nulla és a pozitív egész számok) a pozitív osztóik száma szempontjából négy csoportba soroljuk.

  • A 0-nak az összes természetes szám osztója, így végtelen sok pozitív osztója van.
  • Az 1-nek egy pozitív osztója van, ez az 1.
  • Az olyan pozitív egész számokat, melyeknek pontosan két pozitív osztója van, prímszámoknak nevezzük. Ez a két pozitív osztó az 1 és önmaguk.
  • Az olyan pozitív egész számokat, melyeknek kettőnél több pozitív osztója van, összetett számoknak nevezzük.

Tehát a prímszám olyan pozitív egész szám, melynek pontosan két pozitív osztója van. Az 1 nem prímszám, mert pontosan egy pozitív osztója van.

A prímszámokkal kapcsolatosan meg szoktunk adni egy, az előzővel egyenértékű (ekvivalens) definíciót is.

Mielőtt erre rátérnénk, emlékeztetünk arra, hogy ha egy pozitív egész szám osztója egy szorzat valamelyik tényezőjének, akkor osztója a szorzatnak is. Nézzünk erre egy példát: a 14 osztója a 28-nak, így osztója a 28 háromszorosának, azaz a 84-nek is.

Ennek a megfordítása már nem feltétlenül igaz. Azaz, ha egy pozitív egész szám osztója egy szorzatnak, akkor nem biztos, hogy osztója valamelyik tényezőjének. Például 12 osztója a 36–nak, de nem osztója sem a 4-nek, sem a 9-nek. Bizonyítható, hogy a megfordítás az 1-nél nagyobb pozitív egészek közül csak a prímszámokra igaz, ezért fogalmazhatjuk meg az alábbi definíciót.

Eszerint egy 1-nél nagyobb pozitív egész szám akkor és csak akkor prímszám, ha csak úgy lehet osztója két pozitív egész szám szorzatának, ha osztója legalább az egyik tényezőnek.

***

Klasszikus tételek, illetve megoldatlan problémák a prímszámok köréből

A prímszámok száma

Azt már említettük, hogy a prímszámokkal már az ókori görögök is foglalkoztak. Eukleidész Elemek című művében szerepel az alábbi tétel, melynek bizonyítását is ismertetjük.

Tétel: Végtelen sok prímszám létezik.

Bizonyítás: Tegyük fel, hogy nem igaz az állítás, azaz csak véges sok prímszám létezik.

Legyenek ezek

 {{p}_{1}},{{p}_{2}},...,{{p}_{n}}. 

Képezzük ezekből az alábbi számot

N={{p}_{1}}\cdot {{p}_{2}}\cdot ...\cdot {{p}_{n}}+1.

A képzési szabály alapján nyilvánvaló, hogy N a felsorolt n db prímszám egyikével sem osztható. Ugyanakkor N>1, így létezik prímosztója, ami az előzőek szerint különbözik a az eddig felsorolt prímek mindegyikétől, ami ellentmondás. Így a feltevésünk helytelen, tehát végtelen sok prímszám van.

***

Eratoszthenészi szita

Eratoszthenész görög matematikus volt, aki Kr.e. 3. században, Alexandriában élt és tevékenykedett. Foglalkozott csillagászattal és fizikával is. Matematikusként leginkább az ókor három nevezetes problémája érdekelte, azaz a kockakettőzés, a kör négyszögesítése és a szögharmadolás. Az utókor a nevével leginkább a prímszámok kiválogatására használt eljárása kapcsán találkozott, mely Eratoszthenészi szita néven vált ismertté.

Az eljárás lényege a következő. Írjuk fel az egész számokat 1-től N-ig (N>2). Első lépésben áthúzzuk az 1-et és karikázzuk be a 2-t, majd húzzuk át N-ig a 2-nél nagyobb páros számokat. Ezután karikázzuk be a 3-at, majd húzzuk át a három azon többszöröseit N-ig, melyeket még nem húztunk át és nagyobbak 3-nál. Folytassuk tovább az eljárást. Tehát karikázzuk be azt a legkisebb számot, amit eddig nem jelöltünk meg, majd húzzuk át a nála nagyobb többszöröseit.

Ismételjük meg a fenti eljárást mindig a legkisebb még meg nem jelölt számmal. Ha a legkisebb jelöletlen szám nagyobb vagy egyenlő az N négyzetgyökénél, akkor megállunk. Ekkor a bekarikázott és a jelöletlen számok együttesen az N-nél nem nagyobb prímszámok. Itt kihasználtuk azt a tételt, mely szerint, ha N összetett szám, akkor a legkisebb prímosztója nem nagyobb a szám négyzetgyökénél.

Nézzünk erre egy példát. Legyen N=49. Kövessük végig a folyamatot az alábbi ábrasoron.

A könnyebb áttekinthetőség kedvéért bekereteztük azokat a ki nem húzott számokat is, amiket korábban nem karikáztunk be. Így a prímszámok N=49-ig az alábbi táblázatban láthatók.

***

Szomszédos prímszámok: ikerprímek

Az előző táblázatban is fellelhetünk olyan prímszámokat, melyek szomszédos páratlan számok. Az ilyen prímeket ikerprímeknek nevezzük. Ezek itt a {3, 5}, {5, 7}, {11, 13}, {17, 19}, {29, 31}, {41, 43}.

Megoldatlan probléma, hogy létezik-e végtelen sok ikerprím pár. Ugyanakkor azt már bizonyították, hogy az ikerprímek „nagyon ritkán” helyezkednek el. Erre utal például az, hogy az ikerprímek reciprokösszege konvergens, míg a prímeké divergens.

Azt is igazolták már, hogy végtelen sok olyan p, p+2 számpár van, ahol p prímszám, míg p+2 prím, vagy két prím szorzata.

A ma (2021. 06. 01.) ismert legnagyobb ikerprímek:

65516468355\cdot {{2}^{333333}}\pm 1.

Számjegyeinek a száma 100355.

***

Goldbach-sejtés

Christian Goldbach (1690-1764) német matematikus, a szentpétervári Birodalmi Akadémia tagja volt. Königsbergben született, majd 1725-től haláláig Oroszországban élt.

1724-ben egy Eulerhez írt levelében fogalmazta meg, hogy minden 3-nál nagyobb egész szám felírható legfeljebb három prímszám összegeként.

Euler válaszában a következő szerepelt. Az állítás igazolásához elég lenne bebizonyítani, hogy bármely 2-nél nagyobb páros szám felírható két prímszám összegeként: pl. 4=2+2, 6=3+3, 8=5+3, 10=7+3, 12=5+7 stb.

Ezt a problémát szokás Goldbach-sejtésnek nevezni. Említik még páros, illetve erős Goldbach-sejtésként is. Goldbach levelében szereplő állítást pedig páratlan, vagy gyenge Goldbach-sejtésnek.

Ezzel a közel 300 éves problémával kapcsolatosan ma is csak részeredményekkel rendelkezünk. Eddig

4\cdot {{10}^{18}}\text{-nál}

kisebb páros számokra igazolták számítógéppel.

***

Prímszámok számtani sorozatokban

Kérdés, hogy létezik-e akármilyen hosszú (nem konstans) számtani sorozat csupa prímszámból?

Nézzünk néhány példát! Háromtagú számtani sorozat: {3, 5, 7}, öttagú: {5, 11, 17, 23, 29}, hattagú: {7, 37, 67, 97, 127, 157}.

2004-ben Ben Greennek és Terence Taonak sikerült bebizonyítani, hogy a kérdésre adott válasz: igen. A bizonyítás 49 oldalas és magasabb matematikai eszközöket alkalmaz, így annak ismertetésétől most eltekintünk.

A ma ismert leghosszabb, csupa prímszámból álló számtani sorozatnak 23 tagja van:

56211383760397+44546738095860\cdot k \text{,  }k\in \mathbb{N} \text{, } k\le 22.

Egy végtelen, nem konstans számtani sorozatnak, viszont már nem lehet minden tagja prímszám. Ennek bizonyítása viszonylag egyszerű, ezért most megismerkedünk vele.

Tétel:  Nem létezik olyan végtelen hosszú, d>0 differenciájú számtani sorozat, melynek minden tagja prímszám

Bizonyítás:

Legyen a számtani sorozat első tagja a1=p, ahol p prímszám és a differenciája d>0 egész szám. Tekintsük a számtani sorozat p+1-edik tagját, ami

a_{p+1}=p+p \cdot d=p(1+d). 

Ez a szám viszont összetett, hisz felírható két 1-nél nagyobb pozitív egész szám szorzataként. Ezzel az állítást bizonyítottuk.

Ugyanakkor ismert az alábbi, Dirichlettől származó tétel, ami arról szól, hogy vannak olyan számtani sorozatok, melyeknek végtelen sok tagja prímszám.

Dirichlet-tétel: Ha d>0 és a egész számok relatív prímek, akkor az

{a}_{n}=a+(n-1)d

számtani sorozat végtelen sok prímszámot tartalmaz.

Megmelítjük ennek a tételnek két speciális esetét. Az egyik, hogy végtelen sok 4k+3 alakú prímszám van. A másik szerint 4k+1 (k pozitív egész szám) alakú prímszámból is végtelen sok van. Ezeket az állításokat már nem nehéz bizonyítani, főleg az elsőt.

***

Létezik-e képlet prímszámok előállítására?

Vagyis megadható-e olyan, a természetes ,vagy a pozitív egész számok halmazán értelmezett függvény, amelynek minden helyettesítési értéke prímszám?

Úgy tűnik, hogy ilyenre nem igazán van remény.

Érdekességképpen megemlítjük, hogy Eulertől származik a

p(n)={{n}^{2}}+n+41

összefüggés, aminek az n=0, 1, 2, 3, …, 39  esetén vett helyettesítési értéke prím. Ugyanakkor könnyen igazolható, hogy n=40-nél már nem prím.

Speciális alakú prímszámok, tökéletes számok

Ebben a részben a

{2}^{n}+1 \text{, illetve a }{2}^{n}-1 

alakú prímszámokkal foglalkozunk. Az előbbieket Fermat-, az utóbbiakat Mersenne-féle prímeknek nevezzük.

Fermat-féle prímszámok

Be lehet bizonyítani (lásd a 9. feladatot), hogy ha egy

{2}^{n}+1

alakú szám prím, akkor szükségképpen

n={{2}^{k}}.

Az

{{F}_{k}}={{2}^{{{2}^{k}}}}+1

alakú számokat Fermat-féle számoknak nevezzük.

Pierre Fermat (1601-1665) Toulouse város közigazgatási szervezetének jogi tanácsosa volt, csak szabadidejében foglalkozott matematikával és fizikával. Így is korának legkitűnőbb matematikusai közé tartozott. Számos tétel fűződik a nevéhez a számelmélet témaköréből, ugyanakkor rendkívül értékes megfigyeléseket végzett a geometriában és az infinitezimális számítás előkészítésében.

Fermat úgy vélte, hogy Fk a k minden nemnegatív egész értéke esetén prímszámot ad. Ez igaz is k=0, 1, 2, 3, 4 esetén, ugyanakkor

F_5=2^{2^5}+1=2^{32}+1

nem prím, hisz osztható 641-gyel, mint ahogy ezt már Euler 1732-ben, 25 éves korában bebizonyította.

A Fermat-prímek alkalmazása

Azt már bizonyították, hogy az 5 és 32 közé eső pozitív egész k-k esetén Fk összetett szám. Egyelőre nem találtak k>4 esetén a Fermat-számok között prímet. Egy-egy ilyen gondolatkör kapcsán a laikusokban mindig felmerül a kérdés, hogy van-e értelme ezzel foglalkozni? Érdemes-e további Fermat-prímeket keresni?

A Fermat-prímek jelentőségére Gauss világított rá a szabályos sokszögek szerkeszthetőségére vonatkozó alábbi tételével.

Tétel: Egy szabályos n-szög akkor és csak akkor szerkeszthető körzővel és egyélű vonalzóval, ha

n={{2}^{k}}\cdot {{p}_{1}}\cdot {{p}_{2}}\cdot ...\cdot {{p}_{r}}

ahol k természetes szám, és p1, p2,…, pr páronként különböző Fermat-féle prímek.

Eszerint szerkeszthető pl. szabályos háromszög, ötszög, hatszög, tízszög, tizenkétszög, tizenötszög, tizenhétszög stb.

Mesrenne-féle prímszámok

Bizonyítható, hogy ha egy

{2}^{n}-1

alakú szám prímszám, akkor n is prím (lásd a 10. feladatot).

Az

M_p={2}^{p}-1

alakú számokat, ahol p prímszám, Mersenne-féle számoknak, közülük a prímeket Mersenne-prímeknek nevezzük. A legkisebb olyan Mersenne-szám, ami nem prímszám az M11=2047, ami felírható 23 és 89 szorzataként. Jelenleg, azaz 2021. 06. 01. napján 51 darab Mersenne-prímet ismerünk.

Marin Mersenne (1588-1648) francia matematikus, minorita szerzetes. Nagy érdeme volt abban, hogy korának matematikusai értesültek egymás eredményeiről, mert szinte minden jelentős matematikussal levelezésben állt.

A Mersenne-prímek jelentőségét a prímszámkeresésben betöltött szerepük, valamint a páros tökéletes számokkal való kapcsolatuk adja. A ma ismert legnagyobb prímszám is Mersenne-prím.

Tökéletes számok

Egy pozitív egész számot tökéletes számnak nevezünk, ha pozitív osztóinak az összege egyenlő a szám kétszeresével. Pl. a 6 és a 28 is tökéletes szám, hisz 1+2+3+6=12, illetve 1+2+4+7+14+28=56. Már Eukleidész Elemek című művében szerepel egy konstrukció a tökéletes számok előállítására. Az erre vonatkozó állítást Euler tovább fejlesztette és így alakult ki az alábbi Eukleidész-Euler-tétel.

Tétel: Egy n páros szám akkor és csak akkor tökéletes szám, ha

n={{2}^{p-1}}\left( {{2}^{p}}-1 \right),

ahol Mp=2p-1 Mersenne-féle prím, így p prímszám.

A tételből következik, hogy pontosan annyi páros tökéletes szám van, mint ahány Mersenne-prím. Mivel nem tudjuk, hogy az utóbbiból végtelen sok van-e, így az is megoldatlan probléma, hogy végtelen sok tökéletes szám van-e. Az is nyitott kérdés, hogy van-e egyáltalán páratlan tökéletes szám.

***

Prímtesztek, néhány szó a titkosírásról

Mennyire nehéz eldönteni egy pozitív egész számról, hogy prímszám-e? Mennyi ideig tart egy összetett szám prímtényezős felbontása?

Ezekre a kérdésekre látszólag egyszerűnek tűnik a válasz.

Például prímszám-e az 523?

A korábbiak alapján elég megnézni, hogy az 523 négyzetgyökéig létezik-e olyan prímszám, amely osztója az 523-nak. Mivel ez a szám 22 és 23 közé esik, ezért elég megnézni, hogy a 2, 3, 5, 7, 11, 13, 17, 19 számok valamelyike osztója-e az 523-nak. Az oszthatósági szabályok alapján a 2, 3, 5 és 11 gyorsan kizárható. A maradék mindegyikével elosztva, kiderül, hogy a hányados egyik esetben sem egész szám, így az 523 prímszám.

Ez nem tartott sokáig. Ugyanakkor mit mondhatunk akkor, ha a vizsgált szám több ezer, vagy több tízezer jegyű? Akkor is hatékony ez az eljárás?

Ilyen nagy számok esetén a fenti eljárás a jelenlegi technikai eszközökkel kivitelezhetetlen, mert nagyon sok időt venne igénybe. Például egy 1000 jegyű számot, amelynek nincs kis prímosztója, vagy valamilyen speciális tulajdonsága, évmilliárdok alatt sem lehet tényezőkre bontani.

Milyen hatékony eljárások léteznek?

Ezeket nevezzük prímteszteknek. Közülük most megemlítünk kettőt, melyek viszonylag könnyen érthetők. Az egyik a Fermat-, a másik a Mersenne-prímek tesztelésére alkalmas

Az első a Pepin-teszt, amely kimondja, hogy egy Fk (0<k) Fermat-féle szám, akkor és csak akkor prím, ha teljesül rá, hogy Fk osztója a

{{3}^{\frac{{{F}_{k}}-1}{2}}}+1

számnak.

A második a Lucas-Lehmer-teszt. Eszerint ha p>2 prímszám, továbbá

{{a}_{1}}=4 \text{ } \text{ és } \text{ }{{a}_{n+1}}=a_{n}^{2}-2 \text{ } (n\ge 1).

Ilyenkor az Mp Mersenne-féle szám, akkor és csak akkor prímszám, ha Mp osztója az ap-1-nek.

A nagy összetett számok nehézkes faktorizációja teszi lehetővé azt, hogy a nagy prímszámokat hatékonyan tudjuk használni titkosírásban, információk titkosításában.

***

10 feladat prímszámokra

Alapfeladatok

  • 1. feladat: Páros vagy páratlan az első 2022 darab prímszám összege, illetve szorzata?

Megoldás: Első megközelítésre riasztónak tűnik a kérdés. Most keressük meg az első 2022 darab prímszámot, majd adjuk, illetve szorozzuk össze? Ennél azért egyszerűbben kideríthetjük a választ a kérdésekre. Elég csak a prímszámok paritására gondolnunk.

Mivel a 2 az egyetlen páros prímszám, ezért itt egy páros és 2021 db páratlan prímet kell összeadni. Ezen utóbbi összeg páratlan, ha ehhez hozzáadjuk a 2-t, akkor páratlan számot kapunk eredményül. Az eddig leírtakból az is kiderül, hogy a szorzatuk páros, hisz osztható 2-vel. Ezzel a feladatot megoldottuk.

***

  • 2. feladat: Három prímszám összege 2022. Mennyivel egyenlő közülük a legkisebb?

Megoldás: Három szám összege csak úgy lehet páros, ha mindhárom páros, vagy egy páros és kettő páratlan. Mivel csak egy páros prímszám van, ez a 2, ezért az első eset most nem állhat elő. A második esetben pedig fel kell használnunk a 2-t, így ez a legkisebb a három prímszám közül. A másik kettő lehet például a 2017 és a 3. Ezzel a feladatot megoldottuk.

***

Közepes nehézségű feladatok

  • 3. feladat: Határozzuk meg az összes olyan p és q prímszámot, melyekre teljesül, hogy a p-q és p+q is prímszám!

Megoldás: Nyilván q<p. Mivel két páratlan szám összege és különbsége is páros, így nem lehet mindkét prím páratlan. Hisz tudjuk, hogy csak egy páros prím van a 2. Tehát a kisebbik a 2, azaz q=2. A másik nyilván páratlan. Így p olyan páratlan prímszám, amire p-2, p, p+2 is prímszám.

Mivel ez három egymást követő páratlan szám, így pontosan az egyik osztható 3-mal. Tudjuk, hogy az egyetlen 3-mal osztható prím a 3, és nincs nála kisebb páratlan prím, így p-2=3. Ebből p=5. Így a keresett prímek q=2, p=3. Ezzel a feladatot megoldottuk.

***

  • 4. feladat: Határozzuk meg az összes olyan x, y és z prímszámot, melyekre fennáll az alábbi egyenlőség
2x+7y+14z=434.

Megoldás:  A feltételek szerint a bal oldali kifejezés minden tagja egész szám. Vizsgáljuk meg ezen oldalt. Itt az összeg első és harmadik tagja osztható 2-vel, akárcsak a 434. Így csak abban az esetben állhat fenn az egyenlőség, ha a 7y is páros. Mivel y prím, így szükségképpen y=2.

Ekkor kapjuk, hogy

2x+14z=420,

azaz

x+7z=210.

A 7z és a 210 is osztható 7-tel, amiből következik, hogy az x is. Mivel x prím, ezért x=7. Ezután már könnyen kiszámolhatjuk, hogy z=29. Tehát x=7, y=2 és z=29. Ezzel a feladatot megoldottuk.

***

Egy érdekes feladat prímekre

  • 5. feladat: Létezik-e olyan pozitív egész szám, melyet nem tudunk egy számjegyének megváltoztatásával prímszámmá alakítani? Ha igen, melyik a legkisebb ilyen?

Megoldás:

Ha létezik ilyen, akkor azt célszerű a páros számok körében keresni. Ez azért van, mert a párosszámoknak szükségképpen az utolsó számjegyét kell megváltoztatni, hogy belőle prímszám lehessen. Így elég megnézni, hogy melyik a legkisebb olyan 10-zel osztható pozitív egész szám, melyre teljesül, hogy közte és a rákövetkező 10-zel osztható szám között nincs prímszám.

Ebben segít egy prímszám-táblázat. Így az első ilyen pozitív egész szám a 200. Tehát a 200 megfelelő szám. Ezzel a feladatot megoldottuk.

***

Emelt szintű feladatok

Feladat a prímszámok elhelyezkedésére

  • 6. feladat: Az előző feladat nyomán kézenfekvő a kérdés, hogy milyen sűrűn helyezkednek el a prímszámok a pozitív egész számok között? Létezik-e minden pozitív egész n esetén n db egymást követő pozitív egész szám, melyek mindegyike összetett szám?

Megoldás:                              

Igen, meg lehet adni n db egymást követő összetett számot például a következő konstrukcióval:

{{a}_{1}}=(n+1)!+2, {{a}_{2}}=(n+1)!+3, {{a}_{3}}=(n+1)!+4, …\\ , {{a}_{i}}=(n+1)!+(i+1),… , {{a}_{n}}=(n+1)!+(n+1), 

ahol

(n+1)!=1\cdot 2\cdot 3\cdot ...\cdot (n+1).

Ekkor i+1 osztója ai-nek, mert i+1 osztója (n+1)!-nak és természetesen i+1-nek is.

Ezek a számok nyilván egymást követőek, másrészt minden esetben az ai nagyobb, mint i+1, vagyis nagyobb, mint az osztója, így mindegyik összetett szám. Ezzel a feladatot megoldottuk.

***

Feladat ikerprímekre

  • 7. feladat: Legyen p, q illetve r, s két ikerprím pár, amelyek mindegyike nagyobb, mint 3. Igaz-e, hogy ekkor az
N=p\cdot r-q\cdot s

osztható 12-vel.

Megoldás: Mivel egy pozitív egész szám akkor és csak akkor osztható 12-vel, ha osztható 4-gyel és 3-mal, ezért vizsgájuk meg az N  3-as illetve 4-es maradékát.

A p, q illetve r, s ikerprím párok, így p, q illetve r, s egymást követő páratlan számok, tehát a számpárok egyik tagjának a négyes maradéka 1, a másiké 3. A feltételek alapján mind a négy prímszám nagyobb 3-nál, ezért az egyik sem osztható 3-mal, ami azt jelenti, hogy a számpárok egyik tagjánaka hármas maradéka 1, a másiké 2.

A továbbiakban használjuk fel, hogy két szám szorzatának m-es maradéka egyenlő az m-es maradékaik szorzatának m-es maradékával.

Ha p és r négyes maradéka 3, akkor q és s négyes maradéka 1. Ekkor a pr  négyes maradéka egyenlő a 9 négyes maradékával, azaz 1. Mivel qs négyes maradéka is 1, így a különbségük osztható 4-gyel. Ha p és r négyes maradéka különböző, akkor az r és s négyes maradéka is különböző, amiből következik, hogy a pr és qs négyes maradéka is 3, így N osztható 4-gyel.

Hasonlóan gondolható végig, hogy N osztható 3-mal, amit a tisztelt Olvasóra bízunk. Így N osztható 12-vel. Ezzel a feladatot megoldottuk.

***

Feladat prímszámokra

  • 8. feladat: Legyen
p \text{ és } 8p^2+1

is prím. Lehet-e a

p^2+p+1

összetett szám?

Megoldás: Először nézzük meg, hogy mely p prímszámok esetén lehet

8p^2+1

is prímszám?

Ha p=3, akkor

8p^2 +1=73,

ami ugyancsak prím.

Ha p 3-tól különböző prímszám, akkor hármas maradéka 1 vagy 2. Az előző feladatban idézett tétel alapján a négyzetének a hármas maradéka megegyezik az 1, illetve a 4 hármas maradékával, ami 1.

Ez alapján

8p^2

hármas maradéka 2, így

8p^2+1

osztható 3-mal és nagyobb, mint 3, ami miatt nem lehet prím.

Tehát csak p=3 esetén teljesül a feltétel. Ekkor viszont

p^2+p+1=13,

ami prímszám, így a feltett kérdésre a válasz: nem. Ezzel a feladatot megoldottuk.

***

Feladat a Fermat-prímekre

  • 9. feladat: Bizonyítsuk be, hogy ha egy
F_n=2^n+1 \text{ }(n\in {{\mathbb{Z}}^{+}}) 

alakú szám prímszám, akkor

n=2^k,

ahol k pozitív egész szám. (Fermat-prímek)

Megoldás: Nézzünk erre egy indirekt bizonyítást, azaz tegyük fel, hogy Fn prímszám, mégis van az n számnak 1-nél nagyobb páratlan osztója.

A bizonyítás további részében használjuk az

{{a}^{2k+1}}+{{b}^{2k+1}}=\left( a+b \right)\left( {{a}^{2k}}-{{a}^{2k-1}}b+{{a}^{2k-2}}{{b}^{2}}-...\pm ...+{{b}^{2k}} \right)

azonosságot.

Legyen az n 1-nél nagyobb páratlan osztója 2l+1 , ahol l pozitív egész szám. Ekkor n=(2l+1)q, ahol q pozitív egész szám.

Így

{{F}_{n}}={{2}^{n}}+1={{2}^{(2l+1)q}}+1={{\left( {{2}^{q}} \right)}^{2l+1}}+1=\left( {{2}^{q}}+1 \right)\left( {{\left( {{2}^{q}} \right)}^{2l}}-{{\left( {{2}^{q}} \right)}^{2l-1}}+...+{{2}^{q}} \right),

ahol

1<{{2}^{q}}+1<{{2}^{(2l+1)q}}+1={{F}_{n}},

ami azt jelenti, hogy Fn nem lehet prím. Így ellentmondásra jutottunk, ezért

n=2^k,

ahol k pozitív egész szám. Ezzel a feladatot megoldottuk.

***

Feladat Mersenne-prímekre

  • 10. feladat: Bizonyítsuk be, hogy ha egy
M_n=2^n-1

( ahol n pozitív egész szám ) alakú szám prímszám, akkor n prímszám. (Mersenne-prímek)

Megoldás: Itt is alkalmazzunk indirekt bizonyítást. Tegyük fel, hogy Mn prímszám, mégis létezik az n-nek 1-nél nagyobb és n-nél kisebb osztója.

A továbbiakban használjuk fel az

{{a}^{k}}-{{b}^{k}}=\left( a-b \right)\left( {{a}^{k-1}}+{{a}^{k-2}}b+{{a}^{k-3}}{{b}^{2}}+...+{{b}^{k-1}} \right)

összefüggést.

Legyen az n szám 1-nél nagyobb, nála kisebb osztója q. Ekkor n=pq, ahol p pozitív egész számra is teljesül, hogy nagyobb 1-nél és kisebb n-nél.

Így

{{M}_{n}}={{2}^{n}}-1={{2}^{pq}}-1={{\left( {{2}^{p}} \right)}^{q}}-1=\left( {{2}^{p}}-1 \right)\left( {{\left( {{2}^{p}} \right)}^{q-1}}+{{\left( {{2}^{p}} \right)}^{q-2}}+...+2+1 \right),

ahol a feltételek alapján

1<{{2}^{p}}-1<{{2}^{pq}}-1={{M}_{n}},

amiből következik, hogy Mn nem prímszám. Ez ellentmondás, így feltevésünk helytelen, tehát n prímszám. Ezzel a feladatot megoldottuk.

***

Összefoglalás

Igyekeztünk a cikkben néhány érdekességet, fontos információt felvillantani a prímszámokkal kapcsolatosan. A téma nagyon szerteágazó és olykor-olykor mélyre hatoló, ezért nem volt lehetőségünk mindenre kitérni. Akit további részletek is érdekelnek, annak javaslom Freud Róbert és Gyarmati Edit Számelmélet című könyvét.

Szeretnél még több, hasonló cikket olvasni? Akkor böngéssz a blogunkon! Ha emelt szintű érettségire készülsz, vagy elsőéves egyetemista vagy, akkor ajánljuk figyelmedbe az online tanuló felületünket és a felkészülést segítő csomagjainkat. Az ezekkel kapcsolatos részletekről itt https://erettsegi.pro/ olvashatsz.

Összegyűjtöttük az eddigi összes emelt szintű matematika érettségi feladatsort és a megoldásokat. Ezt a gyűjteményt, valamint az érettségire készüléssel kapcsolatos hasznos tanácsokat a https://erettsegi.pro/emelt-szintu-matematika-erettsegi-feladatsorok/ linken érheted el.

Szerző: Ábrahám Gábor (https://erettsegi.pro/personnel/abrahamgabor/)

Cikkek


A szerző további cikkei a (https://matek.fazekas.hu/index.php?option=com_content&view=category&id=21&Itemid=136) linken érhetők el.

Matematikai témájú cikkeink a https://erettsegi.pro/matekos-blog/ linken olvashatók.

Az emelt szintű érettségire készüléssel kapcsolatos írásaink a https://erettsegi.pro/40-het-alatt-uj-tudas-szuletik-keszulj-a-matek-erettsegire/, illetve https://erettsegi.pro/17-fejezet-matematikabol/ linken érhetők el.

A szerző által írt tankönyvek ahttp://maximkiado.hu/termekek/72/73/2/4 linken találhatók.

***

Matek versenyre készülőknek

Aki szeretne matematikával versenyzés szintjén foglalkozni, annak javaslom az Erdős Pál Matematikai Tehetségondozó Iskolát. Részletek ezen linken https://erdosiskola.mik.uni-pannon.hu/ olvashatók. A matematika versenyek témáit feldolgozó könyvek, kiadványok (a szerző Egyenlőtlenségek I.-II. című könyvei is) a https://www.zalamat.hu/kiadvanyaink linken kersztül vásárolhatók meg.

Leave a Reply