Results 1 to 2 of 2

Math Help - Help with proof using Wilson's theorem

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    13

    Help with proof using Wilson's theorem

    Let p be an odd prime and let a_1, . . . ,a_{p-1}\ be a permutation of \{1, 2, . . ., p-1\}. Prove that there exist i \not = j such that ia_i\equiv ja_j(\bmod p).

    How can I use Wilson's theorem to prove this. I appreciate any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by didact273 View Post
    Let p be an odd prime and let a_1, . . . ,a_{p-1}\ be a permutation of \{1, 2, . . ., p-1\}. Prove that there exist i \not = j such that ia_i\equiv ja_j(\bmod p).

    How can I use Wilson's theorem to prove this. I appreciate any help.
    Say that there was no i\not =j so that ia_i \equiv ja_j(\bmod p). Therefore, 1\cdot a_1,2\cdot a_2, 3\cdot a_3, ... , (p-1)\cdot a_{p-1} are all incongruent to eachother. There are p-1 of them which means that they are a permutation of a_1,...,a_{p-1} by pigeonhole principle. Therefore, (a_1)(2a_2)(3a_3)...((p-1)a_{p-1}) \equiv (a_1)...(a_{p-1})(\bmod p). Canceling we get, (p-1)!\equiv 1(\bmod p), but this is a contradiction because (p-1)!\equiv -1(\bmod p).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence Proof using Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 11th 2011, 08:08 AM
  2. Proof involving Wilson's theorem.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 11th 2010, 06:30 PM
  3. Regarding Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 5th 2010, 01:53 PM
  4. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 01:07 PM
  5. Wilson's theorem proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 16th 2009, 05:48 AM

Search Tags


/mathhelpforum @mathhelpforum