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**^{i}=1(mod n).

### Examples

- a=2, n=3. 2
^{2}=4=1(mod 3), so ord_{3}(2)=2.
- a=10, n=7. 10=3(mod 7), so ord
_{7}(10)=ord_{7}(3). 3^{3}=27=-1(mod 7), and (-1)^{2}=1, so 3^{6}=1(mod 7) and ord_{7}(10)=ord_{7}(3)=6. Notice that this means that 7|999999. (10^{6}-1 = 999999 = 3^{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 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^{i}=a^{i+p}(mod n) for all i sufficiently large. From the definition of congruence, this means that n|a^{i}*(1-a^{p}). gcd(a,n)=1, so gcd(a^{i},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^{i}=1(mod n), which is to say that there exists an integer k such that a^{i}-k*n=1. Let d=gcd(a,n). Then d|a^{i} 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.