Proof of Wilson's Theorem

In the elementary proof here, we solve by pairing an element with its inverse. Why do we know necessarily that this will always happen?

  • 2
    Hint. You know every element has an inverse. When can an element be its own inverse (remember your modulus is prime)? – Ethan Bolker Feb 16 '16 at 14:43
  • when it is congruent to -1 or 1! thanks – feng Feb 16 '16 at 14:45
  • You didn't read the article correctly. It explains that at length. – Yves Daoust Feb 16 '16 at 14:56

Your real question is: how do we know we can pair each element with its own inverse?

The answer to this can be broken into a few pieces.

  1. Every integer relatively prime to $p$ has an inverse mod $p$.
  2. If $a$ has inverse $a^{-1}$ then $a^{-1}$ has inverse $a$.
  3. What about elements which are their own inverse? This amounts to solving $x^2 \equiv 1 \pmod p$, whose only solutions are $x \equiv \pm 1 \pmod p$.

And that's it. If there is a substep which you are not familiar with, then you might consider trying to prove it, or looking it up here or in your text.

  • @ThomasAndrews: Could you explain the details about your first comment? – Isana Yashiro Sep 14 at 6:48
  • 1
    @Nong In the previous version of this answer, I omitted the "relatively prime" statement. – davidlowryduda Sep 14 at 13:27

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.