Relatív prímek

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

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 Z_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 b₁ relatív prímek, valamint a és b₂ is relatív prímek, akkor a és b₁b₂ 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/π², ami körülbelül 60%.

A természetes számok köréből vett a és b pontosan akkor relatív prímek, ha 2^a ‒ 1 és 2^b ‒ 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

1. Legyenek a osztói a₁, a₂, …, a_j; ezek halmaza legyen A és összegük legyen s(A); míg b osztói legyenek b₁, b₂, …, b_k, 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

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

${\frac {Q(N)}{N^{2}}}\to {\frac {6}{\pi ^{2}}}.$

Jelölje $p_{1}<p_{2}<\cdots$ a prímszámok sorozatát. Jelölje $Q_{r}(N)$ azon (a,b) párok számát, amikre $1\leq a,b\leq N$ és $p_{1},\dots ,p_{r}$ egyike sem közös osztója a-nak és b-nek. Nyilván $Q(N)\leq Q_{r}(N)$.

Meghatározzuk $\lim Q_{r}(N)/N^{2}$-et. Ha N $p_{1}\cdots p_{r}$-rel osztható szám, mondjuk $N=p_{1}\cdots p_{r}M$, akkor

$Q_{r}(N)=\left(1-{\frac {1}{p_{1}^{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}^{2}}}\right)N^{2}$

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

Legyen most N tetszőleges: $N=p_{1}\cdots p_{r}M+K$, ahol $0\leq K<p_{1}\cdots p_{r}$ a maradékos osztás tétele szerint.

Ekkor

$Q_{r}(N)<Q_{r}(p_{1}\cdots p_{r}M)+2p_{1}\cdots p_{r}N$

(hozzászámolva az összes párt, aminek valamelyik tagja $p_{1}\cdots p_{r}M$ és $N$ között van). Ezért

${\frac {Q_{r}(N^{2})}{N^{2}}}<\left(1-{\frac {1}{p_{1}^{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}^{2}}}\right)+{\frac {2p_{1}\cdots p_{r}}{N}},$

továbbá nyilván

${\frac {Q_{r}(N)}{N^{2}}}\geq {\frac {Q_{r}(p_{1}\cdots p_{r}M)}{N^{2}}}=\left(1-{\frac {1}{p_{1}^{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}^{2}}}\right){\frac {(p_{1}\cdots p_{r}M)^{2}}{N^{2}}}$

és innen

${\frac {Q_{r}(N)}{N^{2}}}\to \left(1-{\frac {1}{p_{1}^{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}^{2}}}\right).$

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

$Q_{r}(N)-Q(N)\leq \left[{\frac {N^{2}}{p_{r+1}^{2}}}\right]+\left[{\frac {N^{2}}{p_{r+2}^{2}}}\right]\cdots <N^{2}\left({\frac {1}{p_{r+1}^{2}}}+\cdots \right),$

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

${\frac {N^{2}}{p_{r}}}$

hiszen mindig teljesül

${\frac {1}{(n+1)^{2}}}+{\frac {1}{(n+2)^{2}}}+\cdots <{\frac {1}{n}}.$

Így az adódott, hogy

${\frac {Q_{r}(N)}{N^{2}}}-{\frac {1}{p_{r}}}<{\frac {Q(N)}{N^{2}}}<{\frac {Q_{r}(N)}{N^{2}}}$

és limeszt véve

$\lim {\frac {Q(N)}{N^{2}}}=\prod \left(1-{\frac {1}{p^{2}}}\right)$

ahol a jobb oldali szorzatban prím p-ket kell venni. Ez viszont a zéta-függvényre vonatkozó ismereteink alapján $1/\zeta (2)=6/\pi ^{2}$.

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, $1/\zeta (k)$.

Gyűrűkben

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.