dividing binomial coefficient by a number

Question

so, the question is as follows :

find the remainder when $${}^{119}C_{33}$$ is divided by $5$

my approach: well, I don't know about any method except for writing $${}^{119}C_{33} = 264987608114625679810381761543$$ now it is easy to see that the remainder on dividing this by $5$ should be $3$. so,is there a better method to get to the solution? kindly help me out.

note: I saw a similar variation of this question at MSE but it had a special case where in ${}^{n}C_{k} , n! = (n-k)!$ hence I hope this qualifies as a new question.

Answer 1

I agree with Robert Israel's recommendation in the comments to use Lucas's theorem. Here's the computation: \begin{align*} 119_{10} &= 434_5,\\ 33_{10} &= 113_5. \end{align*} Then Lucas tells us that $$\binom{119}{33}\equiv\binom{4}{1}\binom{3}{1}\binom{4}{3}\equiv 4\cdot 3\cdot 4 \equiv 3\pmod{5}.$$

Answer 2

For $m\in \Bbb N$, let $$ f(m)=\frac{m!}{5^{\lfloor m/5\rfloor}\lfloor m/5\rfloor!}$$ be the product of all numbers $1,\ldots, m$ that are not multiples of $5$. The remainders $\bmod 5$ of the factors are periodic $$1,2,-2,-1,*,1,2,-2,-1,*,\ldots,$$ hence so is $f(m)\bmod 5$ (with period length $10$): $$\tag11,2,1,-1,-1,-1,-2,-1,1,1, \ldots $$

Now from $$ {119\choose 33}=\frac{119!}{33!86!}=\frac{119!/5^{23}}{33!/5^6\cdot 86!/5^{17}}=\frac{f(119)}{f(33)f(86)}\cdot\frac{23!}{6!17!}$$ and $$\frac{23!}{6!17!}=\frac{23!/5^{4}}{6!/5^1\cdot 17!/5^{3}}=\frac{f(23)}{f(6)f(17)}\cdot\frac{4!}{1!3!} $$ we see that we need only find a few values of $f\bmod 5$ by lookup from $(1)$, and ${4\choose 3}\bmod 5$.