# Solve a set of congruences

John is thinking of a number $$n$$. He's willing to tell us that the number is close to $$10000$$ and in binary system it ends on $$101$$. In $$7$$ and $$11$$ system it ends on digit $$2$$ and the last two digits in the ternary numeral system are $$21$$. What is this number he is thinking of? I understand we need to create a set of congruences and solve it.

I have tried the following: Two of them are $$x = 2, (mod 7)$$ and $$x = 2 (mod 11)$$. That should be correct. The first one is $$x = 5 (mod 8)$$ and the last is $$x = 7 (mod 9)$$. I can see for this first one that $$101$$ is $$5$$ when converted to decimal system, but where do we get modulo $$8$$, from $$2^3$$? But why? Thank you for any clarification.

• For the same reason that a decimal number that ends in 65 is congruent to 65 modulus 100 as well as being congruenent to 5 modulus 10. Jan 18, 2019 at 12:42

If your binary and ternary numerals are $$\ b_nb_{n-1}\dots b_2b_1b_0\$$ and $$\ t_mt_{m-1}\dots t_1t_0\$$, respectively, with $$b_2=1, b_1=0, b_0=1, t_1=2\$$ and $$\ t_0=1\$$, then, by definition, the numbers they represent are: $$\begin{eqnarray} B &=& b_n\,2^n + b_{n-1}\,2^{n-1} + \dots + b_3\,2^3 + 1\times2^2 + 0\times2 + 1\\ &=& 2^3\,\left(\,b_n\,2^{n-3}+b_{n-1}\,2^{n-4} + \dots + b_3\, \right) + 5\ \ \ \mbox{and}\\ T &=& t_m\,3^m + t_{m-1}\,3^{m-1} + \dots + t_2\,3^2 + 2\times3 + 1\\ &=& 3^2\,\left(\,t_m\,3^{m-2} + t_{m-1}\,3^{m-3} + \dots + t_2\,\right) + 7\ , \end{eqnarray}$$
from which you should be able to see that if you subtract $$\ 5\$$ from $$\ B\$$ the result is divisible by $$\ 8\$$, and if you subtract $$\ 7\$$ from $$\ T\$$ the result is divisible by 9.