In number theory, the multiplicative order i of an integer a modulo a positive integer n (denoted i=ordn(a)) is the smallest positive integer such that ai=1(mod n).
Examples
- a=2, n=3. 22=4=1(mod 3), so ord3(2)=2.
- a=10, n=7. 10=3(mod 7), so ord7(10)=ord7(3). 33=27=-1(mod 7), and (-1)2=1, so 36=1(mod 7) and ord7(10)=ord7(3)=6. Notice that this means that 7|999999. (106-1 = 999999 = 33*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 ordn(a) exists iff a has a multiplicative inverse mod n. n is prime iff for every 0<a<n, an-1=1(mod n) (see Fermat's little theorem).
Proof
To prove: ordn(a) exists iff gcd(a,n)=1.
Let gcd(a,n)=1. From the pigeonhole principle, there exists an integer p such that ai=ai+p(mod n) for all i sufficiently large. From the definition of congruence, this means that n|ai*(1-ap). gcd(a,n)=1, so gcd(ai,n)=1, which means that n|(1-ap), or ap=1(mod n). Thus ordn(a) exists if gcd(a,n)=1 (though it is not necessarily p).
Let i=ordn(a) exist. Then ai=1(mod n), which is to say that there exists an integer k such that ai-k*n=1. Let d=gcd(a,n). Then d|ai and d|k*n, so d|1. The only numbers which divide 1 are 1 and -1, therefore if ordn(a) exists, then gcd(a,n)=1.