The Order of a Natural Number Modulo m

# The Order of a Natural Number Modulo m

Recall from the Euler's Totient Theorem page that if $a, m \in \mathbb{N}$, $(a, m) = 1$, and $\phi (m)$ denotes the number of positive integers less than or equal to $m$ that are relatively prime to $m$ then:

(1)
\begin{align} \quad a^{\phi(m)} \equiv 1 \pmod m \end{align}

It is very possible that there exists smaller positive power for which $a$ raised to that power is congruent to $1$ modulo $m$. Such power is important and we define it below.

 Definition: Let $a, m \in \mathbb{N}$. The Order of $a$ modulo $m$ is the smallest positive integer $t$ such that $a^t \equiv 1 \pmod m$.

Note that if $(a, m) = 1$ then the order of $a$ modulo $m$ is always defined and $1 \leq t \leq \phi (m)$.

For example, consider the following table of values for which the horizontal column lists $a = 1, 2, ..., 12$, the entries give $a, a^2, ..., a^{12}$ modulo $13$:

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

As we can see, the order of $1$ and $12$ is $1$. The order of $2$ is $6$, $7$, and $11$ is $\phi(m) = 12$. The order of $3$ and $9$ is $3$. The order of $5$ and $8$ is $4$. The order of $4$ and $10$ is $6$.

Do you notice anything peculiar? The possible orders of $a$ modulo $m$ are $1, 2, 3, 4, 6, 12$ - which are all of the divisors of $\phi(13) = 12$!

We will now look at some results regarding the order of an integer modulo $m$.

 Theorem 1: Let $a, m \in \mathbb{N}$ and let $(a, m) = 1$. If $t$ is the order of $a$ modulo $m$ then $a^n \equiv 1 \pmod m$ if and only if $n$ is a multiple of $t$.
• Proof: $\Rightarrow$ Suppose that $a^n \equiv 1 \pmod m$. If $t$ is the order of $a$ modulo $m$ then we must have that $n \geq t$. Assume that $n$ is not a multiple of $t$. Then $n = s + kt$ by the division algorithm where $k \in \mathbb{N}$ and $0 \leq s < t$. Then:
(2)
\begin{align} \quad a^{n} \equiv a^{s + kt} \equiv a^s(a^{kt}) \equiv a^s \equiv 1 \pmod m \end{align}
• But then $a^s \equiv 1 \pmod m$ and $s < t$ which contradicts $t$ being the order of $a$ modulo $m$, so, the assumption that $n$ is not a multiple of $t$ is false. Thus $n$ must be a multiple of $t$.
• $\Leftarrow$ Suppose that $n$ is a multiple of $t$. Then $n = kt$ for some $k \in \mathbb{N}$ and thus:
(3)
\begin{align} \quad a^n \equiv a^{kt} \equiv (a^t)^k \equiv 1^k \equiv 1 \pmod m \end{align}
• So $a^n \equiv 1 \pmod m$. $\blacksquare$
 Theorem 2: Let $a, m \in \mathbb{N}$ and let $(a, m) = 1$. If $t$ is the order of $a$ modulo $m$ then $t \mid \phi (m)$.
• Proof: Since $(a, m) = 1$, Euler's totient theorem gives us that:
(4)
\begin{align} \quad a^{\phi(m)} \equiv 1 \pmod m \end{align}
• So by Theorem 1 we must have that $\phi (m)$ is a multiple of the order of $a$, i.e., $kt = \phi(m)$. So $t \mid \phi (m)$. $\blacksquare$
 Theorem 3: Let $a, m \in \mathbb{N}$ and let $(a, m) = 1$. If $t$ is the order of $a$ modulo $m$ then $a^r \equiv a^s \pmod m$ if and only if $r \equiv s \pmod t$.
• Proof: $\Rightarrow$ Suppose that $a^r \equiv a^s \pmod m$ and assume without loss of generality that $r > s$. Then $r - s > 0$ and since $(a, m) = 1$ we have that $(a^s, m) = 1$, so:
(5)
\begin{align} \quad a^r & \equiv a^s \pmod m \\ \quad a^{r-s} & \equiv 1 \pmod m \end{align}
• By Theorem 1 we must have that $r-s = kt$. In other words, $t \mid (r - s)$, so $r \equiv s \pmod t$.
• $\Leftarrow$ Suppose that $r \equiv s \pmod t$. Then $t \mid (r - s)$ so there exists a $k \in \mathbb{N}$ such that $kt = r - s$. So $r - s$ is a multiple of $t$ which gives us that:
(6)
\begin{align} \quad a^{r-s} & \equiv 1 \pmod m \\ \quad a^r & \equiv a^s \pmod m \quad \blacksquare \end{align}
 Theorem 4: Let $a, m \in \mathbb{N}$ and let $(a, m) = 1$. If $a$ has order $t$ modulo $m$ then $a^k$ has order $\frac{t}{(t, k)}$.