Table of Contents

The Order of a (mod m)
Recall that by Euler's theorem that if $(a, m) = 1$, then $a^{\phi (m)} \equiv 1 \pmod {m}$. However, we will now be interested in the congruence $a^t \equiv 1 \pmod {m}$ for $1 ≤ t ≤ \phi (m)$. The smallest such positive t that satisfies this congruence is called the order of a (mod m) or alternatively the exponent to which a belongs (mod m).
Notice that if $(a, m) = 1$, then the least residues of the integers $a, a^2, a^3, ...$ (mod m) are all relatively prime to m. We know that there are $\phi (m)$ least residues that are relatively prime to m, but there are infinitely many powers of a. Hence it follows that for some j ≠ k and j > k then:
(1)Since $(a, m) = 1$, it thus follows that we can divide both sides by a^k to obtain:
(2)In fact there are infinitely many powers of a that satisfy this congruence. For example since $a^{t + k\phi (m)} = a^t (a^k)^{\phi m}$, then for any positive integer k:
(3)Let's create a table for $a^n \mod {13}$. We will let a = 1, a = 2, …, a = 12, and calculate a (mod m), a^{2} (mod m), …, a^12 (mod m).
a  a^{2}  a^{3}  a^{4}  a^{5}  a^{6}  a^{7}  a^{8}  a^{9}  a^{10}  a^{11}  a^{12} 

1  1  1  1  1  1  1  1  1  1  1  1 
2  4  8  3  6  12  11  9  5  10  7  1 
3  9  1  3  9  1  3  9  1  3  9  1 
4  3  12  9  10  1  4  3  12  9  10  1 
5  12  8  1  5  12  8  1  5  12  8  1 
6  10  8  9  2  12  7  3  5  4  11  1 
7  10  5  9  11  12  6  3  8  4  2  1 
8  12  5  1  8  12  5  1  8  12  5  1 
9  3  1  9  3  1  9  3  1  9  3  1 
10  9  12  3  4  1  10  9  12  3  4  1 
11  4  5  3  7  12  2  9  8  10  6  1 
12  1  12  1  12  1  12  1  12  1  12  1 
a  Order of a (mod 13) 

1  1 
12  2 
3, 9  3 
5, 8  4 
4, 10  6 
2, 6, 7, 11  12 
Notice that the only possible orders for a are 1, 2, 3, 4, 6, and 12. Interestingly enough, these are all divisors of 12. So how is 12 related to 13? Well we know that 13 is a prime, so $\phi (13) = 12$.
Theorem 1: If (a, m) = 1 and a has order t (mod m), then a^{n} ≡ 1 (mod m) if and only if n is a multiple of t.
 Proof: Suppose that $n = tq$, that is, n is a multiple of t. It thus follows that $a^n \equiv a^{tq} \equiv (a^t)^q \equiv (1)^q \equiv 1 \pmod m$. Hence if $a^n \equiv 1 \pmod m$, then n must be a multiple of t.
 Proof (Converse): Suppose that $a^n \equiv 1 \pmod m$. Since t is the order of a (mod m), n ≥ t. Hence we can rewrite n as $n = qt + r$ by the division algorithm. We thus obtain that: $a^n \equiv a^{qt + r} \equiv (a^t)^qa^r \equiv (1)^q a^r \equiv a^r \pmod m$. But r = 0 since 0 ≤ r < t since the order of a (mod m) is t. Hence n = qt.
Theorem 2: If (a, m) = 1 and a has order t (mod m), then t  Φ(m).
 Proof: We know that from theorem 1 that $\phi (m)$ must be a multiple of t since by Euler's theorem $a^{\phi (m)} \equiv 1 \pmod m$. Hence t  Φ(m).
We can verify from the original example that all of the orders of a (mod 13) were 1, 2, 3, 4, 6, and 12. All of these divide $\phi (13) = 12$. 1  12, 2  12, 3  12, 4  12, 6  12, and 12  12.
Theorem 3: If p and q are both odd primes, and q  a^{p}  1, then either q  a  1 or q = 2kp + 1.
 Proof: By the definition of a congruence, we know that $a^p \equiv 1 \pmod q$ since q  a^{p}  1. The order of a (mod q) must be a divisor of p by theorem 1, but there are only two divisors of p, namely 1 and p. Suppose that the order of a (mod q) is 1. Hence $a^1 \equiv 1 \pmod q$, so then q  a  1. Suppose that the order of a (mod q) is p. By theorem 2, p must divided $\phi (q) = q  1$. Hence p  q  1, or rather $np = q  1$ or $q = np + 1$. The lefthand side of this equation is odd, hence, the righthand side of this equation must also be odd. Since p is an odd prime and 1 is odd, then n must be even. Hence n = 2k for k ≥ 1. Hence $q = 2kp + 1$.
Example 1
Verify theorem 3 with q = 3 and a = 4, and p = 5.
We must first verify that q  a^{p}  1. In fact, this is true. 3  4^{5}  1, or rather 3  1023. So either 3  4  1 or 3 = 2k(5) + 1. Clearly 3  3, so this is true, and 3 = 10k + 1 does not work since $k \in \mathbb{Z}$ and 10k + 1 > 3.
Theorem 4: If t is the order of a (mod m), then a^{r} ≡ a^{s} (mod m) if and only if r ≡ s (mod t).
 Proof: Suppose that r ≥ s. Hence with the congruence $a^r \equiv a^s \pmod m$, then $a^{rs} \equiv 1 \pmod m$. We know that t is the order of a (mod m). By theorem 1, rs must be a multiple of t, that is t  r  s. Hence $r \equiv s \pmod t$.