# 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)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 | 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 |

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:

- 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:

- 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:

- 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:

- 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: