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

by trap101
Tags: test, theroem, tomorrowhelpfermat
 P: 334 Prove that if "p" is an odd prime, then a) 1p-1+2p-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) 1p+2p+.....+(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.
 P: 29 Just count the ones =)
P: 334
 Quote by Ansatz7 Just count the ones =)
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)

P: 29
Test Tomorrow....Help ...Fermat's Little Theroem

 Quote by 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)
That's not true...
 P: 334 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"
 P: 29 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?
 P: 334 a = pk + b for some constant k, or p|a-b
Math
Emeritus
Thanks
PF Gold
P: 39,497
 Quote by 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"
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?
P: 29
 Quote by 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?
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.
P: 334
 Quote by 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?

well adding -1 to 1 will give 0. But I'm not seeing it with respect to congruence.
P: 334
 Quote by 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.

university level course.....
P: 29
 Quote by trap101 well adding -1 to 1 will give 0. But I'm not seeing it with respect to congruence.
Try adding multiples of p to p-1... there isn't really any more help anyone can give.
 P: 334 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.
P: 334
 Quote by Ansatz7 Try adding multiples of p to p-1... there isn't really any more help anyone can give.

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)
P: 29
 Quote by 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)
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.
 P: 334 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.
P: 29
 Quote by 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)
Yes!
 PF Gold P: 162 I think that people who use the ! operator in programing, often get really confused about congruence because they can't think of it as defining equivalence classes and rather thing about it as an operator.

 Related Discussions Calculus & Beyond Homework 13 Calculus & Beyond Homework 3 Biology, Chemistry & Other Homework 5 Linear & Abstract Algebra 2 Linear & Abstract Algebra 8