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

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ő 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/π², 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.

További információk

• Alice és Bob - 17. rész: Alice és Bob ókori haverja
• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat