Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(609 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Primitive root modulo ''n''}}
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.
In [[modular arithmetic]], a branch of [[number theory]],  a '''primitive root modulo ''n''''' is any number ''g'' with the property that any number [[coprime]] to ''n'' is [[Modular arithmetic#Congruence relation|congruent]] to a power of ''g'' modulo ''n''. In other words, ''g'' is a generator of the [[multiplicative group of integers modulo n]]. That is, for every integer ''a'' [[coprime]] to ''n'', there is an integer ''k'' such that ''g''<sup>''k''</sup> ≡ ''a'' (mod ''n''). Such ''k'' is called the '''index''' or '''[[discrete logarithm]]''' of ''a'' to the base ''g'' modulo ''n''.


[[Carl Friedrich Gauss|Gauss]] defined primitive roots in Article 57 of the [[Disquisitiones Arithmeticae]] (1801), where he credited [[Euler]] with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist. In fact, the ''Disquisitiones'' contains two proofs: the one in Article 54 is a nonconstructive [[Existence theorem|existence proof]], while the other in Article 55 is [[Constructive proof|constructive]].
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


==Elementary example==
Registered users will be able to choose between the following three rendering modes:  
The number 3 is a primitive root modulo 7<ref>http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html</ref> because
::<math>
\begin{array}{rcrcrcrcrcr}
3^1 &=&  3 &=& 3^0 \times 3 &\equiv& 1 \times 3 &=&  3 &\equiv& 3 \pmod 7 \\
3^2 &=&  9 &=& 3^1 \times 3 &\equiv& 3 \times 3 &=&  9 &\equiv& 2 \pmod 7 \\
3^3 &=&  27 &=& 3^2 \times 3 &\equiv& 2 \times 3 &=&  6 &\equiv& 6 \pmod 7 \\
3^4 &=&  81 &=& 3^3 \times 3 &\equiv& 6 \times 3 &=& 18 &\equiv& 4 \pmod 7 \\
3^5 &=& 243 &=& 3^4 \times 3 &\equiv& 4 \times 3 &=& 12 &\equiv& 5 \pmod 7 \\
3^6 &=& 729 &=& 3^5 \times 3 &\equiv& 5 \times 3 &=& 15 &\equiv& 1 \pmod 7 \\
\end{array}
</math>


Here we see that the period of 3<sup>k</sup> modulo 7 is 6.  The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. Curiously, permutations created in this way (and their circular shifts) have been shown to be [[Costas array#Welch|Costas arrays]].
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


==Definition==
<!--'''PNG'''  (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


If ''n'' is a positive [[integer]], the integers between 1 and ''n''&minus;1 which are [[coprime]] to ''n'' (or equivalently, the [[congruence class]]es [[coprime]] to ''n'') form a [[group (mathematics)|group]] with multiplication [[Modular arithmetic|modulo]] ''n'' as the operation; it is denoted by '''Z'''<sub>''n''</sub><sup>&times;</sup> and is called the [[group of units]] modulo ''n'' or the group of primitive classes modulo ''n''. As explained in the article [[multiplicative group of integers modulo n|multiplicative group of integers modulo ''n'']], this group is [[cyclic group|cyclic]] [[if and only if]] ''n'' is equal to 2, 4, ''p''<sup>''k''</sup>, or 2 ''p''<sup>''k''</sup> where ''p''<sup>''k''</sup> is a power of an odd [[prime number]].<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
'''source'''
</ref><ref>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]]</ref> A [[generating set of a group|generator]] of this cyclic group is called a '''primitive root modulo ''n''''', or a '''primitive element of Z'''<sub>''n''</sub><sup>&times;</sup>.
:<math forcemathmode="source">E=mc^2</math> -->


The order of (i.e. the number of elements in) '''Z'''<sub>''n''</sub><sup>&times;</sup> is given by [[Euler's totient function]] <math>\varphi\left(n\right).</math> [[Euler's theorem]] says that ''a''<sup>φ(''n'')</sup> ≡ 1 (mod ''n'') for every ''a'' coprime to ''n''; the lowest power of ''a'' which is congruent to 1 modulo ''n'' is called the [[multiplicative order]] of ''a'' modulo ''n''. In particular, for ''a'' to be a primitive root modulo ''n'', φ(''n'') has to be the smallest power of ''a'' which is congruent to 1 modulo ''n''.
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


==Examples==
==Demos==


For example, if ''n'' = 14 then the elements of '''Z'''<sub>''n''</sub><sup>&times;</sup> are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. Here is a table of their powers modulo 14:
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:


<code>
  x    x, x<sup>2</sup>, x<sup>3</sup>, ... (mod 14)
  1 :  1
  3 :  3,  9, 13, 11,  5,  1 
  5 :  5, 11, 13,  9,  3,  1
  9 :  9, 11,  1
11 :  11,  9,  1
13 :  13,  1
</code>


The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.
* accessibility:
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


For a second example let ''n'' = 15. The elements of '''Z'''<sub>15</sub><sup>&times;</sup> are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ(15) = 8 of them.
==Test pages ==


<code>
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
  x    x, x<sup>2</sup>, x<sup>3</sup>, ... (mod 15)
*[[Displaystyle]]
  1 :   1
*[[MathAxisAlignment]]
  2 :  2,  4,  8, 1 
*[[Styling]]
  4 :  4,  1
*[[Linebreaking]]
  7 :  7,  4, 13, 1
*[[Unique Ids]]
  8 :  8,  4,  2, 1
*[[Help:Formula]]
11 :  11,  1
13 :  13,  4,  7, 1
14 : 14,  1
</code>


Since there is no number whose order is 8, there are no primitive roots modulo 15.
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
===Table of primitive roots===
==Bug reporting==
 
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
This is Gauss's table of  '''the''' primitive roots from the  ''Disquisitiones''. Unlike most modern authors he did not always choose the smallest primitive root. Instead, he chose 10 if it is a primitive root; if it isn't, he chose whichever root gives 10 the smallest index, and, if there is more than one, chose the smallest of them. This is not only to make hand calculation easier, but is used in  § VI where the periodic decimal expansions of rational numbers are investigated.
 
The rows of the table are labelled with the prime powers (excepting 2, 4, and 8) less than 100; the second column is a primitive root modulo that number. The columns are labelled with the primes less than 97. The entry in row ''p'' column ''q'' is the index of ''q'' modulo ''p'' for the given root.
<blockquote>For example, in row 11, 2 is given as the primitive root, and in column 5 the entry is 4. This means that 2<sup>4</sup> = 16 &equiv; 5 (mod 11). </blockquote>For the index of a composite number, add the indices of its prime factors.<blockquote>For example, in row 11, the index of 6 is the sum of the indices for 2 and 3: 2<sup>1 + 8</sup> = 512 &equiv; 6 (mod 11). The index of 25 is twice the index 5: 2<sup>8</sup> = 256 &equiv; 25 (mod 11). (Of course, since 25 &equiv; 3 (mod 11), the entry for 3 is 8).</blockquote>
 
The table is straightforward for the odd prime powers. But the powers of 2, (16, 32, and 64) do not have primitive roots; instead, the powers of 5 account for one-half of the odd numbers less than the power of 2, and their negatives modulo the power of 2 account for the other half. All powers of 5 are ≡ 5 or 1 (mod 8); the columns headed by numbers ≡ 3 or 7 (mod 8) contain the index of its negative.
<blockquote>For example, modulo 32 the index for 7 is 2, and 5<sup>2</sup> = 25 &equiv; &ndash;7 (mod 32), but the entry for 17 is 4, and 5<sup>4</sup> = 625 &equiv; 17 (mod 32).</blockquote>
 
{|  class="wikitable" style="text-align:center" cellpadding="2"
|+ Primitive roots and indices
(other columns are the indices of integers under respective column headings)
|-
| width="25" | ''n''
| width="25" | root
! width="25" | 2
! width="25" | 3
! width="25" | 5
! width="25" | 7
! width="25" | 11
| width="10" rowspan="34" | &nbsp;
! width="25" | 13
! width="25" | 17
! width="25" | 19
! width="25" | 23
! width="25" | 29
| width="10" rowspan="34" | &nbsp;
! width="25" | 31
! width="25" | 37
! width="25" | 41
! width="25" | 43
! width="25" | 47
| width="10" rowspan="34" | &nbsp;
! width="25" | 53
! width="25" | 59
! width="25" | 61
! width="25" | 67
! width="25" | 71
| width="10" rowspan="34" | &nbsp;
! width="25" | 73
! width="25" | 79
! width="25" | 83
! width="25" | 89
|-
!  3 || 2
| 1
|-
!  5 || 2
| 1 || 3
|-
!  7 || 3
| 2 || 1 || 5
|-
!  9 ||2
| 1 || * || 5 || 4 
|-
!  11 || 2
| 1 || 8 || 4 || 7
|-
!  13 || 6
| 5 || 8 || 9 || 7 || 11
|-
!  16 || 5
| * || 3 || 1 || 2 || 1 || 3
|-
! 17 || 10
| 10 || 11 || 7 || 9 || 13 || 12
|-
!  19 || 10
| 17 || 5 || 2 || 12 || 6 || 13 || 8
|-
!  23 || 10
| 8 || 20 || 15 || 21 || 3 || 12 || 17 || 5
|-
!  25 || 2
| 1 || 7 || * || 5 || 16  || 19 || 13 || 18 || 11 
|-
!  27 || 2
| 1 || * || 5 || 16 || 13 || 8 || 15 || 12 || 11 
|-
!  29 || 10
| 11 || 27 || 18 || 20 || 23 || 2 || 7 || 15 || 24
|-
!  31 || 17
| 12 || 18 || 20 || 4 || 29 || 23 || 1 || 22 || 21 || 27
|-
!  32 || 5
| * || 3 || 1 || 2 || 5 || 7 || 4 || 7 || 6 || 3 || 0 
|-
!  37 || 5
| 11 || 34 || 1 || 28 || 6 || 13 || 5 || 25 || 21 || 15 || 27
|- 
!  41 || 6
| 26 || 15 || 22 || 39 || 3 || 31 || 33 || 9 || 36 || 7 || 28 || 32
|-
! 43 || 28
| 39 || 17 || 5 || 7 || 6 || 40 || 16 || 29 || 20 || 25 || 32 || 35 || 18
|-
!  47 || 10
| 30 || 18 || 17 || 38 || 27 || 3 || 42 || 29 || 39 || 43 || 5 || 24 || 25 || 37
|-
!  49 || 10
| 2 || 13 || 41 || * || 16 || 9 || 31 || 35 || 32 || 24 || 7 || 38 || 27 || 36 || 23
|-
!  53 ||26
| 25 || 9 || 31 || 38 || 46 || 28 || 42 || 41 || 39 || 6 || 45 || 22 || 33 || 30 || 8
|-
!  59 || 10
| 25 || 32 || 34 || 44 || 45 || 28 || 14 || 22 || 27 || 4 || 7 || 41 || 2 || 13 || 53 || 28
|-
!  61 || 10
| 47 || 42 || 14 || 23 || 45 || 20 || 49 || 22 || 39 || 25 || 13 || 33 || 18 || 41 || 40 || 51 || 17
|-
!  64 || 5
| * || 3 || 1 || 10 || 5 || 15 || 12 || 7 || 14 || 11 || 8 || 9 || 14 || 13 || 12 || 5 || 1 || 3
|-
!  67  || 12
| 29 || 9 || 39 || 7 || 61 || 23 || 8 || 26 || 20 || 22 || 43 || 44 || 19 || 63 || 64 || 3 || 54 || 5
|-
!  71 || 62
| 58 || 18 || 14 || 33 || 43 || 27 || 7 || 38 || 5 || 4 || 13 || 30 || 55 || 44 || 17 || 59 || 29 || 37 || 11
|-
!  73 || 5
| 8 || 6 || 1 || 33 || 55 || 59 || 21 || 62 || 46 || 35 || 11 || 64 || 4 || 51 || 31 || 53 || 5 || 58 || 50 || 44
|-
!  79 || 29
| 50 || 71 || 34 || 19 || 70 || 74 || 9 || 10 || 52 || 1 || 76 || 23 || 21 || 47 || 55 || 7 || 17 || 75 || 54 || 33 || 4
|-
!  81 || 11
| 25 || * || 35 || 22 || 1 || 38 || 15 || 12 || 5 || 7 || 14 || 24 || 29 || 10 || 13 || 45 || 53 || 4 || 20 || 33 || 48 || 52
|-
!  83 || 50
| 3 || 52 || 81 || 24 || 72 || 67 || 4 || 59 || 16 || 36 || 32 || 60 || 38 || 49 || 69 || 13 || 20 || 34 || 53 || 17 || 43 || 47
|-
!  89 || 30
| 72 || 87 || 18 || 7 || 4 || 65 || 82 || 53 || 31 || 29 || 57 || 77 || 67 || 59 || 34 || 10 || 45 || 19 || 32 || 26 || 68 || 46 || 27
|-
!  97 || 10
| 86 || 2 || 11 || 53 || 82 || 83 || 19 || 27 || 79 || 47 || 26 || 41 || 71 || 44 || 60 || 14 || 65 || 32 || 51 || 25 || 20 || 42 || 91 || 18
|-
| width="25" | &nbsp;
| width="25" | &nbsp;
! width="25" | 2
! width="25" | 3
! width="25" | 5
! width="25" | 7
! width="25" | 11
! width="25" | 13
! width="25" | 17
! width="25" | 19
! width="25" | 23
! width="25" | 29
! width="25" | 31
! width="25" | 37
! width="25" | 41
! width="25" | 43
! width="25" | 47
! width="25" | 53
! width="25" | 59
! width="25" | 61
! width="25" | 67
! width="25" | 71
! width="25" | 73
! width="25" | 79
! width="25" | 83
! width="25" | 89
|}
 
The sequence of smallest primitive roots (which is not the same as the sequence of primitive roots in the above table) may be found at {{OEIS|id=A046145}}.
 
===Arithmetic facts===
 
Gauss proved<ref>Gauss, DA, art. 80</ref> that for any prime number ''p'' (with the sole exception of ''p'' = 3), the product of its primitive roots is congruent to 1 modulo ''p''.
 
He also proved<ref>Gauss, DA, art. 81</ref> that for any prime number ''p'', the sum of its primitive roots is congruent to μ(''p'' &ndash; 1) modulo ''p'' where μ is the [[Möbius function]].
 
<blockquote>For example
 
:''p'' = 3,  &mu;(2) = &ndash;1. The primitive root is 2.
 
:''p'' = 5,  &mu;(4) = 0. The primitive roots are 2 and 3.
 
:''p'' = 7,  &mu;(6) = 1. The primitive roots are 3 and 5.
 
:''p'' = 31, &mu;(30) = &ndash;1. The primitive roots are 3, 11, 12, 13, 17 &equiv; &ndash;14, 21 &equiv; &ndash;10, 22 &equiv; &ndash;9, and 24 &equiv; &ndash;7.
 
::Their product 970377408 &equiv; 1 (mod 31) and their sum 123 &equiv; &ndash;1 (mod 31).
 
::3×11 = 33 &equiv; 2
::12×13 = 156 &equiv; 1
::(&ndash;14)×(&ndash;10) = 140 &equiv; 16
::(&ndash;9)×(&ndash;7) = 63 &equiv; 1, and 2×1×16×1 = 32 &equiv; 1 (mod 31).
 
</blockquote>
 
==Finding primitive roots==
 
No simple general formula to compute primitive roots modulo ''n'' is known. There are however methods to locate a primitive root that are faster than simply trying out all candidates.
 
If the [[multiplicative order]] of a number ''m'' modulo ''n'' is equal to [[Euler's phi function|<math>\varphi\left(n\right)</math>]] (the order of '''Z'''<sub>''n''</sub><sup>×</sup>), then it is a primitive root. In fact the converse is true: If ''m'' is a primitive root modulo ''n'', then the multiplicative order of ''m'' is [[Euler's phi function|<math>\varphi\left(n\right)</math>]]. We can use this to test for primitive roots.
 
First, compute <math>\varphi\left(n\right)</math>. Then determine the different prime factors of <math>\varphi\left(n\right)</math>, say ''p''<sub>1</sub>, ..., ''p''<sub>''k''</sub>. Now, for every element ''m'' of '''Z'''<sub>''n''</sub><sup>*</sup>, compute
:<math>m^{\varphi(n)/p_i}\mod n \qquad\mbox{  for } i=1,\ldots,k</math>
using a fast algorithm for [[modular exponentiation]] such as [[exponentiation by squaring]]. A number ''m'' for which these ''k'' results are all different from 1 is a primitive root.
 
The number of primitive roots modulo ''n'', if there are any, is equal to<ref>{{OEIS|A010554}} </ref>
:<math>\varphi\left(\varphi\left(n\right)\right)</math>
since, in general, a cyclic group with ''r'' elements has <math>\varphi\left(r\right)</math> generators.
 
If ''g'' is a primitive root modulo ''p'', then ''g'' is a primitive root modulo all powers ''p''<sup>''k''</sup> unless ''g'' <sup>''p'' &ndash; 1</sup> ≡ 1 (mod ''p''<sup>2</sup>); in that case, ''g'' + ''p'' is.<ref>This and the next assertion are in Cohen, p.26</ref>
 
If ''g'' is a primitive root modulo ''p''<sup>''k''</sup>, then ''g'' or ''g'' + ''p''<sup>''k''</sup> (whichever one is odd) is a primitive root modulo 2''p''<sup>''k''</sup>.
 
Finding primitive roots modulo ''p'' is also equivalent to finding the roots of the ''(p-1)''<sup>''th''</sup> [[cyclotomic polynomial]] modulo ''p''.
 
==Order of magnitude of primitive roots==
 
The least primitive root modulo ''p'' is generally small.
 
Let ''g''<sub>''p''</sub> be the smallest primitive root modulo ''p'' in the range 1, 2, ..., ''p''&ndash;1.
 
Fridlander (1949) and Salié (1950) proved<ref name="Ribenboim, p.24">{{Harvnb|Ribenboim|1996|p=24}}</ref> that there is a positive constant ''C''  such that for infinitely many primes ''g''<sub>''p''</sub> > ''C'' log ''p''.
 
It can be proved<ref name="Ribenboim, p.24"/> in an elementary manner that for any positive integer ''M'' there are infinitely many primes such that ''M'' < ''g''<sub>''p''</sub> < ''p'' &ndash; ''M''.
 
Burgess (1962) proved<ref name="Ribenboim, p.24"/> that for every ε > 0 there is a ''C'' such that <math>g_p < Cp^{\frac{1}{4}+\epsilon}.</math>
 
[[Emil Grosswald|Grosswald]] (1981) proved<ref name="Ribenboim, p.24"/> that if <math>p > e^{e^{24}}</math>, then <math>g_p < p^{0.499}</math>.
 
Shoup (1990, 1992) proved,<ref>{{harvnb|Bach|Shallit|1996|p=254}}</ref> assuming the [[generalized Riemann hypothesis]], that ''g''<sub>''p''</sub> =O(log<sup>6</sup> ''p'').
 
== Applications ==
 
Primitive root modulo n is often used in [[cryptography]], including the [[Diffie–Hellman key exchange]] scheme.
 
==See also==
* [[Artin's conjecture on primitive roots]]
* [[Dirichlet character]]
* [[Wilson's theorem#Gauss.27s generalization|Gauss's generalization of Wilson's theorem]]
* [[Multiplicative order]]
* [[Root of unity modulo n]]
 
==Notes==
 
{{reflist}}
 
==References==
 
The ''[[Disquisitiones Arithmeticae]]'' has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
 
*{{citation
  | last1 = Bach  | first1 = Eric
  | last2 = Shallit | first2 = Jeffrey
  | title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
  | publisher = [[The MIT Press]]
  | location = Cambridge
  | year = 1996
  | isbn = 0-262-02405-5}}
*{{citation
  | last1 = Cohen  | first1 = Henri
  | title = A Course in Computational Algebraic Number Theory
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 1993
  | isbn = 3-540-55640-0}}
*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | authorlink1 = Carl Friedrich Gauss
  | last2 = Clarke | first2 = Arthur A. (translator into English) 
  | title = Disquisitiones Arithemeticae (Second, corrected edition)
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1986
  | isbn = 0-387-96254-9}}
*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | authorlink1 = Carl Friedrich Gauss
  | last2 = Maser | first2 = H. (translator into German) 
  | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition)
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 0-8284-0191-8}}
*{{Citation
  |authorlink=Øystein Ore
  |last = Ore
  |first = Oystein
  |title = Number Theory and Its History 
  |publisher = Dover
  |year = 1988
  |pages =  284–302
  |isbn = 0-486-65620-9}}
*{{Citation
  | last1 = Ribenboim  | first1 = Paulo
  | title = The New Book of Prime Number Records
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = New York
  | year = 1996
  | isbn = 0-387-94457-5}}
 
==External links==
*{{MathWorld |title=Primitive Root |id=PrimitiveRoot}}
*This site has a [http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/quadratic4.html primitive root calculator] applet.
*A calculator of all primitive roots modulo p is located [http://www.bluetulip.org/programs/primitive.html here].
 
[[Category:Modular arithmetic]]
 
[[ca:Arrel primitiva]]
[[de:Primitivwurzel]]
[[es:Raíz primitiva módulo n]]
[[fr:Racine primitive modulo n]]
[[it:Generatore (teoria dei numeri)]]
[[he:איבר פרימיטיבי]]
[[hu:Primitív gyök]]
[[ja:指数 (初等整数論)]]
[[pl:Pierwiastek pierwotny]]
[[pms:Rèis primitiva]]
[[ru:Первообразный корень (теория чисел)]]
[[ta:ஏது மூலம், மாடுலோ p]]
[[vi:Căn nguyên thủy modulo n]]
[[zh:原根]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"