# Multiplicative order when gcd=1

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 ?

Thanks

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$$.
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?
• Why as $gcd(a,m) = 1$, there is some $N$ such that $a^N \equiv 1$ (mod $m)$? Commented May 21, 2019 at 15:07
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).