Editing Primitive root modulo n (section)

{{Short description|Modular arithmetic concept}}
{{DISPLAYTITLE:Primitive root modulo {{mvar|n}}}}
In [[modular arithmetic]], a number {{mvar|g}} is a '''primitive root modulo&nbsp;{{mvar|n}}''' if every number {{mvar|a}} [[coprime]] to {{mvar|n}} is [[Congruence relation|congruent]] to a power of {{mvar|g}} modulo {{mvar|n}}. That is, {{mvar|g}} is a ''primitive root modulo''&nbsp;{{mvar|n}} if for every integer {{mvar|a}} coprime to {{mvar|n}}, there is some integer {{mvar|k}} for which {{mvar|g}}<sup>{{mvar|k}}</sup> ≡ {{mvar|a}} (mod&nbsp;{{mvar|n}}). Such a value {{mvar|k}} is called the '''index''' or '''[[discrete logarithm]]''' of {{mvar|a}} to the base {{mvar|g}} modulo {{mvar|n}}. So {{mvar|g}} is a ''primitive root modulo''&nbsp;{{mvar|n}} if and only if {{mvar|g}} is a [[Generating_set_of_a_group|generator]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|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 [[Johann Heinrich Lambert|Lambert]] and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a [[Prime number|prime]] {{mvar|n}}. In fact, the ''Disquisitiones'' contains two proofs: The one in Article 54 is a nonconstructive [[Existence theorem|existence proof]], while the proof in Article 55 is [[Constructive proof|constructive]].

A primitive root exists if and only if ''n'' is 1, 2, 4, ''p''<sup>''k''</sup> or 2''p''<sup>''k''</sup>, where ''p'' is an odd prime and {{nowrap|''k'' > 0}}. For all other values of ''n'' the multiplicative group of integers modulo ''n'' is not [[cyclic group|cyclic]].<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0">{{Cite web |title=Primitive root - Encyclopedia of Mathematics |url=https://encyclopediaofmath.org:443/wiki/Primitive_root |access-date=2024-11-05 |website=encyclopediaofmath.org}}</ref><ref name="Vinogradov2003.pp=105-121">{{Harv|Vinogradov|2003|loc=§ VI PRIMITIVE ROOTS AND INDICES|pp=105–121}}</ref>
This was first proved by [[Carl Friedrich Gauss|Gauss]].<ref>{{Harv|Gauss|1986|loc=arts. 52–56, 82–891}}</ref>