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

\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^2_1}\right)\cdots \left(1-\frac{1}{p^2_r}\right)N^2

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

Legyen most N tetszőleges: N=p_1\cdots p_rM+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^2_1}\right)\cdots\left(1-\frac{1}{p^2_r}\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_rM)}{N^2}=\left(1-\frac{1}{p^2_1}\right)\cdots \left(1-\frac{1}{p^2_r}\right) \frac{(p_1\cdots p_rM)^2}{N^2}

és innen

\frac{Q_r(N)}{N^2}\to \left(1-\frac{1}{p^2_1}\right)\cdots \left(1-\frac{1}{p^2_r}\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^2_{r+1}}\right]+ \left[\frac{N^2}{p^2_{r+2}}\right]\cdots<N^2\left(\frac{1}{p^2_{r+1}}+\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[szerkesztés | 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[szerkesztés | forrásszöveg szerkesztése]

  1. Mertens, 1874