Multiplicative order and powers

Question

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)$ ?

Answer 1

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.