Question

When N is divided by 10, the remainder is a. When N is divided by 13, the remainder is b. What is N modulo 130, in terms of a and b? (Your answer should be in the form ra+sb, where r and s are replaced by nonnegative integers less than 130.)

Answer 1

$\begin{cases}N\equiv a\mod10\\N\equiv b\mod13\end{cases}$

means there are integers $n_1,n_2$ such that

$\begin{cases}N=10n_1+a\\N=13n_2+b\end{cases}$

Multiplying the first equation by 13 and the second by 10 gives

$\begin{cases}13N=130n_1+13a\\10N=130n_2+10b\end{cases}$

Adding the two equations gives

$23N=130(n_1+n_2)+13a+10b$
$\implies23N\equiv13a+10b\mod130$

and since $(23,130)=1$ (they are coprime), it follows that

$N\equiv23^{-1}(13a+10b)\mod130$

where $23^{-1}$ is the modular multiplicative inverse of 23 (as opposed to 1/23) modulo 130. By the Euclidean algorithm we have

$130=23(5)+15$
$23=15(1)+8$
$15=8(1)+7$
$8=7(1)+1$
$\implies1=8-1(7)$
$\implies1=2(8)-1(15)$
$\implies1=2(23)-3(15)$
$\implies1=17(23)-3(130)$
$\implies17(23)\equiv1\mod130$

which means 17 is the inverse of 23 mod 130, so

$N\equiv17(13a+10b)\mod130$
$\implies N\equiv221a+170b\mod130$
$\implies N\equiv91a+40b\mod130$