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?

(The answer should be in the form of ra + sb, where r and s are replaced by non-negative integers less than 130)

Answer 1

well \(N\equiv a\pmod{10}\) suggests \(N=10m+a\) for some \(m\in\mathbb{Z}\) while \(N\equiv b\pmod{13}\) suggests \(N=13n+b\) for some \(n\in\mathbb{Z}\)

we also know that since \(\gcd(10,13)=1\) that \(N\equiv ab\pmod{10\cdot13}\) ergo \(N=ab+130p\) and we get:$$(ab+130p)-(13n+b)=b(a-1)+13(10p-n)=0$$whereas \((ab+130p)-(10m+a)=a(b-1)+10(13p-m)=0\)

so we know$$b(a-1)\equiv0\pmod{13}\\ba\equiv b\pmod{13}\\\quad\implies a\equiv1\pmod{13}$$and similarly$$a(b-1)\equiv0\pmod{10}\\ab\equiv a\pmod{10}\\\quad\implies b\equiv 1\pmod{10}$$

Answer 2

hmm

Answer 3

Thanks

Answer 4

wait a second this should be easier to solve... just using CRT...