Remainder when a binomial coefficient is divided by a prime

Question

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.

Answer 1

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}$

Answer 2

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$.

Answer 3

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.