Hi there,

I have been trying to prove Fermat's little Theorem $\displaystyle 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:

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

P(k) = $\displaystyle k^x-k$ is divisible by x when x is a prime

Check when k=1 x=2

P(2) = $\displaystyle 1^2-1$ = 0 so true for P(1) assume true for P(k)

$\displaystyle (k^2)-k=2A$ (where A is an integer)

Prove P(k+1)[/tex] is divisible by 2

$\displaystyle (k+1)^2-(k+1)$

$\displaystyle k^2+2k+1-k-1$

$\displaystyle (k^2-k)+2k$ (substitute in $\displaystyle k^2-k = 2A$)

$\displaystyle 2A+2k$

$\displaystyle 2(A+k)$

So divisible by 2 when x=2 for all k.

Prove for all x

$\displaystyle k^x+k$ is divisible

P(1) $\displaystyle 1^x-1 = 0$ which is divisible by x

Assume true for k

$\displaystyle k^x-k = xA$ (where x is a prime and A is any integer)

$\displaystyle (k+1)^x-(k+1)$

$\displaystyle {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)$

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

$\displaystyle [k^x - k] + {x \choose 1}k^{x-1}...{x \choose x-2}k^2 + {x \choose x-1}k^1$

$\displaystyle xA + {x \choose 1}k^{x-1}...{x \choose x-2}k^2 +{x \choose x-1}k^1$ (substitute in $\displaystyle k^x-k = xA$)

$\displaystyle {x \choose r}$ is divisible by x when x is a prime and $\displaystyle r \not= x $ or $\displaystyle \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 $\displaystyle r=x$ or $\displaystyle r=0$. So a common x may be brought out

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

$\displaystyle 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 $\displaystyle 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)