Test Tomorrow.....Help!!!....Fermat's Little Theroem

trap101

Prove that if "p" is an odd prime, then

a) 1^p-1+2^p-1+.....+(p-1)^p-1 "is congruent" to -1(mod p)

attempt: Well I know from Fermat's little theorem, that all the constants on the left hand side will reduce to 1's:

1 + 1 + 1...........1 (is congruent to) -1 (mod p).

I know there is just a small step to conclude this, but I can't figure it out.

b) 1^p+2^p+.....+(p-1)^p (congruent to) 0 (mod p) (Hint: it may be useful to show: 1+2+....+(p-1) = p(p-1) / 2

Kinda lost with this one sad thing is I got help with it today...smh.

Ansatz7

Just count the ones =)

trap101

What do you mean?...If I count the ones on the LHS, I will have p-1 of them, but that would make it congruent to 1(mod p) not -1(mod p)

Ansatz7

That's not true...

trap101

Ok, well if I add up all the ones I would have some sort of sum 1(p-1) which would leave me with (p-1) congruent to ____ (mod p), but the only "something" i could fathom would be "1"

Ansatz7

I don't think you understand the concept of congruence. Go back to the definition. What does it mean for a to be congruent to b mod p?

trap101

a = pk + b for some constant k, or p|a-b

HallsofIvy

Seriously? p- 1 has the property that if you add 1, you get p= 0 (mod p). What do we call the number that, added to 1, gives 0?

Ansatz7

Exactly... if you (the OP) don't mind my asking, what level (middle school, high school, university) is the course you are taking? It seems like you don't have a clear understanding of congruence yet, but have somehow gotten to Fermat's little theorem... it seems strange to me.

trap101

well adding -1 to 1 will give 0. But I'm not seeing it with respect to congruence.

trap101

university level course.....

Ansatz7

Try adding multiples of p to p-1... there isn't really any more help anyone can give.

trap101

as far as congruence, my understanding is this: it is the relationship between a divisor and the number being divided, in which the remainder that is obtained can be compared with another number divided by the same divisor that obtains a similar remainder.

trap101

Well that's great....Just so I'm on firm ground with the question:

1 + 1 + 1...........1 (is congruent to) ______ (mod p)

adding up all those one's will give me:

(p-1) (congruent to) ______ (mod p)

Ansatz7

Yes, the question is entirely clear. I'm frankly having a hard time believing that you are (presumably) at least a week or so into a university-level number theory course and you cannot show that (p - 1) is congruent to -1 (mod p), unless you're just having silly moment. Think about the definitions of congruence you have posted (I personally think a = pk + b is easiest for this purpose, but of course they are all equivalent). Remember that k can be ANY integer.

trap101

I think I just realized it:

So going back to the fact that I will have a sum of (p-1), p|(p-1) can be written as p(1) + (-1).....in other words, my "remainder" is -1 and so (p-1) "is congruent to" -1 (mod p)



sometimes I get so possessed into thinking of the congruence as an equals sign and start carrying things over from side to side.


Thanks by the way.

Ansatz7

Yes!