3
$\begingroup$

Like the question says, what is the smallest integer which is $1\mod8$, $2\mod25$ and $7\mod11$?

I've worked out a number which is $1\mod8$ and $2\mod25$ by using that $25 - 3 \times 8 = 1$ so the number is $25 - 2\times 3 \times 8 = -23$ which also equals $177\mod200$. But now I'm stuck, as I can't think of integers $a$ and $b$ such that $11a + 200b = 1$?

  • 3
    Sounds like$a$case for the [Chinese remainder theorem@Mathworld](http://mathworld.wolfram.com/ChineseRemainderTheorem.html).2012-06-05

2 Answers 2

2

Note that $200\equiv 2\pmod{11}$, and $-23\equiv-1\pmod{11}$. Thus, $-23+4\cdot200\equiv-1+4\cdot2=7\pmod{11}\;,$ and it follows that $800-23=777$ is a solution to your system of congruences. All you need do now is decide whether it’s the smallest positive solution, and if not, reduce it appropriately.

0

Below is a complete algorithmic solution (i.e. nothing is pulled out of a hat) using Easy CRT. Generally this method is faster than hoping for lucky guesses (it took me $20$ seconds mentally).

If $\rm\:\ x \equiv \color{brown}2\ mod\ 25,\ \color{green}7\ mod\ 11, \ \color{red}1\ mod\ 8,\ $ then applying Easy CRT we quickly compute

$\rm x \equiv \color{brown}2 + 25\:\!\left(\!\frac{\color{green}7\!-\!\color{brown}2}{25}\ mod\ 11\!\right)\equiv -\color{blue}{48}\:\ (mod\ 25\,\!\cdot\! 11)\ \ \ by\ \ \ mod\ 11\!:\, \frac{5}{25}\equiv \frac{1}5\equiv\frac{-10}5\equiv -2 $

$\rm x\equiv\:\! -\color{blue}{48} + 25\,\!\cdot\! 11\:\!\left(\!\frac{\color{red}1\!+\!\color{blue}{48}}{25\,\!\cdot\! 11}\ mod\ 8\!\right)\equiv 777\:\ (mod\ 25\,\!\cdot\!11\!\cdot\! 8)\ \ \ by\ \ \ mod\ 8\!:\, \frac{49}{3\,\!\cdot\! 1}\equiv \frac{9}3\equiv 3\ \ $