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: How to prove this?

  1. Feb 23, 2006 #1
    My teacher posed this as an extra credit problem on an exam, i couldn't quite prove it. i'm wondering if you guys could help me, i would really like to see the proof even though i already took the exam:

    Prove that if n and m are positive integers, then n^m - n is divisible by m.

    I took a few approaches:

    I tried to pose the problem in mod m. so if n^m - n is divisible by m, then it'll be congruent to 0 mod m. so then i tried to induction on n, but i got stuck on the (k+1)^m expansion. I don't believe this is the correct way.

    Another way I tried was to break it up into cases:
    Case #1: m|n, then it must divide n^m - n
    Case #2: m does not divide n. so then n = mq + r, where r is greater than zero and less than q. then i'm still stuck with a binomial expansion.

    any help guys???
  2. jcsd
  3. Feb 23, 2006 #2


    User Avatar
    Homework Helper

    That's wrong as you've stated it. For example, 6 does not divide 2^6-2=62. But it looks similar to Fermat's little theorem, and you might get something valid if you changed some of the conditions on n and m.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook