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

3 Answers 3

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, 2020 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, 2020 at 23:59
  • 1
    $\begingroup$ ... using ${n+1 \choose r+1}$ = ${n \choose r} + {n \choose r+1}$ $\endgroup$
    – wotnotv
    Jun 21, 2020 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, 2020 at 0:08
  • 1
    $\begingroup$ Wow, thanks for correcting it! $\endgroup$
    – UmbQbify
    Jun 21, 2020 at 0:26
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, 2020 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, 2020 at 21:24
  • $\begingroup$ Wow, took me a while to understand. Amazing solution. Thanks! $\endgroup$
    – UmbQbify
    Jun 20, 2020 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, 2020 at 22:22
  • 1
    $\begingroup$ Oh... I guess that's what you got too..... $\endgroup$
    – fleablood
    Jun 20, 2020 at 22:52
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, 2020 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, 2020 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, 2020 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .