# Remainder when a binomial coefficient is divided by a prime

I'm a beginner (started learning yesterday only) in modular arithmetic.

The question is to find the remainder when $${}^{72}C_{36}$$ is divided 73 (where $${}^nC_r$$ denotes $${n \choose k}$$)

I know such problems can be answered by Lucas' theorem, but in this case, it's pointless.

I can't treat $$(36!)^2$$ as modular inverse (and using Wilson's identity) either because the number is huge. Same for Chinese remainder theorem.

And with the above 3 approaches, I'm out of options. No clue how to solve it, even the hint given isn't "good" (and I can't even prove the "hint")

Hint: $${72 \choose 36}={73\choose 0} + {73 \choose 1} +\cdots + {73\choose 36}$$

Everything about this question, including the hint, is just bizzare to me! P. S. I don't want to use the hint (It's actually the complete solution)

And the hint is wrong.

• Can you show that if $1\leq k \leq p-1$ and $p$ is prime that $p | \binom{p}{k}$? – Integrand Jun 20 '20 at 20:32
• What does it mean if a number is prime? What are its divisors? – Integrand Jun 20 '20 at 20:38
• Is ${}^{72}C_{36} = \binom{72}{36}$? (If so, the hint is nonsense) – Brian Moehring Jun 20 '20 at 20:40
• "yes, obviously" That's obnoxious. Not all text use the same notation and it's not clear what the notation $^{72}C_{36}$ is supposed to mean. And as the hint is not true its very unclear what $^{72}C_{36}$ – fleablood Jun 20 '20 at 20:49
• As unsolicited advice, purge the word "obviously" from your mathematical vocabulary. It only served to ignore my point about the hint. I had seen both notations previously, but it is wholly unusual to see them both in the same text, even moreso in the same line. – Brian Moehring Jun 20 '20 at 21:08

## 3 Answers

the hint is nonsense but

I noticed the denominator of $$(36!)(36!)$$ made me think that then numbers $$1$$ to $$36$$ are equiv $$-72$$ througe $$-37\pmod {73}$$ so $$(36!)(36!)\equiv (36!)(-37)*(-38)*...*(-72) \equiv 72!(-1)^{36}\pmod {37}$$ which made me realize the following result:

for any prime $$p$$, because $$\mathbb Z_p$$ is a field and every non-zero equivalence as an inverse:

$${p-1\choose \frac {p-1}2}=\frac {(p-1)!}{(\frac {p-1}2!)^2}\equiv$$

$$(p-1)!\frac 1{1*2*.....*\frac {p-1}2}\frac 1{\frac {p-1}2*....*2*1}\equiv$$

$$(p-1)!\frac 1{1*2*.....*\frac {p-1}2}\frac 1{(-\frac {p+1}2)*....*(-2)*(-1)*(-1)^{\frac {p-1}2}}\equiv$$

$$(p-1)!\frac 1{1*2*......*\frac {p-1}2*\frac {p+1}2*....*(p-2)(p-1)(-1)^{\frac {p-1}2}}\equiv$$

$$(p-1)!\frac 1{(p-1)!(-1)^{\frac {p-1}2}}\equiv(-1)^{\frac {p-1}2}\pmod p$$.

So $${72 \choose 36} \equiv (-1)^{36}\equiv 1 \pmod {73}$$

• Yeah, this is the intelligent way to use Wilson's Theorem. – Integrand Jun 20 '20 at 21:18
• Dont even need Wilson's theory. Just that refering to inverses and division makes sense in $\mathbb Z_p$. – fleablood Jun 20 '20 at 21:24
• Wow, took me a while to understand. Amazing solution. Thanks! – UmbQbify Jun 20 '20 at 21:24
• So actually, for any prime p, binomial coefficient of upper index p-1, the modulo is just $(-1)^{((p-1)-k)}$ for any valid lower index – UmbQbify Jun 20 '20 at 22:22
• Oh... I guess that's what you got too..... – fleablood Jun 20 '20 at 22:52

Just by the way, I think the hint was intended to alternate plus and minus:

$${72 \choose 36}$$ = $${73 \choose 0} - {73 \choose 1} + {73 \choose 2} - ... + {73 \choose 36}$$

$${\qquad\equiv 1} - 0 + 0 - ... + {0 \mod73}$$ $${\qquad\equiv 1\mod73}$$

as $${73}$$ divides into $${73 \choose 1}$$, $${73 \choose 2}$$, ... , $${73 \choose 36}$$, but not into $${73\choose 0}$$.

... built on Jose Carlos Santos's answer, which he deleted.

• Can you prove it? – UmbQbify Jun 20 '20 at 23:53
• ${73 \choose 0} - {73 \choose 1} + {73 \choose 2} - ... - {73 \choose 35} + {73 \choose 36}$ = ${72 \choose 0} - [{72 \choose 0} + {72 \choose 1}] + [{72 \choose 1} + {72 \choose 2}] - ... + [{72 \choose 35} + {72 \choose 36}]$ = ${72 \choose 36}$ – wotnotv Jun 20 '20 at 23:59
• ... using ${n+1 \choose r+1}$ = ${n \choose r} + {n \choose r+1}$ – wotnotv Jun 21 '20 at 0:06
• and 73 divides into ${73 \choose 1}$ , ${73 \choose 2} ...$ but not into ${73 \choose 0}$ – wotnotv Jun 21 '20 at 0:08
• Wow, thanks for correcting it! – UmbQbify Jun 21 '20 at 0:26

Not a very insightful answer, but sometimes there's nothing wrong with getting your hands dirty.

Since $$73$$ is prime, by Wilson's Theorem $$72!\equiv -1 \bmod 73$$. Let's try and compute $$(36!)^2\bmod 73$$.

$$36! = 2^{34}×3^{17}×5^8×7^5×11^3×13^2×17^2×19×23×29×31$$ $$\equiv 55\times 24\times 2 \times 17 \times 17 \times 23\times 70 \times 19\times 23\times 29\times 31$$ $$\equiv 27$$Then since $$27^2 = 729\equiv -1$$, we have $$\binom{72}{36} \equiv -1/-1 =1$$.

• You actually calculated that? How long did it take approximately? I tried doing that (before having any knowledge of modular arithmetic, infact these type of questions motivated me to study modular arithmetic myself which is not taught) – UmbQbify Jun 20 '20 at 21:02
• About 5-10 minutes; it's a Saturday and I don't have too much better to do. Repeated squaring helps a lot, as well as cute tricks (for instance, $55\cdot 4 = 220\equiv 1$, $2^9 =512\equiv 1$, $3^6=726\equiv -1$) that speed things up. – Integrand Jun 20 '20 at 21:04
• There are many very intelligent users on this website, so I won't be surprised if someone finds a more clever solution. – Integrand Jun 20 '20 at 21:05