# Fermats Little Theorem Proof

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 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!

• 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. – Dietrich Burde Dec 11 '18 at 13:57
• 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? – Nikolaj Dec 11 '18 at 14:06

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