2
$\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$
2
  • 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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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