1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Stuck on a proof by induction

  1. Dec 3, 2009 #1
    im stuck on this proof can anyone help?

    Is it true that for all natural numbers n, for each natural number x, x^n − x is
    divisible by n? If so, prove it; if not, explain why not.

    so far i have gotten:

    make x=1, ((1)^n) -1 = 0, therefore x=1 is divisible by n

    assume true for x=k, ie: (k^n) - k is divisible by n

    make x=k+1; ((k+1)^n)-(k+1).......and thats it!!!
  2. jcsd
  3. Dec 3, 2009 #2


    Staff: Mentor

    Before attempting to prove it, you should first do some work to see if it's actually true. Test the statement with a number of values of n.

    If you believe that it's true, you should be doing your induction on n, not x. Your base case is for n = 1. Can you show that x^1 - x is divisible by 1? If that's too obvious, see if if holds for n = 2. IOW, can you show that x^2 - x is divisible by 2?

    x^2 - x = x(x - 1)
    If x is even, you're done, since an even number times an odd number is even.
    If x is odd, then x - 1 is even, and you're done.

    Now, assume that x^n - x is divisible by n, which means that x^n - x = a*n for some integer a.
    The final step is to show that x^(n + 1) - x is divisible by (n + 1), using the induction hypothesis that x^n - x is divisible by n.
    Last edited: Dec 3, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook