Test Tomorrow .Help Fermat's Little Theroem

  • Thread starter trap101
  • Start date
  • Tags
    Test
In summary, the OP is trying to find a number that is congruent to -1 (mod p) but can't seem to figure it out.
  • #1
trap101
342
0
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.
 
Physics news on Phys.org
  • #2


Just count the ones =)
 
  • #3


Ansatz7 said:
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)
 
  • #4


trap101 said:
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...
 
  • #5


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


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


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


trap101 said:
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?
 
  • #9


HallsofIvy said:
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.
 
  • #10


HallsofIvy said:
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.
 
  • #11


Ansatz7 said:
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...
 
  • #12


trap101 said:
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.
 
  • #13


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


Ansatz7 said:
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)
 
  • #15


trap101 said:
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.
 
  • #16


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


trap101 said:
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!
 
  • #18


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.
 

1. What is "Test Tomorrow"?

"Test Tomorrow" refers to a test or exam that is scheduled to take place the following day.

2. What is Fermat's Little Theorem?

Fermat's Little Theorem is a mathematical theorem that states that if p is a prime number, then for any integer a, the number a^p - a is a multiple of p.

3. How is Fermat's Little Theorem used in testing?

Fermat's Little Theorem is often used in cryptography and number theory to test the primality of large numbers.

4. Can you provide an example of Fermat's Little Theorem in action?

For example, if we have the prime number 7 and the integer 3, we can see that 3^7 - 3 = 2187 - 3 = 2184, which is a multiple of 7. This confirms that 7 is indeed a prime number.

5. How can I use Fermat's Little Theorem to prepare for a test?

You can use Fermat's Little Theorem to practice solving primality tests and strengthen your understanding of number theory concepts, which may be covered on your test.

Similar threads

  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
928
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top