The binomial coefficient $\left(\begin{array}{l}99 \\ 19\end{array}\right)$ is $ 107,196,674,080,761,936, x y z $ , Find $x y z$

Question

The binomial coefficient $\left(\begin{array}{l}99 \\ 19\end{array}\right)$ is a 21 -digit number: $ 107,196,674,080,761,936, x y z $ Find the three-digit number $x y z$

I showed that $\left(\begin{array}{l}99 \\ 19\end{array}\right) \equiv 2(\bmod 4)$

and $\left(\begin{array}{l}99 \\ 19\end{array}\right) \equiv 19(\bmod 25)$

Now how to combine them to find last two digit (y and z)??

because we can only combine when $a \equiv b(\bmod n)$

$a \equiv b(\bmod m)$ then if (n,m)=1 then

$a \equiv b(\bmod mn)$ but here we have different b's ...

and also can someone tell some easier method to find $\left(\begin{array}{l}99 \\ 19\end{array}\right) \equiv 2(\bmod 4)$

and $\left(\begin{array}{l}99 \\ 19\end{array}\right) \equiv 19(\bmod 25)$ my approach takes me too long, so i want to see some easier method...

Answer 1

Since $99 \equiv -1 \pmod {25}$, we have $99 \cdot 98 \cdots 81 \equiv (-1)^{19}19! \pmod {25}$. What we would like to do is to simply divide by $19!$ and be done, but you'll notice that $19! \equiv 0 \pmod{25}$ because of the multiples of $5$. So instead, we treat the multiples of $5$ separately and this gives

$$ \binom{99}{19} \equiv (-1)^{19 - 3} \frac{95 \cdot 90 \cdot 85}{15 \cdot 10 \cdot 5} \pmod{25}.$$

Now we simplify:

$$ (-1)^{19 - 3} \frac{95 \cdot 90 \cdot 85}{15 \cdot 10 \cdot 5} = 3 \cdot 17 \cdot 19 = 51 \cdot 19 \equiv 19 \pmod{25}.$$

Answer 2

There are general algorithms for this (look up Chinese Remainder Theorem), but in this simple case, you can just start with 19 and add multiples of 25 until you get to a number that is congruent to 2 (mod 4). There has to be a solution before you get to 100, so it won't take long.

Answer 3

Use chinese remainder theorem. Let $a$ be the last two digit, then $a=19+25b$. Trying $b=1,2,..$ that suits the $\pmod{4}$ condition gives $a=94$.

Basically, the chinese remainder theorem states that if $ (25,4)=1$, there is exactly one solution $\pmod{100}$.The CRT, doesn't give the solution but rather assures that the solution exits.

If you're trying to find $\pmod{1000}$, you would do $a=x+125b$, and try to plug for $b=1,2,..$ until the $\pmod{8}$ condition is satisfied. Basically you choose the biggest modulo, because $a$ reaches $1000$ fast with that.

Answer 4

Here's a far less obvious solution than computing $\dbinom{99}{19}$ in $\pmod{8}$ and $\pmod{125}$, but I'll leave it here just in case anyone wants to see it.

The keys to this solution are that determining $\dbinom{99}{19} \pmod{1001}$ is enough to determine the last $3$ digits, and that $1001 = 7 \cdot 11 \cdot 13$.

To compute an integer $\pmod{1001}$ given all the digits, we need to group the digits in $3$'s and take the alternating sum, i.e. $$\dbinom{99}{19} \equiv 107-196+674-080+761-936+xyz \equiv xyz+330 \pmod{1001}.$$

Next, we use Lucas's Theorem to compute $\dbinom{99}{19}$ modulo $7,11,13$.

Since $99 = 2 \cdot 7^2 + 0 \cdot 7+1$ and $19 = 2\cdot 7 + 5$, we have $$\dbinom{99}{19} \equiv \dbinom{2}{0} \dbinom{0}{2}\dbinom{1}{5} \equiv 1 \cdot 0 \cdot 0 \equiv 0 \pmod{7}.$$

Since $99 = 9 \cdot 11+0$ and $19 = 1\cdot 11 + 8$, we have $$\dbinom{99}{19} \equiv \dbinom{9}{1}\dbinom{0}{8} \equiv 9 \cdot 0 \equiv 0 \pmod{11}.$$

Since $99 = 7 \cdot 13+8$ and $19 = 1\cdot 13 + 6$, we have $$\dbinom{99}{19} \equiv \dbinom{7}{1}\dbinom{8}{6} \equiv 7 \cdot 28 \equiv 7 \cdot 2 \equiv 14 \equiv 1 \pmod{13}.$$

The first two conditions tell us that $\dbinom{99}{19} \equiv 0 \pmod{77}$.

To combine this with the third condition, note that $\dbinom{99}{19} \equiv 0 \equiv -77 \pmod{77}$ and $\dbinom{99}{19} \equiv 1 \equiv -77 \pmod{13}$. So $\dbinom{99}{19} \equiv -77 \equiv 924 \pmod{1001}$.

Therefore, $xyz+330 \equiv \dbinom{99}{19} \equiv 924 \pmod{1001}$, and thus, $xyz \equiv 594 \pmod{1001}$. So, $xyz = 594$.