Qwertyuiop23
New member
- Joined
- Jun 7, 2009
- Messages
- 1
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 type it out so you can understand in text format but I am aware it is quite hard to read it like that. 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|r} denotes 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) 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|0}k^x + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 + {x|x}1 – [k+1]
k^x + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 + 1 – [k+1] (simplify)
[k^x – k] + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1
xA + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 (substitute in k^x-k = xA)
{x|r} is divisible by x when x is a prime and r doesn’t = x or 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[(x-1)!/(r!(x-r)!)] (bringing out x)
x(A + { x-1|1}k^(x-1)… { x-1|x-2}k^2 + {x-1|x-1}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 and this is the correct Forum!)
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 type it out so you can understand in text format but I am aware it is quite hard to read it like that. 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|r} denotes 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) 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|0}k^x + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 + {x|x}1 – [k+1]
k^x + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 + 1 – [k+1] (simplify)
[k^x – k] + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1
xA + {x|1}k^(x-1)… {x|x-2}k^2 + {x|x-1}k^1 (substitute in k^x-k = xA)
{x|r} is divisible by x when x is a prime and r doesn’t = x or 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[(x-1)!/(r!(x-r)!)] (bringing out x)
x(A + { x-1|1}k^(x-1)… { x-1|x-2}k^2 + {x-1|x-1}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 and this is the correct Forum!)