# Thread: Proving Fermat's Little Theorem

1. ## Proving Fermat's Little Theorem

Hi there,

I have been trying to prove Fermat's little Theorem $n^x-n$ is divisible by x when x is a prime number) by using mathematical induction and without using modular arithmetic. I think I have got the proof all correct but if someone could quickly read through it to make sure it is correct it would be very helpful and for those people that are experts at math I don't think it would take very long at all!

I have tried to use LaTex but I am not too sure how well I succeeded in using it. So as a backup I have also made a screenshot of it typed up in word so that you can see it there. I have hyperlinked to the image hosted on imageshack.

Link to image proof: Imageshack - induction.png

Typed Proof:

${x \choose r}$ denotes $\frac{x!}{r!(x-r)!}$ (binomial theorem)

P(k) = $k^x-k$ is divisible by x when x is a prime
Check when k=1 x=2
P(2) = $1^2-1$ = 0 so true for P(1) assume true for P(k)
$(k^2)-k=2A$ (where A is an integer)
Prove P(k+1)[/tex] is divisible by 2
$(k+1)^2-(k+1)$
$k^2+2k+1-k-1$
$(k^2-k)+2k$ (substitute in $k^2-k = 2A$)
$2A+2k$
$2(A+k)$
So divisible by 2 when x=2 for all k.

Prove for all x
$k^x+k$ is divisible
P(1) $1^x-1 = 0$ which is divisible by x
Assume true for k
$k^x-k = xA$ (where x is a prime and A is any integer)
$(k+1)^x-(k+1)$
${x \choose 0}k^x+{x \choose 1}k^{x-1}...{x \choose x-2}k^2+{x \choose x-1}k^1+{x \choose 0}1-(k+1)$
$k^x + {x \choose 1}k^{x-1}...{x \choose x-2}k^2 +{x \choose x-1}k^1 + 1 - (k+1)$(simplify)
$[k^x - k] + {x \choose 1}k^{x-1}...{x \choose x-2}k^2 + {x \choose x-1}k^1$
$xA + {x \choose 1}k^{x-1}...{x \choose x-2}k^2 +{x \choose x-1}k^1$ (substitute in $k^x-k = xA$)

${x \choose r}$ is divisible by x when x is a prime and $r \not= x$ or $\not= 0$ because there are no prime factors in the denominator but there is one in the numerator. As in the above equation the binomial coefficients don’t have $r=x$ or $r=0$. So a common x may be brought out

$x\frac{(x-1)!}{r!(x-r)!}$ (bringing out x)

$x(A + {x-1 \choose 1}k^{x-1}...{x-1 \choose x-1}k^2 + {x-1 \choose x-2}k^1)$

So by principle of mathematical induction $k^x+k$ is divisible by x when x is a prime and k is any positive integer.

So if you could point if it doesn't work out and why it would be much appreciated.

Thanks again
Qwertyuiop23

(Hopefully I have explained myself well enough)

2. I doubt anyone wants to read closely a long proof of something that is quite simple (no offense).
I would suggest learning modular arithmetic if you wanted to clarify your understanding of integers. Almost every book about elementary number theory begins with those ideas.

Here is a very simple proof :
$\mathbb{Z}/p\mathbb{Z} = \mathbb{F}_p$ is a field. In perticular its $p-1$ nonzero elements form a group under the multiplication of $\mathbb{F}_p$. But in any finite group of order $n$, we have $x^n=1$ for all $x \in G$. Hence in this case $x^{p-1}=1$, or in other words $x^{p-1}-1$ is divisible by $p$.

3. Originally Posted by Qwertyuiop23
I have been trying to prove Fermat's little Theorem $n^x-n$ is divisible by x when x is a prime number) by using mathematical induction and without using modular arithmetic.
As you can see, using induction is very cumbersome – but, for your sake, I took the trouble of looking through your proof and didn’t find any mistake. Still, I would repeat Bruno J.’s advice that it’s much better to use modular arithmetic instead. This has many important applications in algebra, not just in proving theorems like this, so learning modular arithmetic is highly to be recommended.