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 >
t, such that
as ≡
at (mod
n). Since
a and
n are
coprime,
a has an inverse element
a−1 and we can multiply both sides of the congruence with
a−
t, yielding . The concept of multiplicative order is a special case of the
order of group elements. The multiplicative order of a number
a modulo
n is the order of
a in the
multiplicative group whose elements are the residues modulo
n of the numbers coprime to
n, and whose group operation is multiplication modulo
n. This is the
group of units of the
ring Zn; it has
φ(
n) elements,
φ being
Euler's totient function, and is denoted as
U(
n) or
U(
Zn). As a consequence of
Lagrange's theorem, the order of always
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. This means that the group
U(
n) is
cyclic and the residue class of
a 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
φ(
n). == Programming languages ==