Prove $a^p\equiv a\pmod p$

Question

Prove $a^p\equiv a\pmod p$, $p$ is a prime number.

Well, apart from writing this as $ a^p \pmod p = a \pmod p$ I don't know how to continue from here.

https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem — TIWARI, Nov 17 '16 at 17:05
@TIWARI Proofs are too complicated in there, can you please help me find a simple proof for this? — Ilan Aizelman WS, Nov 17 '16 at 17:07
If you want some kind of intuition then check this https://www.youtube.com/watch?v=OoQ16YCYksw and again see the proof you will find it simple — TIWARI, Nov 17 '16 at 17:11
$$2^6=64\neq2\pmod 6$$ Anyway, @IlanAizelmanWS : this theorem is true in general for $;p;$ a prime . — DonAntonio, Nov 17 '16 at 17:30
@DonAntonio: And $a$ coprime (relatively prime) with respect to $p$. — barak manos, Nov 17 '16 at 17:37
Most all of the common proofs are listed in the Wikipedia article. If you have a specific question about one of them then you should state it, or else you should give some context telling us what number theory or group theory methods you know. — Bill Dubuque, Nov 17 '16 at 17:52
@barakmanos Not really: the equivalence $;a^p=a\pmod p;$ is always true for $;p;$ prime and any $;a\in\Bbb Z;$ . Perhaps you're thinking of the also well known $;a^{p-1}=1\pmod p;$ , which requires $;p;$ a prime and $;(a,p)=1;$ and which, in fact, follows from the first one. — DonAntonio, Nov 17 '16 at 18:03

score 3 · Accepted Answer · answered Nov 17 '16 at 18:00

I'm assuming $p$ is prime. If $p\mid a$, then $a^p\equiv 0 \equiv a \pmod{p}$ and we're done. If $p\nmid a$ then notice that both $\{1,2,\ldots,p-1\}$ and $\{a,2a,3a,\ldots,(p-1)a\}$ are reduced residue systems modulo $p$, and so the numbers in one set have to be congruent to the numbers in the other set, in some order. Therefore the products of both sets are congruent modulo $p$.

$$1\cdot 2\cdot 3\cdots (p-1) \equiv a(2a)(3a)\cdots (p-1)a \pmod{p}.$$

Rearrange a bit:

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

Since $(p-1)!$ is relatively prime to $p$, we can divide it out:

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

Now multiply through by $a$ and we're done.

score 2 · Answer 2 · answered Nov 17 '16 at 18:09

First of all, rewrite the theorem : let $p$ be a prime number $\forall a \in \mathbb{N}, a^p \equiv a [p]$

1: For all we show $\forall k, 0<k<p, p|\binom{p}{k}$.

We know $k\binom{p}{k}=p\binom{p-1}{k-1}$ (you can show that easily), and $0<k<p$ so $\gcd(k,p)=1$ and by the gauss theorem $p|\binom{p}{k}$.

2: By induction on $a$ :

For $a=0$ it is ok.

Let assume that it is true $\forall a\in \{1,..p-2\}$ by the binomial formula we have :

$(a+1)^p=n^p+\sum_{k=1}^{p-1}\binom{p}{k}n^k+1\equiv a+1 [p]$ because $\forall k \in \{1,..p-1\},\binom{p}{k}\equiv 0 [p]$

Prove $a^p\equiv a\pmod p$

2 Answers2