-1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Is there a methodical way to obtain this result? $\endgroup$ – model_checker Nov 19 '16 at 14:52
  • $\begingroup$ @Supermario Yes, there is. We want $19+25n \equiv 2\pmod 4$, which may be solved for $n$, giving $3$. $\endgroup$ – Arthur Nov 19 '16 at 14:55
  • $\begingroup$ @Supermario Yes, we can use CRT = Chinese Remainder Theorem - see my answer. $\endgroup$ – Bill Dubuque Nov 19 '16 at 16:52
2
$\begingroup$

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.$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

x is congruent to -6 modulo 4 and modulo 25. That is x+6=4k=25n=100(n/4). n is divisible by 4 because 25n is divisible by 4 and 25 isn't. x is congruent to -6 modulo 100.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.