Main Page | See live article | Alphabetical index

Multiplicative order

In number theory, the multiplicative order of a number a modulo n, when gcd(a,n) = 1, is the smallest integer k with
ak = 1 in Zn.
The order of a modulo n is usually written ordn a, or, On(a).

This is a special case of order in a group: if (G, *) is a group written with the usual multiplicative notation (so that at represents the t-fold product under *), it is the least integer k such that ak=e in G.

The primitive rootss modulo n, when they exist, are the residues modulo n of largest possible order. They exist exactly when there is an element of order φ(n), φ being Euler's totient function. This is the condition that the group G be cyclic.

When n is a prime number p, that is always the case. The condition is that the order of some a mod p for some prime p is p-1; there always are such a, and their number is in fact known, being φ(p-1).

See also: Modular arithmetic, Glossary of group theory\n