Remainder when $^{40}C_{12}$ is divided by $7$.

Question

I was solving a binomial summation problem, and I got $^{40}C_{12}$ as the answer. Now, the question demands to find the remainder when it is divided by $7$. $40!$ can be divided $5$ times by $7$ (using a famous GIF trick.) Unfortunately, $28!$ and $12!$ can be divided $4$ and $1$ time respectively by $7$, and hence the answer is clearly not zero. I am hence unable to find a way to deduce the remainder (without using a calculator to calculate $^{40}C_{12}$).

quasi · Answer

begin{align*}
binom{40}{12}
&=
frac
{(40)cdots (29)}
{(12)cdots (1)}
\[6pt]
&=
Bigl(frac{40}{12}{cdots}frac{36}{8}Bigr)
{,cdot,}
5
{,cdot,}
Bigl(frac{34}{6}{cdots}frac{29}{1}Bigr)
\[6pt]
&equiv
bigl(1{cdots}1bigr)
{,cdot,}
5
{,cdot,}
bigl(1{cdots}1bigr)
;(text{mod};7)&&text{[since each fraction in the above line}
\[0pt] 
&&&;text{reduces to $1$, mod $7$]}
\[4pt]
&equiv
5
;(text{mod};7)
\[4pt]
end{align*}

egreg · Answer

We could do the binomial expansion of $(x+1)^{40}$ in the seven-element field, by exploiting that $(x+1)^7=x^7+1$, so
$$
(x+1)^{40}=((x+1)^7)^5(x+1)^5=(x^7+1)^5(x+1)^5
$$
The power $x^{12}$ can only be obtained as $x^7$ from the first factor, where the coefficient is $binom{5}{1}=5$ and $x^5$ from the second, where the coefficient is $1$. Therefore
$$
binom{40}{12}equiv5pmod{7}
$$

Remainder when $^{40}C_{12}$ is divided by $7$.

2 Answers

Add your own answers!

Ask a Question