Relatív prímek

A Wikipédiából, a szabad enciklopédiából

A matematikában az a és b egész számok esetén azt mondjuk, hogy az a a b-hez relatív prím, vagy egyszerűen a és b relatív prímek, ha az 1-en és −1-en kívül nincs más közös osztójuk. Vagy ami ezzel ekvivalens, ha a és b legnagyobb közös osztója 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. Minden prímszám tetszőleges másikhoz relatív prím, illetve egy prímszámhoz minden nála kisebb természetes szám relatív prím. 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 és n közötti, n-hez képest relatív prím egészek számát.

Tulajdonságok[forrásszöveg szerkesztése]

1. ábra: a 4 és a 9 relatív prímek, mert az átló egyetlen rácsponton sem megy keresztül

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-lemma).
  • A b egész számhoz találunk olyan y egész számot, hogy by ≡ 1 (mod a). Más szavakkal, a b által reprezentált elem invertálható elem a modulo a maradékosztályok Za gyűrűjében.

A fentiekből következően, ha a és b relatív prímek, és brbs (mod a), akkor rs (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.

Szemléletesen: a és b egész szám pontosan akkor relatív prímek, ha a Descartes-féle koordináta-rendszerben 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, ami körülbelül 60%[1].

A természetes számok köréből vett a és b pontosan akkor relatív prímek, ha 2a ‒ 1 és 2b ‒ 1 is relatív prímek.

A relatív prímek binér relációja nem tranzitív, mivel például a 2 és a 3, valamint a 3 és a 4 relatív prímek, de a 2 és a 4 nem.

Relatív prím számok szorzatának osztói a tényezők osztói szorzatai[forrásszöveg szerkesztése]

  1. 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)!
    1. 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.
    2. 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.
  2. 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ók száma") és a σ(n) ("osztók összege") függvény (gyenge) multiplikativitásának bizonyítása.

Valószínűség[forrásszöveg szerkesztése]

Feltehető a kérdés, hogy mi annak a valószínűsége, hogy véletlenszerűen kiválasztva két egész számot, ezek egymáshoz relatív prímek. Két szám, akkor és csak akkor relatív prím egymáshoz, ha nincs közös prímosztójuk, ez a számelmélet alaptétele szerint könnyen igazolható. Ezt az átfogalmazást használjuk fel a kérdés megválaszolására.

Jelölje Q(N) azon (a,b) párok számát, ahol a és b is 1 és N közé eső természetes szám és a, b relatív prímek. Be fogjuk látni, hogy

Jelölje a prímszámok sorozatát. Jelölje azon (a,b) párok számát, amikre és egyike sem közös osztója a-nak és b-nek. Nyilván .

Meghatározzuk -et. Ha N -rel osztható szám, mondjuk , akkor

mivel annak valószínűsége, hogy a és b mindkettő osztható -vel és ezek az események függetlenek (a szita-formulára is hivatkozhatunk).

Legyen most N tetszőleges: , ahol a maradékos osztás tétele szerint.

Ekkor

(hozzászámolva az összes párt, aminek valamelyik tagja és között van). Ezért

továbbá nyilván

és innen

Most visszatérünk az eredeti -hez. és legfeljebb annyi, ahány olyan (a,b) pár van, aminek mindkét tagja osztható egy -nél nagyobb prímszámmal, innen

ahol az x valós szám egész részét jelöli. Ez viszont kisebb, mint

hiszen mindig teljesül

Így az adódott, hogy

és limeszt véve

ahol a jobb oldali szorzatban prím p-ket kell venni. Ez viszont a zéta-függvényre vonatkozó ismereteink alapján .

Az általános eset igazolása ugyanúgy megy: annak valószínűsége, hogy egy véletlenszerűen kiválasztott szám-k-as tagjainak nincs közös osztója, .


Gyűrűkben[forrásszöveg szerkesztése]

A relatív prímek fogalma kiterjeszthető az egységelemes kommutatív gyűrűkre. Ezekben a gyűrűkben egységnek nevezzük azokat az elemeket, amelyek az összes elemnek osztói. A gyűrű két eleme relatív prím, ha közös osztóik éppen az egységek.

Az egész számok gyűrűjében az egységek az 1 és a -1. Eszerint a 2 és a -3 relatív prímek.

Jegyzetek[forrásszöveg szerkesztése]

  1. Mertens, 1874