So I have to prove Fermats Little Theorem which states that if p is a prime and a is a integer that cannot be divided by $p$, then

$a^{p-1}\equiv 1\pmod{p}$.

So my proof is:

Let $p$ be a prime and a be a integer that cannot be divided by $p$. Consider the two sequences of numbers where we represent the residual classes with the numbers $1,2,...,p-1$:

$x: 1, 2, 3, \ldots, (p-1)$, which are the residual classes,

$a\cdot x: a\cdot 1, a\cdot 2, ..., a\cdot (p-1)$.

Since $\gcd(a,p)=1$, two different numbers in the second row cannot be congruent modulo $p$. If they were we would have that $c\cdot a≡b\cdot a\pmod{p}, 1\le c<b \le p-1$ and since $\gcd(a,p)=1$ we can cancel out $a$ so $c\equiv b\pmod{p}$ which means that $c=b$. This means that we have the same remainders mod $p$ in both rows (maybe in a different order).

We therefore have that $(a\cdot 1)\cdot (a\cdot 2) \cdot \cdots \cdot (a\cdot (p-1))\equiv 1\cdot 2\cdot 3\cdot \cdots \cdot (p-1)\pmod{p}$. This means that $a^{p-1}\cdot 1\cdot 2\cdot \cdots \cdot (p-1)≡1\cdot 2\cdot \cdots \cdot (p-1)\pmod{p}$.

Since $2,3,...,(p-1)$ are relatively prime with $p$ we can cancel them out so we get that

$a^{p-1}\equiv 1\pmod{p}$.

Are there any errors or places which needs better/more explanation? Thank you for your time!

  • 1
    $\begingroup$ Yes, this looks exactly like one of the proofs here, using modular arithmetic. Did you compare it already? Same question also here at this site. Looks also the same. $\endgroup$ Commented Dec 11, 2018 at 13:57
  • $\begingroup$ Yes I have looked, I might not have specified what part of the proof I'm not sure about. It's the part where I explain why two numbers in the second row cannot be congruent modulo p, is that explanation correct? $\endgroup$
    – statman
    Commented Dec 11, 2018 at 14:06

1 Answer 1


Your proof is correct. I’d try to be a little more technical and state that $\phi: x \mapsto ax$ is a permutation over the residues (you prove this the way you already did) and use modular inverses instead of “cancel out”, but everything is correct.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .