Editing Multiplicative order (section)

== Properties ==

Even without knowledge that we are working in the [[multiplicative group of integers modulo n]], we can show that ''a'' actually has an order by noting that the powers of ''a'' can only take a finite number of different values modulo ''n'', so according to the [[pigeonhole principle]] there must be two powers, say ''s'' and ''t'' and [[without loss of generality]] ''s''&nbsp;>&nbsp;''t'', such that ''a''<sup>''s''</sup>&nbsp;≡&nbsp;''a''<sup>''t''</sup>&nbsp;(mod&nbsp;''n''). Since ''a'' and ''n'' are [[coprime]], ''a'' has an inverse element ''a''<sup>−1</sup> and we can multiply both sides of the congruence with ''a''<sup>−''t''</sup>, yielding ''a''<sup>''s''−''t''</sup>&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;''n'').

The concept of multiplicative order is a special case of the [[Order (group theory)|order of group elements]]. The multiplicative order of a number ''a'' modulo ''n'' is the order of ''a'' in the [[multiplicative group of integers modulo n|multiplicative group]] whose elements are the residues modulo ''n'' of the numbers coprime to ''n'', and whose group operation is multiplication modulo&nbsp;''n''. This is the [[group of units]] of the [[ring (mathematics)|ring]] '''Z'''<sub>''n''</sub>; it has ''φ''(''n'') elements, φ being [[Euler's totient function]], and is denoted as ''U''(''n'') or&nbsp;''U''('''Z'''<sub>''n''</sub>).

As a consequence of [[Lagrange's theorem (group theory)|Lagrange's theorem]], the order of ''a'' (mod ''n'') always [[divisor|divides]] ''φ''(''n''). If the order of ''a'' is actually equal to ''φ''(''n''), and therefore as large as possible, then ''a'' is called a [[primitive root modulo n|primitive root]] modulo ''n''. This means that the group ''U''(''n'') is [[Cyclic group|cyclic]] and the residue class of ''a'' [[Cyclic_group#Definition_and_notation|generates]] it.

The order of ''a'' (mod ''n'') also divides λ(''n''), a value of the [[Carmichael function]], which is an even stronger statement than the divisibility of&nbsp;''φ''(''n'').