Relatív prímek

A Wikipédiából, a szabad lexikonbó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ím, ha az 1-en és −1-en kívül nincs más közös osztójuk. Vagy ami ezzel ekvivalensen, 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 and n − 1 közötti, n-hez képest relatív prím egészek számát.

Tartalomjegyzék

1 Tulajdonságok
- 1.1 Relatív prím számok szorzatának osztói a tényezők osztói szorzatai
2 Valószínűség
3 Lásd még
4 Források

[szerkesztés] 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-tétel).
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 inverálható elem a moduló 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. 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átarendszerben 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/π² (lásd Pi), ami körülbelül 60%. (lásd lentebb)

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.

[szerkesztés] Relatív prím számok szorzatának osztói a tényezők osztói szorzatai

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

[szerkesztés] 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^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ábá 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 jobboldali szorzatban prím p-ket kell venni. Ez viszont a zéta-függvényre vonatkozó ismereteink alapján $1 / ζ(2) = 6 / π 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 / ζ(k)$ .