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
szerkesztésAz „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 br ≡ bs (mod a), akkor r ≡ s (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ő 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/π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- 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)!
- 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.
- 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ó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ésFeltehető 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
Jelölje a prímszámok sorozatát. Jelölje azon (a,b) párok számát, amikre és egyike sem közös osztója a-nak és b-nek. Nyilván .
Meghatározzuk -et. Ha N -rel osztható szám, mondjuk , akkor
mivel annak valószínűsége, hogy a és b mindkettő osztható -vel és ezek az események függetlenek (a szita-formulára is hivatkozhatunk).
Legyen most N tetszőleges: , ahol a maradékos osztás tétele szerint.
Ekkor
(hozzászámolva az összes párt, aminek valamelyik tagja és között van). Ezért
továbbá nyilván
és innen
Most visszatérünk az eredeti -hez. és legfeljebb annyi, ahány olyan (a,b) pár van, aminek mindkét tagja osztható egy -nél nagyobb prímszámmal, innen
ahol az x valós szám egész részét jelöli. Ez viszont kisebb, mint
hiszen mindig teljesül
Így az adódott, hogy
és limeszt véve
ahol a jobb oldali szorzatban prím p-ket kell venni. Ez viszont a zéta-függvényre vonatkozó ismereteink alapján .
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, .
Gyűrűkben
szerkesztésA 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
szerkesztésJegyzetek
szerkesztés- ↑ Mertens, 1874