Results 1 to 4 of 4

Math Help - What is modulo and Binomial?

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    What is modulo and Binomial?

    I saw this:
    binomial(n+3, n) mod n = 1
    How can I solve for a few of the values of n...
    I have a basic understanding of mod such that if something were written: (242%9) I would know the answer to be 8... But what is this binomial form.. I've never seen this notation? Can someone give me an example of working this problem: binomial(n+3, n) mod n = 1
    For say the first 3 numbers that work in this equation as "n"
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Santa Cruz, CA
    Posts
    2,844
    Thanks
    3

    Re: What is modulo and Binomial?

    Quote Originally Posted by orange gold View Post
    I saw this:
    binomial(n+3, n) mod n = 1
    How can I solve for a few of the values of n...
    I have a basic understanding of mod such that if something were written: (242%9) I would know the answer to be 8... But what is this binomial form.. I've never seen this notation? Can someone give me an example of working this problem: binomial(n+3, n) mod n = 1
    For say the first 3 numbers that work in this equation as "n"
    This is actually an identity of some kind. To prove it, I would recommend writing this out in factorial form. However, this is not true in all cases -- there is a very important condition that is missing from this statement that I state in the verification process.

    So it follows that

    \begin{aligned}\binom{n+3}{n}\pmod{n} &\equiv \frac{(n+3)!}{n!(n+3-n)!}\pmod{n}\\&\equiv \frac{(n+3)(n+2)(n+1)n!}{n!\cdot 6}\pmod{n}\\ &\equiv \frac{(n+3)(n+2)(n+1)}{6}\pmod{n}\end{aligned}

    Now when we're working with mods, \frac{1}{6}\equiv 6^{-1}\pmod{n}, and this inverse exists iff \gcd(6,n)=1 (i.e. 2\nmid n and 3\nmid n).

    Supposing that 6^{-1} exists, then it follows that

    6^{-1}(n+3)(n+2)(n+1)\pmod{n}&\equiv \ldots

    Thus, I leave it for you to finish verifying that \binom{n+3}{n}\pmod{n}\equiv 1 given that \gcd(6,n)=1.

    I hope this makes sense!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Re: What is modulo and Binomial?

    That seems to give me these numbers:
    1 5 7 11 13 17 19 23 25 29 31 35 37 41 43...
    But the OEIS that showed me that formula gave this list as the answers:
    25,35,49,55,65,77,85,91,95,115,119,121...
    A133633 - OEIS
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: What is modulo and Binomial?

    Quote Originally Posted by orange gold View Post
    That seems to give me these numbers:
    1 5 7 11 13 17 19 23 25 29 31 35 37 41 43...
    But the OEIS that showed me that formula gave this list as the answers:
    25,35,49,55,65,77,85,91,95,115,119,121...
    A133633 - OEIS
    Look up what n mod 1 is for a natural number n.

    Try re-reading the definition of the sequence on OEIS.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 15th 2010, 05:33 AM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 09:04 AM
  3. Replies: 1
    Last Post: October 5th 2009, 11:11 PM
  4. Replies: 1
    Last Post: March 11th 2009, 11:09 PM
  5. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 5th 2007, 06:59 AM

Search Tags


/mathhelpforum @mathhelpforum