Fermat's Little Theorem and Exponential Congruences

kmeado07 · Mar 18, 2009

Homework Statement

From fermat's little theorem deduce that when p is prime,

n^p is equivalent to n (mod p)

for all integers n.

I know from Fermat's Little Theorem that ,

n^(p-1) is equivalent to 1 (mod p),

but i don't know how to use it for this particular question.

Dick · Mar 18, 2009

If a is equivalent to b mod(p) then c*a is equivalent to c*b mod(p). What might be a good choice for c in your problem?

kmeado07 · Mar 18, 2009

ok, so in my question, c=n ?
So by dividing by n i would get,

1^p is equiavlent to 1 (mod p)

How do i reach n^(p-1) on the left hand side?

Dick · Mar 18, 2009

n^p divided by n IS NOT 1^p. PLEASE stop and review algebra with exponents before you try to continue.

kmeado07 · Mar 18, 2009

sorry, silly mistake.
dividing by n would give me,

n^(p-1) equivalent to 1 (mod p)

which is fermat's little theorem. so is this all i need to do?

kmeado07 · Mar 18, 2009

This is ok if p doesn't divide n, but the question asks me for all integers n.
So how do i show it's also true for when p divides n?

Dick · Mar 18, 2009

kmeado07 said:

This is ok if p doesn't divide n, but the question asks me for all integers n.
So how do i show it's also true for when p divides n?

You actually want to go the other way. Start with Fermat's little theorem and then go to your conclusion. Multiply by n, you can always do that.