# Tough Divisibility Problem

When the five digit number $2A13B$ is divided by $19$, the remainder is $12$. Determine the remainder of $3A21B$ when divided by $19$.

$$2A13B \equiv 12 \pmod{19}$$

$$20000 + 1000A + 100 + 30 + B \equiv 12 \pmod{19}$$

$$5 + 12A + 5 + 11 + B \equiv 12 \pmod{19}$$

$$21+ 12A+ B \equiv 12 \pmod{19}$$

$$12A+ B + 9 \equiv 0 \pmod{19}$$

This is where I'm stuck.

• Can you reduce $3000 + 1000A + 210 + B$ modulo 19 in the same way? Sep 1 '18 at 15:34

Hint: $3A21B = 2A13B + 10000 + 80$

• Yes, everybody seems to have missed that! Sep 1 '18 at 18:40
• This is by far the best answer, and arguably the only reasonable one to the problem. All the others are making it ridiculously overcomplicated. Sep 2 '18 at 1:25

You have some errors, which I will fix: \begin{align}\overline{2A13B}=20000 + 1000A + 100 + 30 + B &\equiv 12 \pmod{19} \Rightarrow \\ (19\cdot 1052+12)+(19\cdot 52+12)A+(19\cdot 5+5)+(19\cdot 1+11)+B&\equiv 12 \pmod{19} \Rightarrow \\ 12+12A+5+11+B&\equiv 12 \pmod{19} \Rightarrow \\ 12A+19\cdot 1+9+B&\equiv 12 \pmod{19} \Rightarrow \\ 12A+9+B&\equiv 12 \pmod{19} \Rightarrow \\ 12A+B&\equiv 3\pmod{19}.\end{align} Since $0\le A,B\le 9$, then: $(A,B)=(0,3),(3,5),(6,7),(9,9)$. Similarly: \begin{align}\overline{3A21B}=30000 + 1000A + 200 + 10 + B &\equiv x \pmod{19} \Rightarrow \\ (19\cdot 1578+18)+(19\cdot 52+12)A+(19\cdot 10+10)+10+B&\equiv x \pmod{19} \Rightarrow \\ 18+12A+10+10+B&\equiv x \pmod{19} \Rightarrow \\ 12A+19\cdot 2+B&\equiv x \pmod{19} \Rightarrow \\ 12A+B&\equiv x \pmod{19}.\end{align} So, $x=3$.

For example, take $\overline{2A13B}=20133\equiv 12 \pmod{19}$ and $\overline{3A21B}=30213\equiv 3\pmod{19}$.

Hint : $B \equiv -12A-9 \pmod{19}$. Next, in $3A21B \pmod{19}$ you can replace $B$ by the RHS expression for it.

\begin{align}30\,000+1\,000A+200+10+B\equiv x\pmod{19}&\iff-1+12A+10+10+B\equiv x\pmod{19}\\&\iff12A+B\equiv x\pmod{19}.\end{align}Therefore, since $12A+B+9\equiv0\pmod{19}$, take $x=10$.

• I didn't get your answer properly. On the condition that $12A+B\equiv9\pmod{19}$, we get $12A + B \equiv x \pmod{19} \implies 12A+B\equiv9\pmod{19}$. Does it denote the right answer is $9$. You had also written "take $x = 10$", why?
– Busi
Sep 1 '18 at 17:11
• @Busi There was a typo in my answer, which I have already edited. I wrote $12A+B\equiv9\pmod{19}$ where I should have written $12A+B+9\equiv0\pmod{19}$. Thank you. Sep 1 '18 at 17:16