Fermat’s Little Theorem: Induction Proof

Question

I was verifying various proofs of Fermat's Little Theorem lately and stumbled upon a proof by induction, which I think, uses some kind invalid circular argument. Correct me if I am wrong please here.

The steps are as follows:

1. Assume: $n^p \equiv n \pmod p$
2. Work out lemma: $(n+m)^p \equiv n^p + m^p \mod p$ using Binomial expansion
3. Define base case: $n = 1$ (which is true) and prove that it is true for $n < m < p -1$
4. $(n + 1)^p \equiv n^p + 1 \mod p$ by lemma
5. use the assumption from point 1. to prove the assumption from point 1?:):

$n^p + 1 \equiv n + 1 \mod p$

My problem is obviously with step 5. where you are using what you want to proof in the actual proof. (or you have to know that $n^p \equiv n \pmod p$ is somehow true by using other proof, thus rendering this inductive proof useless).

Sources:

• https://proofwiki.org/wiki/Fermat%27s_Little_Theorem#Proof_4
• https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem#Multinomial_proofs

Answer 1

Hint: it is the special case $\,f_n:= n^p\,$ below, working $\bmod p$

Lemma $ $ If $\,f_1\equiv 1\,$ and $\,\forall n\ge 1\!:\ \color{#0a0}{f_{n+1}}\equiv f_n+1\,$ then $\,\forall n\ge 1\!:\ f_n\equiv n$

Proof $ $ We induct on $\,n.\,$ Our hypothesis $\,f_1\equiv 1\,$ is the base case, and the inductive step is just the following easy inference $\,\color{#c00}{f_n\equiv n}\Rightarrow \color{#0a0}{f_{n+1}}\equiv \color{#c00}{f_n}+1\equiv \color{#c00}n+1$