Definition of the order of an integer modulo n: Let n > 1 and gcd(a, n) = 1. The order of a modulo n is the smallest positive integer k such that ak ≡ 1 (mod n).
Theorem: Let the integer a have order k modulo n. Then ab ≡ 1 (mod n) if and only if k|b; in particular, k|?(n)
Proof: Suppose to be begin with k | b, so that h = jk for some integer j. Because ak ≡ 1 (mod n), this implies that (ak)j ≡ 1j (mod n) or ab ≡ 1 (mod n).
Conversely, let b be any positive integer satisfying ab ≡ 1 (mod n). By division algorithm, there exist q and r such that b = qk + r, where 0 ≤ r < k. Consequently,
ab = aqk + r = (ak)r ar
By hypothesis, both ab ≡ 1 (mod n) and ak ≡ 1 (mod n), the implication of which is that ar ≡ 1 (mod n). Because 0 ≤ r < k, we end up with r = 0; otherwise, the choice of k as the smallest positive integer such that ak ≡ 1 (mod n) is contradicted. Hence, h = qk, and k | b.
Theorem: If the integer a has order k modulo n, then ai ≡ aj (mod n) if and only if i ≡ j (mod n).
Proof: First, suppose that ai ≡ aj (mod n), where i ≥ j. Because a is relatively prime to n, we may cancel a power of a to obtain ai – j ≡ 1 (mod n). According to previous theorem, this last congruence holds only if k | i – j , which just another way of saying that i ≡ j (mod k).
Conversely, let i ≡ j(mod k). Then we have i = j + qk for some integer q. By the condition k, ak ≡ 1 (mod n), so that
ai ≡ aj + qk ≡ aj (ak)q ≡ aj (mod n).
Theorem: If the integer a has order k modulo n and b > 0, then ab has order
k /gcd(b, k).
Proof: Let d = gcd(b, k). Then we may write b = b1d and k = k1d with gcd (b1, k1)=1. Clearly, (ab)k1= (ab1k)k / d = (ak)b1 ≡ 1 (mod n)
If ab is assume to have order r modulo n, then r | k1. On the other hand, since a has order k modulo n, the congruence ahr ≡ (ah)r ≡ 1 (mod n)
Indicates that k | br; in words k1d | h1dr or k1 |b1r. But gcd(k1, b1) = 1, and therefore k1 | r. This divisibility relation, when combined with the one obtained earlier gives
r = k1 = k /d = k/gcd(h, k). (proved).