# Suppose that $gcd(a,n)= 1$. Prove that $a^m \equiv 1 \pmod n$ iff $ord(a,n) \mid m$

Here is my attempt.

Suppose we have $a^m \equiv 1 \pmod n$ and assume that $ord(a,n) = k$ (order of $a)$ and so since $k = ord(a,n)$ it follows that $k \leq m$ .
Now if $k = m$ then we are done but now assume that $k < m$ and it also follows that $a^k \equiv 1 \pmod n$. Hence we do have that $a^m \equiv a^k \pmod n$ which means that $n \mid a^m - a^k$ and so $n | a(a^{m-1} - a^{k-1})$, however since $gcd(a,n) = 1$ then we know that $n \mid a^{m-1} - a^{k-1}$ and eventually since we have $k < m$ we can keep doing that until we have $n \mid a^{m-k} - 1$.

but how do I conclude form here that $k \mid m$ or is there another simpler method ?

For the converse statement (other implication , it's trivial)

Suppose that $ord(a,n) \mid m$

so again let $k = ord(a,n)$ then there exists an integer $t$ such that $kt = m$

then since $a^k\equiv 1 \pmod n$ then $a^{kt} \equiv 1 ^{t} \pmod n$ and so $a^m \equiv 1 \pmod n$ . So I am just stuck in the first implication

## 2 Answers

If $k<m$ apply Euclidean division to write $m=qk+r$. Then $a^m\equiv a^r\equiv1$, but $r<k$, and this implies $r=0$.

The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:a^n \equiv 1\:$ is closed under positive subtraction, i.e.

$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$

Thus, by theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \!$ := order of $\rm\,a.$

Theorem $\ \$ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\ n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$

Proof $\$ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \,$

See here for elaboration on the Theorem, and for more on the key innate structure see this post on order ideals and denominator ideals.