1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Test Tomorrow .Help Fermat's Little Theroem

  1. Feb 27, 2012 #1
    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. jcsd
  3. Feb 27, 2012 #2
    Re: Test Tomorrow.....Help!!!....Fermat's Little Theroem

    Just count the ones =)
     
  4. Feb 27, 2012 #3
    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)
     
  5. Feb 27, 2012 #4
    Re: Test Tomorrow.....Help!!!....Fermat's Little Theroem

    That's not true...
     
  6. Feb 27, 2012 #5
    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"
     
  7. Feb 27, 2012 #6
    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?
     
  8. Feb 27, 2012 #7
    Re: Test Tomorrow.....Help!!!....Fermat's Little Theroem

    a = pk + b for some constant k, or p|a-b
     
  9. Feb 27, 2012 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
  10. Feb 27, 2012 #9
    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.
     
  11. Feb 27, 2012 #10
    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.
     
  12. Feb 27, 2012 #11
    Re: Test Tomorrow.....Help!!!....Fermat's Little Theroem


    university level course.....
     
  13. Feb 27, 2012 #12
    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.
     
  14. Feb 27, 2012 #13
    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.
     
  15. Feb 27, 2012 #14
    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)
     
  16. Feb 27, 2012 #15
    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.
     
  17. Feb 27, 2012 #16
    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.
     
  18. Feb 27, 2012 #17
    Re: Test Tomorrow.....Help!!!....Fermat's Little Theroem

    Yes!
     
  19. Feb 27, 2012 #18

    kai_sikorski

    User Avatar
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Test Tomorrow .Help Fermat's Little Theroem
  1. Fermat test (Replies: 3)

  2. Fermat Little Theorem? (Replies: 10)

Loading...