In [number theory], the [multiplicative] [order] i of an [integer] a [modulo] a [positive] integer n (denoted i=ord_n(a)) is the smallest positive integer such that aⁱ[is congruent to|=]1(mod n).

Examples

a=2, n=3. 2²=4[=]1(mod 3), so ord₃(2)=2.

a=10, n=7. 10[=]3(mod 7), so ord₇(10)=ord₇(3). 3³=27[=]-1(mod 7), and (-1)²=1, so 3⁶[=]1(mod 7) and ord₇(10)=ord₇(3)=6. Notice that this means that 7|999999. (10⁶-1 = 999999 = 3³*7*11*13*37.)

Conditions

An integer a has a multiplicative order mod a positive integer n iff [gcd](a,n)=1. This is equivalent to saying that ord_n(a) exists [iff] a has a [multiplicative inverse] mod n. n is [prime] [if and only if|iff] for every 0<a<n, a^n-1[=]1(mod n) (see [Fermat's little theorem]).

Proof

To prove: ord_n(a) exists iff gcd(a,n)=1.
Let gcd(a,n)=1. From the [pigeonhole principle], there exists an integer p such that aⁱ[=]a^i+p(mod n) for all i sufficiently large. From the definition of congruence, this means that n|aⁱ*(1-a^p). gcd(a,n)=1, so gcd(aⁱ,n)=1, which means that n|(1-a^p), or a^p[=]1(mod n). Thus ord_n(a) exists if gcd(a,n)=1 (though it is not necessarily p).
Let i=ord_n(a) exist. Then aⁱ[=]1(mod n), which is to say that there exists an integer k such that aⁱ-k*n=1. Let d=gcd(a,n). Then d|aⁱ and d|k*n, so d|1. The only numbers which divide 1 are 1 and -1, therefore if ord_n(a) exists, then gcd(a,n)=1.

multiplicative order (idea)