Does $a^m \equiv 1\ (\text{ mod } n)$ solution exist for every integer where $(a,n)=1$?

Question

For example, given the following modular equation: $$7^m \equiv 1\ (\text{ mod } 13); \quad (7,13)=1$$ By hard working, we can find the solution: $$7^{12} \equiv 1\ (\text{ mod } 13)$$

From my observation, the solution seems to exist for all $a,n \text{ where } (a,n)=1$.
But, I can't come up with any proof. So the question is,

Given integer $a, m, n$, where $(a,n)=1$, Is the following statement always solvable?

$$a^m \equiv 1\ (\text{ mod } n)$$

And if always true or for the true cases, given $a\text{ and }n$ what would be the practical way to find the solution? (Something better than brute-forcing all the values)

Thanks in advance,

Answer 1

Yes. That is Euler's theorem:

For any $a$ coprime with $n$, one has $$a^{\varphi (n)}\equiv 1\mod n,$$ where $\varphi$ is the totient function.

So the least $m$ such that $a^m\equiv 1\mod n$ (the order of $a$ modulo $n$) is a divisor of $\varphi(n)$.

Note: the value of the totient function is easy to calculate: if $n=p_1^{r_1}\dotsm p_k^{r_k}$ is the decomposition of $n$ as a product of distinct primes, then $$\varphi(n)=p_1^{r_1-1}(p_1-1)\dotsm p_k^{r_k-1}(p_k-1).$$

Answer 2

Such an $m$ always exists, and the least such $m$ always divides $\varphi(n)$, where $\varphi$ denotes Euler's totient function.

A nice way to prove this is by showing that the units of the ring $\Bbb{Z}/n\Bbb{Z}$ are precisely the classes of numbers coprime to $n$.

Answer 3

Since $a$ is relatively prime with $n$, it has an inverse modulo$~n$, a solution $s$ to $as\equiv 1\pmod n$. (If $s,t$ are Bézout coefficients such that $1=as+nt$, then $s$ is such an inverse.) This means that multiplication by $a$, as operation on the set of $n$ congruence classes modulo$~n$, has an inverse (multiplication by $s$), so it is a bijection. Then the sequence of classes modulo$~n$ of $1=a^0,a=a^1,a^2,a^3,\ldots$, which must ultimately encounter a class that is already present earlier in the sequence (as the stock of fresh classes is finite), must do this for the first time by hitting the class of $a^0$ (otherwise the class of first collision has two distinct predecessor classes, contradicting bijectivity). That is $a^m\equiv1\pmod n$ has a solution $m>0$.