Results 1 to 3 of 3

Math Help - Proving Fermat's Little Theorem

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    11

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by Qwertyuiop23 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fermat's little theorem help!
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: January 17th 2011, 08:16 PM
  2. Replies: 4
    Last Post: January 10th 2011, 08:51 AM
  3. Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2010, 01:33 AM
  4. fermat's little theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 15th 2010, 04:20 PM
  5. Not Fermat's Last Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 8th 2008, 10:39 PM

Search Tags


/mathhelpforum @mathhelpforum