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?

  • 6
    $\begingroup$ Are you familiar with proof by mathematical induction? It looks like Theorem 2 is the induction step in the proof of Theorem 3. $\endgroup$ – Gerry Myerson Feb 23 '14 at 9:14
  • $\begingroup$ 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. $\endgroup$ – Emmet B Feb 23 '14 at 9:20
  • 3
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 23 '14 at 9:24
  • $\begingroup$ thanks that cleared a lot. $\endgroup$ – 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.

  • 1
    $\begingroup$ there is a small typo there in the second term it should be (1+1) instead of (1-1) $\endgroup$ – Emmet B Feb 23 '14 at 9:43
  • $\begingroup$ @EmmetB, thanks, fixed. $\endgroup$ – Karolis Juodelė Feb 23 '14 at 11:39

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.