A pozitív egész számokat osztóik száma szerint három csoportba
sorolhatjuk: 1. Egy osztója van: ebből csak egy szám van, az 1-es. 2.
Kettő darab osztója van [1, és önmaga]: ezek a prím, vagy másnéven
törzsszámok. 3. Kettőnél több osztója van: ezek az összetett számok.
Prímszámok előállítására szolgál a “Eratosztenész-féle szita”. Euklides
bebizonyította, hogy végtelen sok prímszám van, s az is bizonyítható,
hogy bármilyen “hézagok” is lehetnek a prímszámok között. Két, vagy több
egész szám relatív prím, ha az 1-en kívül nincs más közös osztója, azaz
a legnagyobb közös osztójuk az 1. Két szám akkor is lehet relatív prím,
ha összetett, például a 6, és a 35.
Az
Eratosztenész-féle szita azt jelenti, hogy a felsorolt számok közül
[1-től valameddig] kihúzgálom azokat, amelyek 2-vel, 3-mal, n-nel
oszthatók, s amelyek nem lettek kihúzva, azok a prím számok. Példaként
100-ig írjuk fel a számokat, s elkezdjük kihuzogatni a 2-vel
oszthatóakat, 3-mal oszthatóakat, stb., s csak a 10-ig kell elmennünk,
mivel a 10 négyzete adja ki a százat, és ennek megfelelően amit nem
húztunk ki, azok mind prím számok.
Megjegyzés küldése