Primitiv rot (talteori)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 februari 2020; kontroller kräver 12 redigeringar .

En primitiv rot modulo m är ett heltal g så att

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

och

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

på

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

var är Euler-funktionen . Med andra ord är en primitiv rot en generator av den multiplikativa gruppen av en restring modulo m . $\varphi(m)$

För att inte kontrollera allt från till räcker det med att kontrollera tre villkor: $\aln$ $ett$ $\varphi(m)$

Är talet coprime med , och om inte, så är detta inte en primitiv rot. $g$ $m$
Eftersom , alltid ett jämnt tal , för alla tal , då det har minst en primtal divisor - ett primtal , för att sålla bort ett betydande antal icke-rötter räcker det därför att leta efter ett tal som passar primitiv rot modulo . [1] Om resultatet är +1 m , så är g inte en rot, annars är resultatet -1 m när g är en möjligen primitiv rot. $\varphi(m)$ $m>2$ $\varphi(m)$ $2$ $g^{\varphi (m)/2}\not \equiv 1{\pmod {m))$ $m$ $\mots$ $\mots$
Därefter bör du se till att för alla , där är en primtalsdelare av talet som erhålls som ett resultat av dess faktorisering. $g^{\ell }\not \equiv 1{\pmod {m))$ $\ell ={\frac {\varphi (m)}{p))$ $sid$ $\varphi(m)$

Egenskaper

Existens

Primitiva rötter existerar endast i formens moduler $m$

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

där är ett primtal och är ett heltal. Endast i dessa fall är den multiplikativa gruppen av restringens modulom en cyklisk ordningsgrupp . $p>2$ $a\geqslant 1$ $\varphi(m)$

Modulo nummer index

För en primitiv rot g är dess potenser g 0 =1, g , …, g φ( m ) − 1 ojämförliga modulo m och bildar ett reducerat system av rester modulo m . Därför, för varje tal ett samprimtal till m , finns det en exponent l, 0 ⩽ ℓ ⩽ φ( m ) − 1, så att

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

Ett sådant tal ℓ kallas index för a i basen g .

Kvantitet

Om modulo m finns en primitiv rot g , så finns det φ(φ( m )) olika primitiva rötter modulo m , och alla har formen , där och . $g^{k}$ $1\leq k\leq \varphi (m)-1$ $(k,\varphi (m))=1$

Minsta rot

Vinogradovs forskning visade att det finns en sådan konstant att det för varje primtal finns en primitiv rot . Med andra ord, för enkla moduler är den minsta primitiva roten av ordning . Matematiker Victor Shupe från University of Toronto visade att om den " generaliserade Riemann-hypotesen " är sann, så är den primitiva roten bland de första talen i den naturliga serien [2] . $C$ $sid$ $g<C{\sqrt {p))$ $sid$ $O({\sqrt {p)))$ $O(\log ^{6}{p})$

Historik

Primitiva rötter för enkla moduler introducerades av Euler , men förekomsten av primitiva rötter för alla enkla moduler bevisades endast av Gauss i " Arithmetical Investigations " (1801). $sid$ $sid$

Exempel

Siffran 3 är en primitiv rot modulo 7. För att se detta räcker det att representera varje tal från 1 till 6 som en viss styrka av en trippel modulo 7:

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

Exempel på minsta primitiva rötter modulo m (sekvens A046145 i OEIS ):

Modul m	2	3	fyra	5	6	7	åtta	9	tio	elva	12	13	fjorton
primitiv rot	ett	2	3	2	5	3	—	2	3	2	—	2	3

Se även

Anteckningar

↑ Primitiva rot - konkurrenskraftiga programmeringsalgoritmer . cp-algorithms.com . Hämtad 27 oktober 2020. Arkiverad från originalet 24 oktober 2020. (obestämd)
↑ Bach, Eric; Shallit, Jeffrey. Algoritmisk talteori (Vol I: Effektiva algoritmer). - Cambridge: The MIT Press, 1996. - S. 254. - ISBN 978-0-262-02405-1 .

Litteratur

Vinogradov I.M. Kapitel 6. Primitiva rötter och index // Fundamentals of Number Theory. - 1952. - 182 sid.
Nesterenko Yu. V. Kapitel 7. Primitiva rötter och index // Talteori. - M . : "Akademin", 2008. - 464 sid.

Länkar

Primitiva rötter på MAXimal Arkiverad 1 december 2011 på Wayback Machine
Weisstein, Eric W. Primitive Root (engelska) på Wolfram MathWorld- webbplatsen .

Ordböcker och uppslagsverk	Stor ryss