# Fermat's little theorem proof by Euler

I am reading a book, it explains the Euler's proof of Fermat's little theorem (FLT). There are 3 theorems are presented to prove FLT, I understood the first two (I will skip the proof of each theorem), but I could not understand the proof of third theorem.

Theorem 1. if $p$ is prime then, $\quad(a+1)^p- (a^p + 1) = 0\mod p$

Theorem 2. $(a+1)^p-(a+1) = 0 \mod p \quad$ if $\quad a^p = a\mod p$

Theorem 3. $a^p = a \mod p$

I understood the first two, but then in Theorem 3 the author proves this step by using Theorem 2. But my confusion is that Theorem 3 was assumed in Theorem 2, looks like a circular reasoning. Is this the Euler's original proof for FLT? What is the Euler's original proof?

• Are you familiar with proof by mathematical induction? It looks like Theorem 2 is the induction step in the proof of Theorem 3. – Gerry Myerson Feb 23 '14 at 9:14
• Indeed the author says in step 2 and 3 induction is used. I am a little familiar with induction, I understand the base case, but I could not understood the induction step. – Emmet B Feb 23 '14 at 9:20
• When you want to use induction to prove something for all $a$, first you prove it for some base case, then you prove that if it's true for $a$ it's true for $a+1$, then you conclude it's true for all $a$. Theorem 2 is the "if it's true for $a$ it's true for $a+1$" part. – Gerry Myerson Feb 23 '14 at 9:24
• thanks that cleared a lot. – Emmet B Feb 23 '14 at 9:43

Firstly, $1^p - 1 = 0$. Now, try evaluating $2^p - 2$.
$$2^p - 2 = (1+1)^p - (1+1) = (1^p+1) - (1+1) = 1^p - 1 = 0$$ Rinse and repeat.