4
$\begingroup$

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.

$\endgroup$
16
  • 2
    $\begingroup$ Can you show that if $1\leq k \leq p-1$ and $p$ is prime that $p | \binom{p}{k}$? $\endgroup$ – Integrand Jun 20 '20 at 20:32
  • 2
    $\begingroup$ What does it mean if a number is prime? What are its divisors? $\endgroup$ – Integrand Jun 20 '20 at 20:38
  • 1
    $\begingroup$ Is ${}^{72}C_{36} = \binom{72}{36}$? (If so, the hint is nonsense) $\endgroup$ – Brian Moehring Jun 20 '20 at 20:40
  • 2
    $\begingroup$ "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}$ $\endgroup$ – fleablood Jun 20 '20 at 20:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Brian Moehring Jun 20 '20 at 21:08
4
$\begingroup$

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

$\endgroup$
10
  • 2
    $\begingroup$ Yeah, this is the intelligent way to use Wilson's Theorem. $\endgroup$ – Integrand Jun 20 '20 at 21:18
  • $\begingroup$ Dont even need Wilson's theory. Just that refering to inverses and division makes sense in $\mathbb Z_p$. $\endgroup$ – fleablood Jun 20 '20 at 21:24
  • $\begingroup$ Wow, took me a while to understand. Amazing solution. Thanks! $\endgroup$ – UmbQbify Jun 20 '20 at 21:24
  • $\begingroup$ 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 $\endgroup$ – UmbQbify Jun 20 '20 at 22:22
  • 1
    $\begingroup$ Oh... I guess that's what you got too..... $\endgroup$ – fleablood Jun 20 '20 at 22:52
10
$\begingroup$

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.

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

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

$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$ – UmbQbify Jun 20 '20 at 21:02
  • 2
    $\begingroup$ 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. $\endgroup$ – Integrand Jun 20 '20 at 21:04
  • 2
    $\begingroup$ There are many very intelligent users on this website, so I won't be surprised if someone finds a more clever solution. $\endgroup$ – Integrand Jun 20 '20 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.