Primitív gyök (számelmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. február 7-én felülvizsgált verziótól ; az ellenőrzések 12 szerkesztést igényelnek .

A modulo m primitív gyök olyan g egész szám , amelyre

g^{\varphi (m)}\equiv 1{\pmod {m))

és

g^{\ell }\not \equiv 1{\pmod {m))

nál nél

1\leq \ell <\varphi (m),

hol van az Euler-függvény . Más szóval, egy primitív gyök egy modulo m maradékgyűrű multiplikatív csoportjának generátora . $\varphi(m)$

Annak érdekében, hogy ne ellenőrizzen mindent től -ig , elegendő három feltételt ellenőrizni: $\ell$ $egy$ $\varphi(m)$

A szám koprím -e és ha nem, akkor ez nem primitív gyök. $g$ $m$
Mivel , mindig páros szám , minden szám esetén, akkor van legalább egy prímosztója - egy prímszám , ezért ahhoz, hogy jelentős számú nem gyököt kiszűrjünk, elegendő olyan számot ellenőrizni, amely illeszkedik a primitív gyök modulo . [1] Ha az eredmény +1 m , akkor g nem gyök, ellenkező esetben az eredmény -1 m, ha g egy esetleg primitív gyök. $\varphi(m)$ $m>2$ $\varphi(m)$ $2$ $g^{\varphi (m)/2}\not \equiv 1{\pmod {m))$ $m$ $\equiv$ $\equiv$
Ezután meg kell győződnie arról, hogy minden , ahol a faktorizálás eredményeként kapott szám prímosztója . $g^{\ell }\not \equiv 1{\pmod {m))$ $\ell ={\frac {\varphi (m)}{p))$ $p$ $\varphi(m)$

Tulajdonságok

Létezés

A primitív gyökök csak az alak modulusaiban léteznek $m$

{\displaystyle m=2,4,p^{a},2p^{a))

ahol egy prímszám és egy egész szám. Csak ezekben az esetekben a modulo m maradékgyűrű multiplikatív csoportja ciklikus rendű csoport . $p>2$ $a\geqslant 1$ $\varphi(m)$

Modulo szám index

Egy g primitív gyöknél a g 0 =1, g , …, g φ( m ) − 1 hatványai összehasonlíthatatlanok modulo m és redukált modulo m maradékrendszert alkotnak . Ezért minden számhoz egy m -hez tartozó koprím van egy l, 0 ⩽ ℓ ⩽ φ( m ) − 1 kitevő, úgy, hogy

g^{\ell }\equiv a{\pmod {m)).

Az ilyen ℓ számot a indexnek nevezzük g bázisban .

Mennyiség

Ha modulo m létezik egy g primitív gyök , akkor van φ(φ( m )) különböző modulo m primitív gyök , és mindegyiknek van alakja , ahol és . $g^{k}$ $1\leq k\leq \varphi (m)-1$ $(k,\varphi (m))=1$

Minimális gyökér

Vinogradov kutatása kimutatta, hogy van olyan állandó , hogy minden prímhez van egy primitív gyök . Más szavakkal, egyszerű modulok esetén a minimális primitív gyök sorrendje . Victor Shupe matematikus , a Torontói Egyetemről kimutatta, hogy ha az „ általánosított Riemann-hipotézis ” igaz, akkor a primitív gyök a természetes sorozat első számai között van [2] . $C$ $p$ $g<C{\sqrt {p))$ $p$ $O({\sqrt {p)))$ $O(\log ^{6}{p})$

Történelem

Az egyszerű modulok primitív gyökereit Euler vezette be , de az egyszerű modulok primitív gyökeinek létezését csak Gauss bizonyította az " Aritmetikai vizsgálatok " (1801) című művében. $p$ $p$

Példák

A 3-as szám egy primitív modulo 7 gyök. Ennek megtekintéséhez elegendő minden 1-től 6-ig terjedő számot egy hármas modulo 7 bizonyos hatványaként ábrázolni:

3^{1}\equiv 3\ {\pmod {7))

3^{2}\equiv 2\ {\pmod {7))

3^{3}\equiv 6\ {\pmod {7))

3^{4}\equiv 4\ {\pmod {7))

3^{5}\equiv 5\ {\pmod {7))

3^{6}\equiv 1\ {\pmod {7))

Példák a legkisebb primitív gyökök modulo m -re ( A046145 szekvencia az OEIS -ben ):

m modul	2	3	négy	5	6	7	nyolc	9	tíz	tizenegy	12	13	tizennégy
primitív gyökér	egy	2	3	2	5	3	—	2	3	2	—	2	3

Lásd még

Jegyzetek

↑ Primitív gyökér – versenyképes programozási algoritmusok . cp-algorithms.com . Letöltve: 2020. október 27. Az eredetiből archiválva : 2020. október 24. (határozatlan)
↑ Bach, Eric; Shallit, Jeffrey. Algoritmikus számelmélet (I. kötet: Hatékony algoritmusok). - Cambridge: The MIT Press, 1996. - P. 254. - ISBN 978-0-262-02405-1 .

Irodalom

Vinogradov I.M. 6. fejezet: Primitív gyökök és indexek // A számelmélet alapjai. - 1952. - 182 p.
Nesterenko Yu. V. 7. fejezet: Primitív gyökerek és indexek // Számelmélet. - M . : "Akadémia", 2008. - 464 p.

Linkek

Primitive Roots on MAXimal Archiválva : 2011. december 1. a Wayback Machine -nél
Weisstein, Eric W. Primitive Root (angol) a Wolfram MathWorld webhelyén .

Szótárak és enciklopédiák	Nagy orosz