Register to reply

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

by trap101
Tags: test, theroem, tomorrowhelpfermat
Share this thread:
trap101
#1
Feb27-12, 08:46 PM
P: 339
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.
Phys.Org News Partner Science news on Phys.org
Scientists discover RNA modifications in some unexpected places
Scientists discover tropical tree microbiome in Panama
'Squid skin' metamaterials project yields vivid color display
Ansatz7
#2
Feb27-12, 08:59 PM
P: 29
Just count the ones =)
trap101
#3
Feb27-12, 09:03 PM
P: 339
Quote Quote by Ansatz7 View Post
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)

Ansatz7
#4
Feb27-12, 09:04 PM
P: 29
Test Tomorrow....Help ...Fermat's Little Theroem

Quote Quote by trap101 View Post
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...
trap101
#5
Feb27-12, 09:16 PM
P: 339
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
#6
Feb27-12, 09:19 PM
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?
trap101
#7
Feb27-12, 09:22 PM
P: 339
a = pk + b for some constant k, or p|a-b
HallsofIvy
#8
Feb27-12, 09:23 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,682
Quote Quote by trap101 View Post
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?
Ansatz7
#9
Feb27-12, 09:27 PM
P: 29
Quote Quote by HallsofIvy View Post
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.
trap101
#10
Feb27-12, 09:29 PM
P: 339
Quote Quote by HallsofIvy View Post
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.
trap101
#11
Feb27-12, 09:30 PM
P: 339
Quote Quote by Ansatz7 View Post
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.....
Ansatz7
#12
Feb27-12, 09:30 PM
P: 29
Quote Quote by trap101 View Post
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.
trap101
#13
Feb27-12, 09:34 PM
P: 339
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
#14
Feb27-12, 09:43 PM
P: 339
Quote Quote by Ansatz7 View Post
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)
Ansatz7
#15
Feb27-12, 09:49 PM
P: 29
Quote Quote by trap101 View Post
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.
trap101
#16
Feb27-12, 09:54 PM
P: 339
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
#17
Feb27-12, 09:55 PM
P: 29
Quote Quote by trap101 View Post
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!
kai_sikorski
#18
Feb27-12, 10:18 PM
PF Gold
kai_sikorski's Avatar
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.


Register to reply

Related Discussions
Fermat primality test Calculus & Beyond Homework 13
Fermat test Calculus & Beyond Homework 3
Test tomorrow need help Biology, Chemistry & Other Homework 5
A primality test for Fermat numbers faster than Pépin's test ? Linear & Abstract Algebra 2
Fermat test Linear & Abstract Algebra 8