Primitiv rod (talteori)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. februar 2020; checks kræver 12 redigeringer .

En primitiv rod modulo m er et heltal g sådan, at

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

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

på

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

hvor er Euler-funktionen . Med andre ord er en primitiv rod en generator af den multiplikative gruppe af en restring modulo m . $\varphi(m)$

For ikke at kontrollere alt fra til , er det nok at kontrollere tre forhold: $\ell$ $en$ $\varphi(m)$

Er tallet coprime med , og hvis ikke, så er dette ikke en primitiv rod. $g$ $m$
Da , altid et lige tal , for alle tal , så har det mindst én primtal divisor - et primtal , derfor, for at luge ud et betydeligt antal ikke-rødder, er det derfor nok at tjekke for et tal, der passer til primitiv rod modulo . [1] Hvis resultatet er +1 m, så er g ikke en rod, ellers er resultatet -1 m, når g er en muligvis primitiv rod. $\varphi(m)$ $m>2$ $\varphi(m)$ $2$ $g^{\varphi (m)/2}\not \equiv 1{\pmod {m))$ $m$ $\ækvivalent$ $\ækvivalent$
Dernæst skal du sikre dig, at for alle , hvor er en primtal divisor af det tal , der opnås som et resultat af dets faktorisering. $g^{\ell }\not \equiv 1{\pmod {m))$ $\ell ={\frac {\varphi (m)}{p))$ $s$ $\varphi(m)$

Egenskaber

Eksistens

Primitive rødder eksisterer kun i moduli af formen $m$

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

hvor er et primtal og er et heltal. Kun i disse tilfælde er den multiplikative gruppe af restringens modulom en cyklisk ordensgruppe . $p>2$ $a\geqslant 1$ $\varphi(m)$

Modulo nummer indeks

For en primitiv rod g er dens potenser g 0 =1, g , …, g φ( m ) − 1 uforlignelige modulo m og danner et reduceret system af rester modulo m . Derfor er der for hvert tal et coprime til m en eksponent l, 0 ⩽ ℓ ⩽ φ( m ) − 1, således at

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

Et sådant tal ℓ kaldes indekset for a i grundtallet g .

Mængde

Hvis modulo m eksisterer en primitiv rod g , så er der φ(φ( m )) forskellige primitive rødder modulo m , og alle har formen , hvor og . $g^{k}$ $1\leq k\leq \varphi (m)-1$ $(k,\varphi (m))=1$

Minimum root

Vinogradovs forskning viste, at der er en sådan konstant , at der for hver prime er en primitiv rod . Med andre ord, for simple moduler er den minimale primitive rod af orden . Matematiker Victor Shupe fra University of Toronto viste, at hvis den " generaliserede Riemann-hypotese " er sand, så er den primitive rod blandt de første tal i den naturlige række [2] . $C$ $s$ $g<C{\sqrt {p}}$ $s$ $O({\sqrt {p)))$ $O(\log ^{6}{p})$

Historie

Primitive rødder til simple moduler blev introduceret af Euler , men eksistensen af primitive rødder til simple moduler blev kun bevist af Gauss i " Arithmetical Investigations " (1801). $s$ $s$

Eksempler

Tallet 3 er en primitiv rod modulo 7. For at se dette er det nok at repræsentere hvert tal fra 1 til 6 som en vis styrke af en tredobbelt 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))

Eksempler på mindste primitive rødder modulo m (sekvens A046145 i OEIS ):

Modul m	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten
primitiv rod	en	2	3	2	5	3	—	2	3	2	—	2	3

Se også

Noter

↑ Primitive rod - konkurrencedygtige programmeringsalgoritmer . cp-algorithms.com . Hentet 27. oktober 2020. Arkiveret fra originalen 24. oktober 2020. (ubestemt)
↑ Bach, Eric; Shallit, Jeffrey. Algoritmisk talteori (Vol I: Effektive algoritmer). - Cambridge: The MIT Press, 1996. - S. 254. - ISBN 978-0-262-02405-1 .

Litteratur

Vinogradov I.M. Kapitel 6. Primitive rødder og indekser // Fundamentals of Number Theory. - 1952. - 182 s.
Nesterenko Yu. V. Kapitel 7. Primitive rødder og indekser // Talteori. - M . : "Academy", 2008. - 464 s.

Links

Primitive Roots on MAXimal Arkiveret 1. december 2011 på Wayback Machine
Weisstein, Eric W. Primitive Root (engelsk) på Wolfram MathWorld- webstedet .

Ordbøger og encyklopædier	Stor russer