# 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}$? Jun 20 '20 at 20:32
• What does it mean if a number is prime? What are its divisors? Jun 20 '20 at 20:38
• Is ${}^{72}C_{36} = \binom{72}{36}$? (If so, the hint is nonsense) 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}$ 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. Jun 20 '20 at 21:08

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? 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}$ Jun 20 '20 at 23:59
• ... using ${n+1 \choose r+1}$ = ${n \choose r} + {n \choose r+1}$ Jun 21 '20 at 0:06
• and 73 divides into ${73 \choose 1}$ , ${73 \choose 2} ...$ but not into ${73 \choose 0}$ Jun 21 '20 at 0:08
• Wow, thanks for correcting it! Jun 21 '20 at 0:26

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. 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$. Jun 20 '20 at 21:24
• Wow, took me a while to understand. Amazing solution. Thanks! 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 Jun 20 '20 at 22:22
• Oh... I guess that's what you got too..... Jun 20 '20 at 22:52

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) 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. 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. Jun 20 '20 at 21:05