Results 1 to 2 of 2

Math Help - Let p be a prime...

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    34

    Let p be a prime...

    Let p be a prime. Let r1, r2, ..., rp-1 be the integers 1, 2, ..., p-1 in some order. Prove that some two of the numbers

    1*r1, 2*r2, ..., (p-1)*rp-1

    must be congruent modulo p.
    [Hint: If not, think of their product modulo p.]

    (The 1, 2, and p-1 when following an r are supposed to be subscript. I can't seem to figure out how to make them and keep them that way.)

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by NikoBellic View Post
    Let p be a prime. Let r1, r2, ..., rp-1 be the integers 1, 2, ..., p-1 in some order. Prove that some two of the numbers

    1*r1, 2*r2, ..., (p-1)*rp-1

    must be congruent modulo p.
    [Hint: If not, think of their product modulo p.]

    (The 1, 2, and p-1 when following an r are supposed to be subscript. I can't seem to figure out how to make them and keep them that way.)



    Well, let's check the product! : r_1\cdot 2r_2\cdot\ldots\cdot(p-1)r_{p-1} ; but by Wilson' Theorem, if all these elements are different modulo p then their product is the same as

    1\cdot 2\cdot\ldots\cdot(p-1)=-1\!\!\!\pmod p . On the other hand we can write 1r_1\cdot 2r_2\cdot\ldots\cdot(p-1)r_{p-1}=(1\cdot2\cdot\ldots\cdot(p-1))(1\cdot2\cdot\ldots\cdot (p-1))=(-1)\cdot(-1)=1\!\!\!\pmod p ...contradiction.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07:51 AM
  4. Replies: 6
    Last Post: August 27th 2010, 11:44 PM
  5. if ((2^n) -1 ) is prime, prove n is prime ?! >.<
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 18th 2009, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum