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?

  • $\begingroup$ 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? $\endgroup$ – stackErr May 4 '14 at 3:51
  • $\begingroup$ 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$. $\endgroup$ – John Marty May 4 '14 at 4:01
  • $\begingroup$ Basically the same idea can be used to prove Euler's Theorem $a^{\varphi(m)}\equiv 1\pmod{m}$ if $\gcd(a,m)=1$. $\endgroup$ – André Nicolas May 4 '14 at 5:15
  • 1
    $\begingroup$ 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. $\endgroup$ – David May 4 '14 at 5:23
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.