# If $\binom{99}{19}\equiv 19\pmod{25}$ and $\binom{99}{19}\equiv 2\pmod {4}$, how can we deduce that $\binom{99}{19}\equiv 94\pmod{100}$?

Problem: If $\binom{99}{19}\equiv 19\pmod{25}$ and $\binom{99}{19}\equiv 2\pmod {4}$, how can we deduce that $\binom{99}{19}\equiv 94\pmod{100}$?

My Attempt: The actual problem asks one to find $\binom{99}{19}\pmod{1000},$ but I am first trying to find the last two digits of $N=\binom{99}{19}.$ So I broke the $100$ into $25$ and $4$ since they are relatively prime and obtained the following congruences: $$\binom{99}{19}\equiv 19\pmod{25}$$ and $$\binom{99}{19}\equiv 2\pmod {4}.$$ But the solution,states that the lst two digits of $N$ are $94.$ I am unable to use the aforementioned facts to conclude that $N\equiv 94\pmod{100}.$ Please help.

There are four numbers less than $100$ that are congruent to $19$ modulo $25$. They are $19, 44, 69$ and $94$. Of those, only one is congruent to $2$ modulo $4$.
• @Supermario Yes, there is. We want $19+25n \equiv 2\pmod 4$, which may be solved for $n$, giving $3$. – Arthur Nov 19 '16 at 14:55
There is a formula for solving a system of congruences with coprime moduli, which everyone should know: if $ua+vb=1$ is a Bézout's relation between the coprime integers $a$ and $b$, then a solution of the system $\;\begin{cases}x\equiv\alpha\mod a, \\ x\equiv \beta\mod b, \end{cases}$ is given by $$x\equiv \beta\cdot ua+\alpha\cdot vb\mod ab.$$ In the present case, a Bézout's relation is $25-6\cdot 4=1$, hence the solutions are $$x\equiv 2\cdot 25- 19\cdot 24=-406\equiv -6\equiv 94\mod 100.$$
By CRT: $\ {\rm mod}\ 4\!:\ 2 \equiv x \equiv 19\!+\!25j \equiv -1\!+\!j\,$ $\Rightarrow\,$ $j\equiv \color{#c00}3,\$ so $\ x = 19\!+\!25(\underbrace{\color{#c00}3\!+\!4k}_{\large j})=94\!+\!100k$ Remark $\$ The above method can be recast as a formula, see Easy CRT.