Proof of n^m - n Divisible by m for Positive Integers

[JasonJo]

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?

 

[StatusX]

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.