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.
 A: 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}$
A: 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$.
A: 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.
