The Order of a (mod m)

# 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)
\begin{align} a^j \equiv a^k \pmod m \end{align}

Since $(a, m) = 1$, it thus follows that we can divide both sides by a^k to obtain:

(2)
\begin{align} a^{j - k} \equiv 1 \pmod m \end{align}

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)
\begin{align} a^{t + k\phi (m)} \equiv a^t (a^{k})^{\phi (m)} \equiv a^t (1) \equiv 1 \pmod m \end{align}

Let's create a table for $a^n \mod {13}$. We will let a = 1, a = 2, …, a = 12, and calculate a (mod m), a2 (mod m), …, a^12 (mod m).

a a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12
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 an ≡ 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 | ap - 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 | ap - 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 | ap - 1. In fact, this is true. 3 | 45 - 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 ar ≡ as (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^{r-s} \equiv 1 \pmod m$. We know that t is the order of a (mod m). By theorem 1, r-s must be a multiple of t, that is t | r - s. Hence $r \equiv s \pmod t$.