**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 a^{k} ≡ 1 (mod n).

**Theorem**: Let the integer a have order k modulo n. Then a^{b} ≡ 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 a^{k} ≡ 1 (mod n), this implies that (a^{k})^{j} ≡ 1^{j} (mod n) or a^{b} ≡ 1 (mod n).

Conversely, let b be any positive integer satisfying a^{b} ≡ 1 (mod n). By division algorithm, there exist q and r such that b = qk + r, where 0 ≤ r < k. Consequently,

a^{b} = a^{qk + r }= (a^{k})^{r} a^{r}

By hypothesis, both a^{b} ≡ 1 (mod n) and a^{k} ≡ 1 (mod n), the implication of which is that a^{r} ≡ 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 a^{k} ≡ 1 (mod n) is contradicted. Hence, h = qk, and k | b.

**Theorem**: If the integer a has order k modulo n, then a^{i} ≡ a^{j} (mod n) if and only if i ≡ j (mod n).

**Proof**: First, suppose that a^{i} ≡ a^{j} (mod n), where i ≥ j. Because a is relatively prime to n, we may cancel a power of a to obtain a^{i – 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, a^{k} ≡ 1 (mod n), so that

a^{i} ≡ a^{j + qk }≡ a^{j} (a^{k})^{q} ≡ a^{j} (mod n).

**Theorem**: If the integer a has order k modulo n and b > 0, then a^{b} has order

k /gcd(b, k).

**Proof**: Let d = gcd(b, k). Then we may write b = b_{1}d and k = k_{1}d with gcd (b_{1}, k_{1})=1. Clearly, (a^{b})^{k}_{1}= (a^{b}_{1}^{k})^{k / d} = (a^{k})^{b}_{1} ≡ 1 (mod n)

If a^{b} is assume to have order r modulo n, then r | k_{1}. On the other hand, since a has order k modulo n, the congruence a^{hr} ≡ (a^{h})^{r} ≡ 1 (mod n)

Indicates that k | br; in words k_{1}d | h_{1}dr or k_{1} |b_{1}r. But gcd(k_{1}, b_{1}) = 1, and therefore k_{1} | r. This divisibility relation, when combined with the one obtained earlier gives

r = k_{1} = k /d = k/gcd(h, k). (proved).