# What suggests the first step in this proof of Fermat's Little Theorem?

I've recently started looking at various different proofs of Fermat's Little Theorem, which states that, for $p$ a prime and $a$ an integer not divisible by $p$, that $a^{p-1} \equiv 1 \mod{p}$. I've looked at various proofs of the result and I see how it can be proved. However, I want to better understand the following proof, due to Ivory:

Consider the following numbers: $a, 2a, \ldots (p-1)a$. We know that these numbers, after re-ordering, are congruent to $1, 2, 3 \ldots, (p-1) \mod{p}$. As $a\times2a\times\ldots\times(p-1)a = a^{p-1}(p-1)!$, we have $a^{p-1}(p-1)! \equiv (p-1)! \mod{p}$. But as $(p-1)!$ and $p$ are coprime, we can cancel. Thus we have $a^{p-1} \equiv 1 \mod{p}$, as required

My question about this is as follows: Why start off by considering the numbers $a, 2a, \ldots (p-1)a$? What is it that suggests that looking at these numbers will lead to the proof? Additionally, are there are any other proofs that use a similar approach?

• But as (p−1)! and p are coprime, we can cancel. Thus we have $a^{p-1} \equiv 1 \mod{p}$ How do you know this? Isn't this applying Fermat's little theorem in the proof itself? – stackErr May 4 '14 at 3:51
• I don't think so, it is just a property of modular arithmetic. if $ax \equiv ay$ mod p $a(x-y) \equiv 0$ mod p. But $a \not \equiv 0$ mod p$,$x \equiv y$mod p$. – John Marty May 4 '14 at 4:01
• Basically the same idea can be used to prove Euler's Theorem $a^{\varphi(m)}\equiv 1\pmod{m}$ if $\gcd(a,m)=1$. – André Nicolas May 4 '14 at 5:15
• As to "what suggests this step", maybe someone can give a good reason for it, but you have to be prepared for the possibility that there is no good reason and that it was just a bright idea which cannot (even retrospectively) be rationalised. Although written mathematics should always be logical, the process of finding out what to write is frequently very far from logical. – David May 4 '14 at 5:23
• This is just speculation, but maybe Ivory wasn't looking for a proof of Fermat's theorem? Maybe he was considering that product for some other reason, and got to that equation, and suddenly realized that it was a proof of Fermat's theorem that he hadn't seen before? This is called serendipity. – bof May 4 '14 at 5:49

The idea is probably best motivated by group theory. In group theory, the integers modulo $p$ behave really nicely under multiplication. In particular, the nice property is that $ab = ac$ implies $b = c$. Therefore, if you are considering $1, 2, 3, \ldots, (p-1)$, and you want to bring $a$ into the picture, a natural thing to do is to exploit the nice symmetry of multiplication by $a$ in the group of integers modulo $p$ under multiplication, by multiplying everything by $a$.
As to why consider $1, 2, 3, \ldots, (p-1)$ in the first place, I think it's as David says: it was probably just a bright idea. One possible motivation (which is probably a stretch) is that you need $p-1$ of something since you have $p-1$ in the exponent.
Of course, if you're going to use the group of integers modulo $p$ to motivate this then you might as well use Lagrange's theorem to prove $a^{p-1} \equiv 1$ directly.