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`