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)}$.