# Multiplicative order and powers

Let's consider two number $$a$$ and $$b$$ such as $$gcd(a,b)=1$$. Can you explain me intuitively why there exist $$n>0$$ such as $$a^{n} \equiv 1 \space (mod \space b)$$ ?

• If you start looking at powers of $a$ you'd eventually start getting repeats when considering the result modulo $b$, say $a^x$ and $a^{x+y}$ both resulting in $z\pmod{b}$, but then $a^xa^y\equiv a^x\equiv z\pmod{b}$. Try to reason that $a^y\equiv 1\pmod{b}$, using the fact that $a$ is coprime to $b$ and so $z$ is as well. Commented May 22, 2019 at 13:21
• At this point, can we infere that $y<b$ ? If yes how ? Commented May 22, 2019 at 13:30
• Why should we care that $y<b$? From what I wrote alone, no you cannot, but you can add a few additional conditions... changing the opening statement to "If you start looking at the first $b$ powers of $a$ you'd eventually start getting repeats..." We know that we'll get repeats because of the pigeon-hole principle, us having at most $b-1$ holes (since it is impossible for $a^x \equiv 0\pmod{b}$) and having $b$ pigeons. This guarantees that $1\leq x<x+y\leq b$ and so $1\leq y\leq b-x<b$ Commented May 22, 2019 at 13:34
• Thanks so much, if you post i vote your answer as the correct one Commented May 22, 2019 at 13:47

Sure:

• Exponents don't cause a change in gcd.
• There are finitely many remainders possible.
• There are, therefore, repeated remainders are forced after a certain point.

A proof of Fermat's little theorem I once saw is as follows:

Let A, be the set of all products of a, and one of the natural numbers less than b (b in this case is prime, and $$\gcd(a,b)=1$$). Any of these giving same remainder on division by b, implies that the two natural numbers a was multiplied by, are congruent mod b. This of course is impossible.

The product of all elements of set A, is: $$a^{b-1}(b-1)!$$ and the set of all non-zero remainders is forced to occur in this set by the above argument, so $$a^{b-1}(b-1)!\equiv (b-1)!\bmod b$$ which turns into:$$a^{b-1}\equiv 1\bmod b$$ when you cancel the factor of factorial on both sides.

It then follows using $$1^r=1$$ and it's equivalent in modulo that all multiples of $$b-1$$ , as exponents are 1 mod b . These combine in the composite cases.