Multiplicative order when gcd=1

Question

If $a^{n}\equiv 1 \pmod m$, then $aa^{n-1}\equiv 1 \pmod m$, so $a^{n-1}$ is the multiplicative inverse of $a$ modulo $m$ and $\gcd(a,m)=1$.

What I don't understand is why $\gcd(a,m)=1$ and $a^{n}\equiv 1 \pmod m$ imply that exists an $n$ such as $n<m$ ?

Thanks

Answer 1

Consider all different positive powers of $a$ modulo $m$. In other words, the sequence $$ a, a^2, a^3,\ldots\pmod m $$ It will necessarily be a repeating sequence, and as there are at most $m-1$ possible values a term could take, we must be back at $a$ again at the latest with $a^m$. The one before that (at latest $a^{m-1}$) must be $1$.

Answer 2

As $gcd(a,m) = 1$, there is some $N$ such that $a^N \equiv 1$ (mod $m)$. Now assume that $a^n \not\equiv 1$ (mod $m$) for all $n < m$. Can you show that this means that $a^i$ are all pairwise not congruent to each other for all $i < m$? What would that imply?

Answer 3

This is because, if $\gcd(a,m)=1$, Euler's theorem asserts that $a^{\varphi(m)}\equiv 1\pmod m$.

Now, if $p_1, \dots,p_s$ are the prime factors of $m$, one has $$\frac{\varphi(m)}m=\Bigl(1-\frac1{p_1}\Bigr)\dotsm\Bigl(1-\frac1{p_s}\Bigr)<1$$ so that $\;\varphi(m)<m$.