Primitív gyök

A Wikipédiából, a szabad enciklopédiából

Ha n>1 természetes szám,akkor g primitív gyök modulo n, ha a g, g2,…,gφ(n) hatványok különböző maradékot adnak n-nel osztva, azaz g rendje modulo n pontosan φ(n). Itt φ(n) az Euler-féle φ-függvény. Más szóval, g hatványai a redukált maradékrendszert adják modulo n. Ha például n=5, akkor g=2 megfelel: hatványai rendre 2,4,3,1 modulo 5.

Először Legendre bizonyította be 1798-ban kiadott Théorie des nombres című könyvében, hogy minden p prímszámra létezik primitív gyök modulo p.

Primitív gyök pontosan az n=2, 4, pk, 2pk alakú számokra létezik, ahol p páratlan prímszám. Ha n=2k, ahol k≥3, akkor nincs primitív gyök modulo n, de teljes redukált maradékrendszert adnak az 5,52,…,5t,-5,-52,…,-5t maradékosztályok, ahol t=2k-2.

Nevezetes probléma, hogy mekkora egy p prímszámra vonatkozó legkisebb primitív gyök. Erdős Pál például a \sqrt{p}(\log p)^{17} becslést adta 1945-ben. A legjobb ismert becslés O(p^{1/4+\varepsilon}) (D. A. Burgess, 1962) míg a Riemann-sejtést feltéve 70 (log p)2-es felső korlát adódik.

Egy másik kérdés Artin sejtése: ha a egy -1-től különböző egész szám, ami nem négyzetszám, akkor végtelen sok prímszámra a primitív gyök. Ezzel kapcsolatban Gupta és Ram Murty eredményei után Heath-Brown bebizonyította, hogy legfeljebb két prímszámra és legfeljebb három pozitív négyzetmentes számra nem teljesülhet az állítás. Az érdekes az a dologban, hogy még mindig nem tudunk egyetlen prímet sem, amire igaz az állítás.

Erdős egy érdekes sejtése, hogy ha a p prím elég nagy, akkor van olyan q<p primitív gyöke, hogy q prím.