Relatív prímek

(Relatív prím szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2023. november 13.

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. A definíciókból egyenesen következik, hogy 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. Ezen kívül egy adott prímszámhoz minden olyan természetes szám relatív prím, amely nem a többszöröse. Az 1 minden egész számhoz relatív prím; a 0 csak az 1-hez és a ‒1-hez. Továbbá két egymást követő természetes szám is mindig relatív prímek egymáshoz.

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

szerkesztés
 
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ő Eukleidé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

szerkesztés
  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

szerkesztés

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

szerkesztés

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.

További információk

szerkesztés
  1. Mertens, 1874