Results 1 to 2 of 2

Thread: Help with proof using Wilson's theorem

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    13

    Help with proof using Wilson's theorem

    Let $\displaystyle p$ be an odd prime and let $\displaystyle a_1, . . . ,a_{p-1}\$ be a permutation of $\displaystyle \{1, 2, . . ., p-1\}$. Prove that there exist $\displaystyle i \not = j$ such that $\displaystyle 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
    10
    Quote Originally Posted by didact273 View Post
    Let $\displaystyle p$ be an odd prime and let $\displaystyle a_1, . . . ,a_{p-1}\$ be a permutation of $\displaystyle \{1, 2, . . ., p-1\}$. Prove that there exist $\displaystyle i \not = j$ such that $\displaystyle 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 $\displaystyle i\not =j$ so that $\displaystyle ia_i \equiv ja_j(\bmod p)$. Therefore, $\displaystyle 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 $\displaystyle p-1$ of them which means that they are a permutation of $\displaystyle a_1,...,a_{p-1}$ by pigeonhole principle. Therefore, $\displaystyle (a_1)(2a_2)(3a_3)...((p-1)a_{p-1}) \equiv (a_1)...(a_{p-1})(\bmod p)$. Canceling we get, $\displaystyle (p-1)!\equiv 1(\bmod p)$, but this is a contradiction because $\displaystyle (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: Apr 11th 2011, 08:08 AM
  2. Proof involving Wilson's theorem.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Dec 11th 2010, 06:30 PM
  3. Regarding Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: Aug 5th 2010, 01:53 PM
  4. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 10th 2010, 01:07 PM
  5. Wilson's theorem proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 16th 2009, 05:48 AM

Search Tags


/mathhelpforum @mathhelpforum