Relatív prímek

A Wikipédiából, a szabad lexikonból.

A matematikában a és b egész számokat relatív prímeknek nevezzük, ha 1-en és −1-en kívül nincs más közös osztójuk. Vagy ezzel ekvivalensen, ha legnagyobb közös osztójuk 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 prímszámok a 0-án kívül minden összetett számhoz relatív prímek. 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

[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
Nagyít
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ámnak van multiplikatív inverze modulo a: tehát létezik olyan y egész szám, hogy by ≡ 1 (mod a). Más szavakkal, b egységelem a Z/aZ modulo a 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. 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ámok csakkor 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/π2 (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 csakkor relatív prímek, ha 2a − 1 és 2b − 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

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

Véletlenszerűen kiválasztva két egész számot, legyenek A és B, feltehető a kérdés, hogy mi annak a valószínűsége, hogy A és B relatív prímek. Ennek a meghatározásánál kényelmes azt a meghatározást használnunk, hogy A és B akkor és csak akkor relatív prímek, ha nincs olyan prímszám, ami mindkettőnek osztója lenne (lásd a számelmélet alaptételét).

Annak a valószínűsége, hogy egy tetszőleges szám osztható p prímmel (vagy bármely egésszel) éppen 1 / p. Így annak a valószínűsége, hogy mindkét szám osztható ezzel a prímmel, 1 / p2, annak a valószínűsége pedig, hogy legalább egyikük nem osztható vele, 1 − 1 / p2. Ezért, annak a valószínűségét, hogy két szám relatív prím, a következő szorzat adja:

\prod_{p \in \mathbb{P}} \left(1-\frac{1}{p^2}\right) = \frac{1}{ \prod \frac{1}{1-p^{-2}}} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}

Itt ζ a Riemann-féle zéta-függvény, a \mathcal{P} pedig a prímszámok halmazát jelöli. Általánosságban, annak a valószínűsége, hogy k darab véletlenül kiválasztott egész szám relatív prím, 1 / ζ(k).

Gyakran nem világos, mint értünk azon, hogy „véletlenül kiválasztott egész szám”. Talán úgy könnyű ezt megérteni, hogy föltesszük, hogy véletlenszerűen kiválasztunk egy egész számot 1 és N egész szám között. Ekkora az N felső határhoz létezik egy PN valószínűség arra nézve, hogy a két véletlenül választott szám relatív prím. Ez a valószínűség sohasem lesz pontosan 6 / π2, de ahogy egyre nagyobb N-eket veszünk, N \to \infty, P_N \to 6/\pi^2.

[szerkesztés] Lásd még

[szerkesztés] Források

  • az angol Wikipedia szócikke