Prímszámok

A prímszám egy bizonyos típusú természetes szám. Bármely természetes szám egyenlő önmagának 1-szeresével. Ha a szám egyenlő bármely más szám szorzatával, akkor a számot "összetett számnak" nevezzük. A legkisebb összetett szám a 4, mert 2 x 2 = 4. Az 1 nem összetett szám. Minden más szám prímszám. A prímszámok azok az 1-től különböző számok, amelyek nem egyenlőek m x n-nel (kivéve 1 x önmagát). A legkisebb prímszám a 2. A következő prímszámok a 3, 5, 7, 11 és 13. Nincs legnagyobb prímszám.

A prímszámok előfordulásának módja nehéz probléma a matematikusok számára. Ha egy szám nagyobb, akkor nehezebb eldönteni, hogy prímszám-e. Az egyik válasz a prímszámtétel. Az egyik megoldatlan probléma a Goldbach-féle sejtés.

A prímszámokról másképp is gondolkodhatunk. A 12-es szám nem prímszám, mert egy téglalapot lehet alkotni, amelynek oldalai 4 és 3 hosszúak. Ennek a téglalapnak a területe 12, mert mind a 12 kocka felhasználásra kerül. A 11-gyel ez nem lehetséges. Akárhogy is rendezzük el a téglalapot, mindig maradnak tömbök, kivéve azt a téglalapot, amelynek oldalai 11 és 1 hosszúságúak.

Hogyan találjuk meg a kis prímszámokat

Van egy egyszerű módszer a prímszámok listájának megtalálására. Eratoszthenész alkotta meg. Eratoszthenész szitája a neve. Felfogja a nem prímszámokat (mint egy szita), és átengedi a prímszámokat.

A módszer egy számlistával és egy b nevű speciális számmal dolgozik, amely a módszer során változik. Ahogy végigmész a módszerrel, bekarikázol néhány számot a listán, másokat pedig áthúzol. Minden bekarikázott szám prímszám, és minden áthúzott szám összetett szám. Az elején minden szám egyszerű: nincs bekarikázva és nincs áthúzva.

A módszer mindig ugyanaz:

Írja fel egy papírlapra az összes egész számot 2-től a vizsgált számig. Az 1-es számot ne írd le. Menjünk a következő lépésre.
Kezdjük úgy, hogy b egyenlő 2-vel. Menjünk a következő lépésre.
Karikázza be a b-t a listában. Menjen a következő lépésre.
A b-től kezdve számolj még b-vel feljebb a listán, és húzd ki ezt a számot. Ismételjük meg a számok számolását és a számok áthúzását a lista végéig. Menjünk a következő lépésre.

(Például: Ha b 2, akkor bekarikázod a 2-est, és áthúzod a 4-est, 6-ost, 8-ast, és így tovább. Ha b 3, akkor bekarikázod a 3-at, és áthúzod a 6, 9, 12, stb. számokat. A 6 és a 12 már át lett húzva. Húzd át őket újra).

Növelje a b értéket 1-gyel. Menjen a következő lépésre.
Ha a b-t áthúzta, térjen vissza az előző lépésre. Ha b egy olyan szám a listán, amelyet nem húztak át, akkor lépjünk a 3. lépésre. Ha b nincs a listán, menjünk az utolsó lépésre.
(Ez az utolsó lépés.) Kész is van. Az összes prímszámot bekarikáztuk, az összes összetett számot áthúztuk.

Ezt a módszert például a 2-től 10-ig terjedő számok listáján végezhetjük el. A végén a 2, 3, 5 és 7-es számok bekarikázva maradnak. Ezek prímszámok. A 4, 6, 8, 9 és 10 áthúzásra kerül. Ezek összetett számok.

Ez a módszer vagy algoritmus túl sokáig tart a nagyon nagy prímszámok megtalálásához. De kevésbé bonyolult, mint a nagyon nagy prímszámok esetében használt módszerek, például a Fermat-féle prímteszt (egy teszt, amely azt vizsgálja, hogy egy szám prím-e vagy sem) vagy a Miller-Rabin-féle prímteszt.

Mire használják a prímszámokat

A prímszámok nagyon fontosak a matematikában és a számítástechnikában. Az alábbiakban néhány valós felhasználási módot mutatunk be. A nagyon hosszú számokat nehéz megoldani. Nehéz megtalálni a prímtényezőiket, ezért a legtöbbször a valószínűleg prímszámokat használják titkosításra és titkos kódokra.

A legtöbb embernek van bankkártyája, amellyel ATM segítségével pénzt vehet fel a számlájáról. Ezt a kártyát egy titkos hozzáférési kód védi. Mivel a kódot titokban kell tartani, nem tárolható a kártyán tiszta szövegben. A kód titkos tárolására titkosítást használnak. Ez a titkosítás szorzásokat, osztásokat és nagy prímszámok maradékainak megtalálását használja. A gyakorlatban gyakran használják az RSA nevű algoritmust. Ez a kínai maradéktételt használja.

Ha valaki digitális aláírással rendelkezik az e-mailjéhez, akkor titkosítást használ. Ez biztosítja, hogy senki ne tudjon hamisítani egy tőlük származó e-mailt. Az aláírás előtt létrehozzák az üzenet hash-értékét. Ezt kombinálják a digitális aláírással, így jön létre az aláírt üzenet. Az alkalmazott módszerek nagyjából ugyanazok, mint a fenti első esetben.

Az eddig ismert legnagyobb prímszám megtalálása egyfajta sporttá vált. Annak vizsgálata, hogy egy szám prím-e, nehéz lehet, ha a szám nagy. A jelenleg ismert legnagyobb prímszámok általában Mersenne-prímszámok, mivel a prímszámok leggyorsabb ismert tesztje a Lucas-Lehmer-teszt, amely a Mersenne-számok speciális formájára támaszkodik. Egy Mersenne-prímszámokat kereső csoport itt[1] található.

Kérdések és válaszok

K: Mi az a prímszám?

V: A prímszám olyan természetes szám, amely nem osztható más természetes számmal, kivéve az 1-et és önmagát.

K: Mi a legkisebb összetett szám?

V: A legkisebb összetett szám a 4, mert 2 x 2 = 4.

K: Melyek a 2 után következő prímszámok?

V: A 2 után a következő prímszámok a 3, 5, 7, 11 és 13.

K: Van-e legnagyobb prímszám?

V: Nem, nincs legnagyobb prímszám. A prímszámok halmaza végtelen.

K: Mit állít az aritmetika alaptétele?

V: Az aritmetika alaptétele kimondja, hogy minden pozitív egész szám felírható prímszámok szorzataként egyedi módon.

K: Mi a Goldbach-féle sejtés?

V: A Goldbach-féle sejtés egy megoldatlan probléma a matematikában, amely azt állítja, hogy minden kettőnél nagyobb páros egész szám kifejezhető két prímszám összegeként.

K: Ki jegyezte fel a bizonyítékot, hogy nincs legnagyobb prímszám?

V: Euklidész jegyezte fel a bizonyítékot, hogy nincs legnagyobb prímszám.