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
    6,135
    Thanks
    2610

    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
    821
    Thanks
    375

    Re: Modulus proof with factorials

    Let

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

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

    $\displaystyle a p b=(2p-1)!$

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

    so $\displaystyle a b-1$ is divisible by p

    $\displaystyle a p b - p$ is divisible by $\displaystyle p^2$
    Last edited by Idea; Oct 22nd 2016 at 02: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
    821
    Thanks
    375

    Re: Modulus proof with factorials

    $\displaystyle 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

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

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

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

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

    Therefore $\displaystyle (2p-1)!-p$ is divisible by $\displaystyle 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, 04:21 PM
  2. Triangular Factorials proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 9th 2011, 11:18 AM
  3. simple yet clever proof with factorials
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 20th 2009, 11:00 PM
  4. Need help with a proof using factorials
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Oct 11th 2009, 04:28 PM
  5. Proof with Factorials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 19th 2009, 01:00 AM

Search Tags


/mathhelpforum @mathhelpforum