- #1
JasonJo
- 429
- 2
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?
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?