google.com, pub-5333805121326903, DIRECT, f08c47fec0942fa0

2013. január 26., szombat

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í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.

0 megjegyzés:

Megjegyzés küldése