Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By Sylvia104
  • 1 Post By Sylvia104

Thread: Wilson's theorem

  1. #1
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    145
    Thanks
    4

    Wilson's theorem

    Hi,

    Would the following constitute a proof of "if n is compositie then (n-1!)=0 mod n"

    We can use the chinese remainder theorem to find $\displaystyle (n-1) mod n. $

    Suppose that $\displaystyle n = p_{1}^{a1}, p_{2}^{a2}...p_{r}^{ar} $

    Then because in each case $\displaystyle p_{i}^{ai} $ is less than (n-1) and so it divides (n-1!). We find that $\displaystyle n-1 =0 mod p_{i}^{ai} $ for all i. Then the CRT implies that n-1 =0 mod n


    Does the above make sense??

    Thanks for any help!
    Last edited by Ant; May 16th 2012 at 03:57 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Wilsonís theorem

    Quote Originally Posted by Ant View Post
    in each case $\displaystyle p_{i}^{ai} $ is less than (n-1)
    This is only true if $\displaystyle i>1;$ it is not true if $\displaystyle i=1$ (i.e. if $\displaystyle n$ is a single-prime power).

    By the way, $\displaystyle (4-1)!\not\equiv0\mod4.$ The converse of Wilsonís theorem only states that if $\displaystyle n$ is composite, then $\displaystyle (n-1)!\not\equiv-1\mod n.$
    Last edited by Sylvia104; May 17th 2012 at 03:15 AM.
    Thanks from Ant
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    145
    Thanks
    4

    Re: Wilsonís theorem

    ah yes, I didn't deal with that case. Thank you
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Sylvia104's Avatar
    Joined
    Mar 2012
    From
    London, UK
    Posts
    107
    Thanks
    37

    Re: Wilsonís theorem

    You were almost correct though. If $\displaystyle n$ is composite, we in fact have

    $\displaystyle (n-1)!\ \equiv\ \left\{\begin{array}{rl} 2\mod n & \text{if}\ n=4 \\\\ 0\mod n & \text{if}\ n>4 \end{array}\right.$

    If $\displaystyle n>4$ and $\displaystyle n=ab$ where $\displaystyle a,b\in\{2,3,\ldots,n-1\},$ then (i) if $\displaystyle a\ne b$ we have straightaway $\displaystyle n=ab\mid(n-1)!$ (ii) if $\displaystyle a=b$ then:

    $\displaystyle a^2=n>4$

    $\displaystyle \Rightarrow\ a>2$

    $\displaystyle \Rightarrow\ n=a^2>2a$

    $\displaystyle \Rightarrow\ a,2a\in\{2,\ldots,n-1\}$

    $\displaystyle \Rightarrow\ n\mid2n=2a^2\mid(n-1)!$
    Thanks from Ant
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Ant
    Ant is offline
    Member
    Joined
    Apr 2008
    Posts
    145
    Thanks
    4

    Re: Wilson's theorem

    I see, so you really needn't split it into coprime divisors of n like I did.

    I had the above proof as an exam questions - hopefully I'll still get some marks for getting close!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 30th 2011, 10:26 AM
  2. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 10th 2010, 01:07 PM
  3. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  4. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 23rd 2008, 07:52 AM
  5. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 7th 2008, 11:41 AM

Search Tags


/mathhelpforum @mathhelpforum