When N is divided by 10, the remainder is a. When N is divided by 11, the remainder is b. What is N modulo 110, in terms of a and b?
+287 Do you know the Chinese Remainder Theorem? You can apply it directly to this problem.
+26367 When n is divided by 10, the remainder is a.
When n is divided by 11, the remainder is b.
What is n modulo 110, in terms of a and b?
\(\begin{array}{|rcll|} \hline n &\equiv& {\color{red}a} \pmod{10} \quad \text{or} \quad n = a+10r,~ r\in\mathbb{Z} \\ n &\equiv& {\color{red}b} \pmod{11} \quad \text{or} \quad n = b+11s,~ s\in\mathbb{Z} \\ n &\equiv& {\color{red}x} \pmod{110} \quad |\quad 110 = 10*11\\ \hline \end{array}\)
\(\begin{array}{|lrcll|} \hline &n &=& a+10r \quad | \quad *11 \\ &\mathbf{11n} &=& \mathbf{11a+10*11r} \qquad (1) \\\\ &n &=& b+11s \quad | \quad *10 \\ &\mathbf{10n} &=& \mathbf{10b+10*11s} \qquad (2) \\ \hline (1)-(2): & 11n - 10n &=& 11a+10*11r - 10b - 10*11s \\ & n &=& 11a - 10b +10*11(r-s) \quad | \quad \text{let } r-s = t\\ & n &=& 11a - 10b +10*11t \quad |\quad 110 = 10*11\\ & \mathbf{n} &=& \mathbf{11a - 10b +110t} \qquad (3) \\ \hline \end{array}\)
\(\begin{array}{|rcll|} \hline \mathbf{n} &=& \mathbf{11a - 10b +110t} \qquad (3) \\ n &=& \underbrace{\color{red}11a-10b}_{=x} \pmod{110} \\ \hline \end{array}\)
\(n \pmod{110} \equiv 11a-10b \)
