Editing Primitive root modulo n (section)

==Definition==
If {{mvar|n}} is a positive integer, the integers from 1 to {{nowrap|{{mvar|n}} − 1}} that are [[coprime]] to {{mvar|n}} (or equivalently, the [[congruence class]]es coprime to {{mvar|n}}) form a [[group (mathematics)|group]], with multiplication [[Modular arithmetic|modulo]] {{mvar|n}} as the operation; it is denoted by [[multiplicative group of integers modulo n|<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}]], and is called the [[group of units]] modulo {{mvar|n}}, or the group of primitive classes modulo {{mvar|n}}. As explained in the article [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar|n}}]], this multiplicative group (<math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}) is [[cyclic group|cyclic]] '''if and only if''' {{mvar|n}} is equal to 2, 4, {{mvar|p{{sup|k}}}}, or 2{{mvar|p{{sup|k}}}} where {{mvar|p{{sup|k}}}} is a power of an odd [[prime number]].<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0" /><ref name="Vinogradov2003.pp=105–121">{{Harvnb|Vinogradov|2003|loc=§ VI Primitive roots and indices|pp=105–121}}.</ref> When (and only when) this group <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is cyclic, a [[generating set of a group|generator]] of this cyclic group is called a '''primitive root modulo {{mvar|n}}'''<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (or in fuller language '''primitive root of unity modulo {{mvar|n}}''', emphasizing its role as a fundamental solution of the '''[[Root of unity modulo n|roots of unity]]''' polynomial equations X{{su|p={{mvar|m}}}} − 1 in the ring <math>\mathbb{Z}</math>{{sub|{{mvar|n}}}}), or simply a '''primitive element of''' <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}}.

When <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is non-cyclic, such primitive elements mod {{mvar|n}} do not exist. Instead, each prime component of {{mvar|n}} has its own sub-primitive roots (see {{math|15}} in the examples below).

For any {{mvar|n}} (whether or not <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is cyclic), the order of <math>\mathbb{Z}</math>{{su|b={{mvar|n}}|p=×}} is given by [[Euler's totient function]] {{mvar|φ}}({{mvar|n}}) {{OEIS|id=A000010}}. And then, [[Euler's theorem]] says that {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> ≡ 1 (mod {{mvar|n}})}} for every {{mvar|a}} coprime to {{mvar|n}}; the lowest power of {{mvar|a}} that is congruent to 1 modulo {{mvar|n}} is called the [[multiplicative order]] of {{mvar|a}} modulo {{mvar|n}}. In particular, for {{mvar|a}} to be a primitive root modulo {{mvar|n}}, {{nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> }} has to be the smallest power of {{mvar|a}} that is congruent to 1 modulo {{mvar|n}}.