# Thread: What is modulo and Binomial?

1. ## 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"

2. ## Re: What is modulo and Binomial?

Originally Posted by orange gold
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

\displaystyle \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, $\displaystyle \frac{1}{6}\equiv 6^{-1}\pmod{n}$, and this inverse exists iff $\displaystyle \gcd(6,n)=1$ (i.e. $\displaystyle 2\nmid n$ and $\displaystyle 3\nmid n$).

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

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

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

I hope this makes sense!

3. ## 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

4. ## Re: What is modulo and Binomial?

Originally Posted by orange gold
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