Results 1 to 6 of 6
Like Tree1Thanks
  • 1 Post By Idea

Thread: Modulus proof with factorials

  1. #1
    Junior Member
    Joined
    Feb 2014
    From
    England
    Posts
    54
    Thanks
    2

    Modulus proof with factorials

    Hi everyone
    I'm having trouble with the following question:
    Prove that (2p−1)! ≡ p(mod p^2).
    Hint: p divides (2p-1)!.
    Any help would be much appreciated.
    Thanks, Alex
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,919
    Thanks
    2491

    Re: Modulus proof with factorials

    Quote Originally Posted by alexlbrown59 View Post
    Hi everyone
    I'm having trouble with the following question:
    Prove that (2p−1)! ≡ p(mod p^2).
    Hint: p divides (2p-1)!.
    Any help would be much appreciated.
    Thanks, Alex
    let $p=4$

    $(2p-1)! = 7! = 5040$

    $p^2 = 16$

    $5040 \pmod{16} = 0 \neq 4$

    this sequence in $p$ is a bit interesting, it's $s_p = \begin{cases}p,&p \text{ is prime.} \\ 0, &\text{else} \end{cases}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2014
    From
    England
    Posts
    54
    Thanks
    2

    Re: Modulus proof with factorials

    Sorry I should have put in the original question that p is a prime number! I have to show that it's true for all primes and this is the part I'm struggling with.
    Thanks, Alex.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    753
    Thanks
    341

    Re: Modulus proof with factorials

    Let

    a=\prod _{k=1}^{p-1} (p+k)

    b= \prod _{k=1}^{p-1} k

    a p b=(2p-1)!

    By Wilson's Theorem, a=-1 and b=-1 mod p

    so a b-1 is divisible by p

    a p b - p is divisible by p^2
    Last edited by Idea; Oct 22nd 2016 at 03:04 AM.
    Thanks from johng
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2014
    From
    England
    Posts
    54
    Thanks
    2

    Re: Modulus proof with factorials

    Many thanks for replying but I don't understand the notation you've used...please could you write it out in plain English?
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    753
    Thanks
    341

    Re: Modulus proof with factorials

    a= \prod _{k=1}^{p-1} (p+k)=(p+1)(p+2)\text{...}(p+(p-1))=1*2*\text{...}*(p-1)=(p-1)! (mod p)

    and

    b=\prod _{k=1}^{p-1} k=1*2*\text{...}*(p-1)=(p-1)! (mod p)

    Now, look at (2p-1)!.
    Break it up into the product of three pieces, a, p, and b so that (2p-1)!=a p b

    a=-1 and b=-1 by Wilson's Theorem
    so a b=1 mod p which means a b=1+r p for some r

    (2p-1)!=a p  b=p(1+rp)=p+r p^2

    Therefore (2p-1)!-p is divisible by p^2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction, involving factorials
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 12th 2013, 05:21 PM
  2. Triangular Factorials proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 9th 2011, 12:18 PM
  3. simple yet clever proof with factorials
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 21st 2009, 12:00 AM
  4. Need help with a proof using factorials
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Oct 11th 2009, 05:28 PM
  5. Proof with Factorials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 19th 2009, 02:00 AM

Search Tags


/mathhelpforum @mathhelpforum