1
$\begingroup$

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!

$\endgroup$
  • $\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$ – Dietrich Burde Dec 11 '18 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$ – Nikolaj Dec 11 '18 at 14:06
0
$\begingroup$

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.

$\endgroup$

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.