# Odd Primes with Modulo

• Nov 17th 2009, 07:42 PM
zachsch
Odd Primes with Modulo

Let p be an odd prime. Given:

(x+1)^p = x^p + 1^p (mod p)

holds for any integer x, prove n^p = n(mod p) for all integers n.

Any help would be greatly appreciated!!
• Nov 17th 2009, 08:30 PM
tonio
Quote:

Originally Posted by zachsch

Let p be an odd prime. Given:

(x+1)^p = x^p + 1^p (mod p)

holds for any integer x, prove n^p = n(mod p) for all integers n.

Any help would be greatly appreciated!!

Induction on n: for n= 1 is trivial, so suppose it's true for n-1 and then:

$\displaystyle n^p=(n-1+1)^p\buildrel\text{ind. hyp.}\over=(n-1)^p+1^p\!\!\!\pmod p$ ...take it from here

Tonio
• Nov 17th 2009, 08:36 PM
zachsch
How would I go about "taking it from here"?
• Nov 17th 2009, 08:51 PM
tonio
Quote:

Originally Posted by zachsch
How would I go about "taking it from here"?

Well, for that you'll have to think and make a little effort instead of writing back immediately asking for the solution...

Tonio
• Nov 17th 2009, 09:25 PM
zachsch
Got it! Thanks a million!!!
• Nov 18th 2009, 08:59 AM
gmatt
By the way you said in your hypothesis that p has to be odd, implying that this does not work for p=2. It does in fact work for p=2.

Also, the proof of the hypothesis is far more interesting than the proof of your statement, which is practically a corollary of the hypothesis.