The multiplicative order of an integer 
modulo an integer 
relatively prime
to 
is the smallest positive integer exponent 
for which 
. It is also called the haupt-exponent or modulo
order.
If 
has a primitive root 
, then 1, 
, 
, ..., 
form a reduced
residue system modulo 
, where 
is the totient function.
In this system, there are 
primitive roots,
namely the residues 
for exponents 
relatively prime to 
.
The multiplicative order is implemented in the Wolfram Language as MultiplicativeOrder[g, n].
When 
has a primitive root and 
is a positive divisor of 
, the number of distinct residue
classes modulo 
having multiplicative order 
is 
. This count need not hold for other moduli. Cunningham
(1922) published the multiplicative order for primes
to 25409 and bases 2, 3, 5, 6, 7, 10, 11, and 12.
For example, the multiplicative order of 10 (mod 7) is 6, since
 |
(1)
|
The multiplicative order of 10 mod an integer 
relatively prime
to 10 gives the period of the decimal expansion
of the reciprocal of 
(Glaisher 1878, Lehmer 1941). For example, the haupt-exponent
of 10 (mod 13) is 6, and
 |
(2)
|
which has period 6.
The following table gives the first few multiplicative orders for bases 
(mod 
), where the moduli 
run in increasing order through the integers relatively prime to 
.
 | OEIS | haupt-exponents |
| 2 | A002326 | 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, ... |
| 3 | A050975 | 1, 2, 4, 6, 2, 4, 5, 3, 6, 4, 16, 18, 4, 5, ... |
| 4 | A050976 | 1, 2, 3, 3, 5, 6, 2, 4, 9, 3, 11, 10, 9, 14, ... |
| 5 | A050977 | 1, 2, 1, 2, 6, 2, 6, 5, 2, 4, 6, 4, 16, 6, 9, ... |
| 6 | A050978 | 1, 2, 10, 12, 16, 9, 11, 5, 14, ... |
| 7 | A050979 | 1, 1, 2, 4, 1, 2, 3, 4, 10, 2, 12, 4, 2, 16, ... |
| 8 | A050980 | 2, 4, 1, 2, 10, 4, 4, 8, 6, 2, 11, 20, 6, 28, ... |
| 9 | A050981 | 1, 1, 2, 3, 1, 2, 5, 3, 3, 2, 8, 9, 2, 5, 11, ... |
| 10 | A002329 | 1, 6, 1, 2, 6, 16, 18, 6, 22, 3, 28, ... |
If 
is a primitive root modulo 
and 
is an arbitrary integer relatively
prime to 
,
then there exists among the numbers 0, 1, 2, ..., 
exactly one number 
such that
 |
(3)
|
The number 
is the discrete logarithm of 
to base 
modulo 
(Schneier 1996, p. 501). Note that Nagell (1951, p. 112)
instead uses the term "index" and writes
 |
(4)
|
For example, the number 7 is a primitive root of 
,
and since 
,
the discrete logarithm of 15 to base 7 is 3
(modulo 41) (Nagell 1951, p. 112).
The generalized multiplicative order used in the Wolfram Language is the smallest positive integer
exponent 
for which 
is congruent modulo 
to one of a specified set of target
residues. It is implemented as MultiplicativeOrder[g,
n, 
a1,
a2, ...
].
For a primitive root 
and a single target 
, this gives the discrete
logarithm except for the residue 1, whose discrete
logarithm is 0 and whose least positive exponent is 
.
With target residues 
and 1, the generalized multiplicative order is the suborder
function, denoted 
for base 
. With the single target residue
1, it is the ordinary multiplicative order 
, implemented as MultiplicativeOrder[a,
n].
."
§8.1 in 
" and "The Index Calculus." §31 and 33
in