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

a^k = 1 in Z_n.

The order of a modulo n is usually written ord_n a, or, O_n(a).

This is a special case of order in a group: if (G, *) is a group written with the usual multiplicative notation (so that a^t represents the t-fold product under *), it is the least integer k such that a^k=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).