Relatív prímek
A Wikipédiából, a szabad lexikonból.
A matematikában a és b egész számokat relatív prímeknek nevezzük, ha 1-en és −1-en kívül nincs más közös osztójuk. Vagy ezzel ekvivalensen, ha legnagyobb közös osztójuk 1.
Például a 6 és a 35 relatív prímek, de a 6 és a 27 nem, mert mindkettő osztható 3-mal. A prímszámok a 0-án kívül minden összetett számhoz relatív prímek. Az 1 minden egész számhoz relatív prím; a 0 csak az 1-hez és a −1-hez.
Annak gyors eldöntésére, hogy két szám relatív prím-e alkalmas az euklideszi algoritmus.
Az Euler-függvény (vagy Euler-féle fí-függvény) pozitív egész n-ekre megadja az 1 and n − 1 közötti, n-hez képest relatív prím egészek számát.
Tartalomjegyzék |
[szerkesztés] Tulajdonságok
Az „a és b relatív prímek” kijelentéssel ekvivalens állítások:
- Léteznek x és y egész számok úgy, hogy ax + by = 1 (lásd még: Bézout-tétel).
- A b egész számnak van multiplikatív inverze modulo a: tehát létezik olyan y egész szám, hogy by ≡ 1 (mod a). Más szavakkal, b egységelem a Z/aZ modulo a gyűrűjében.
A fentiekből következően, ha a és b relatív prímek, és br ≡ bs (mod a), akkor r ≡ s (mod a) (mert „oszthatunk b-vel” modulo a számolva). Továbbá, ha a és b1 relatív prímek, valamint a és b2 is relatív prímek, akkor a és b1b2 szintén relatív prímek (mert az egységelemek szorzata szintén egységelem).
Ha a és b relatív prímek, és a osztója a bc szorzatnak, akkor a osztója c-nek. Ez tekinthető Euklidész híres lemmájának általánosításaként, amely kimondja, hogy ha p prím, és p osztója a bc szorzatnak, akkor vagy p osztója b-nek, vagy p osztója c-nek. Ez tekinthető Euklidész híres lemmájának általánosításaként, amely kimondja, hogy ha p prím, és p osztója a bc szorzatnak, akkor vagy p osztója b-nek, vagy p osztója c-nek.
Szemléletesen: a és b egész számok csakkor relatív prímek, ha a Descartes-féle koordinátarendszerben az (a, b) koordinátájú pont „látszik” az origóból, azaz nincsen egész koordinátájú pont az origó és az (a, b) pont között. (Lásd az 1. ábrát.)
Annak a valószínűsége, hogy két véletlenül választott egész szám relatív prím, 6/π2 (lásd Pi), ami körülbelül 60%. (lásd lentebb)
A természetes számok köréből vett a és b csakkor relatív prímek, ha 2a − 1 és 2b − 1 is relatív prímek.
[szerkesztés] Relatív prím számok szorzatának osztói a tényezők osztói szorzatai
- Legyenek a osztói a1, a2, ..., aj; ezek halmaza legyen A és összegük legyen s(A); míg b osztói legyenek b1, b2, ..., bk, s ezek halmaza legyen B és összegük s(B) (j,k egynél nagyobb természetes számok)!
- Ekkor egy A-beli x és egy B-beli y szám szorzata biztosan osztója ab-nek, hiszen az oszthatóság definíciója szerint léteznek olyan q,r egész számok, a=xq és b=yr, és így ab=(xq)(yr)=(xy)qr, ami azt jelenti, (xy) tényleg osztója ab-nek.
- Fordítva, ab egy osztójának prímfelbontását képezve, ezek a relatív prímség miatt két közös elem nélküli csoportra oszlanak: a prímosztói, illetve b prímosztói; a két diszjunkt csoport elemeinek szorzatát külön-külön képezve pedig részint a, részint pedig b egy osztóját kapjuk.
- A 2.1. és 2.2. gondolatmenetek eredményét összefoglalva adódik, hogy éppen a és b osztóinak szorzatai adják ab osztóit, vagyis ezek halmaza C = {xy | x∈A, y∈B}. Tehát A és B elemeit összeszorozva kapjuk az ab osztóit,
E tételre épül a d(n) ("osztókszáma") és a σ(n) ("osztókösszege") függvény (gyenge) multiplikativitásának bizonyítása.
[szerkesztés] Valószínűség
Véletlenszerűen kiválasztva két egész számot, legyenek A és B, feltehető a kérdés, hogy mi annak a valószínűsége, hogy A és B relatív prímek. Ennek a meghatározásánál kényelmes azt a meghatározást használnunk, hogy A és B akkor és csak akkor relatív prímek, ha nincs olyan prímszám, ami mindkettőnek osztója lenne (lásd a számelmélet alaptételét).
Annak a valószínűsége, hogy egy tetszőleges szám osztható p prímmel (vagy bármely egésszel) éppen 1 / p. Így annak a valószínűsége, hogy mindkét szám osztható ezzel a prímmel, 1 / p2, annak a valószínűsége pedig, hogy legalább egyikük nem osztható vele, 1 − 1 / p2. Ezért, annak a valószínűségét, hogy két szám relatív prím, a következő szorzat adja:

Itt ζ a Riemann-féle zéta-függvény, a
pedig a prímszámok halmazát jelöli. Általánosságban, annak a valószínűsége, hogy k darab véletlenül kiválasztott egész szám relatív prím, 1 / ζ(k).
Gyakran nem világos, mint értünk azon, hogy „véletlenül kiválasztott egész szám”. Talán úgy könnyű ezt megérteni, hogy föltesszük, hogy véletlenszerűen kiválasztunk egy egész számot 1 és N egész szám között. Ekkora az N felső határhoz létezik egy PN valószínűség arra nézve, hogy a két véletlenül választott szám relatív prím. Ez a valószínűség sohasem lesz pontosan 6 / π2, de ahogy egyre nagyobb N-eket veszünk,
,
.
[szerkesztés] Lásd még
- Legnagyobb közös osztó
- Bézout-tétel
- Euklidészi algoritmus
[szerkesztés] Források
- az angol Wikipedia szócikke


Based on work by