# Test Tomorrow .Help Fermat's Little Theroem

1. Feb 27, 2012

### trap101

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

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.

2. Feb 27, 2012

### Ansatz7

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

Just count the ones =)

3. Feb 27, 2012

### trap101

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

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)

4. Feb 27, 2012

### Ansatz7

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

That's not true...

5. Feb 27, 2012

### trap101

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

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"

6. Feb 27, 2012

### Ansatz7

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

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?

7. Feb 27, 2012

### trap101

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

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

8. Feb 27, 2012

### HallsofIvy

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

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?

9. Feb 27, 2012

### Ansatz7

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

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.

10. Feb 27, 2012

### trap101

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

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

11. Feb 27, 2012

### trap101

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

university level course.....

12. Feb 27, 2012

### Ansatz7

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

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

13. Feb 27, 2012

### trap101

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

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.

14. Feb 27, 2012

### trap101

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

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)

15. Feb 27, 2012

### Ansatz7

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

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.

16. Feb 27, 2012

### trap101

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

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.

17. Feb 27, 2012

### Ansatz7

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

Yes!

18. Feb 27, 2012

### kai_sikorski

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

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.