Prímszám, relatív prím
Milyen számot nevezünk prímszámnak? Mikor mondjuk, hogy két vagy több szám relatív prím?
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ímszámok, vagy másnéven törzsszámok.
3. Kettőnél több osztója van: ezek az összetett számok.
Az első 10 prímszám: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
A prímszámokhoz kapcsolódó legfontosabb tétel a számelmélet alaptétele, ami azt mondja ki, hogy minden 1-nél nagyobb egész szám a tényezők sorrendjétől eltekintve egyértelműen előállítható prímszámok szorzataként.
Prímszámok előállítására szolgál a „Eratosztenész-féle szita”. Eukleidesz bebizonyította, hogy végtelen sok prímszám van. 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 n-ig] kihúzgálom azokat, amelyek 2-vel, 3-mal, n-nel oszthatók, s amelyek nem lettek kihúzva, azok a prímszá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. Ekkor 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ímszámok.
