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$?

Answer 1

If

N = a (mod 10)

N = b (mod 13)

gcd(10,13) = 1

then

N = 10 bx + 13 ay (mod 130)

Where

10x + 13y = 1

-> (10x + 13) (mod 2) = 1 (mod 2)

-> y (mod 2) = 1

y = -3, x = 4

-> N = 40b – 39a (mod 130)

 

It is given that  ra + sb should be non-negative:

 

N = 40b – 39a (mod 130)

N = 40b + (130 – 39)a (mod 130)

N = 40b + 91a (mod 130)

 

Therefore, N modulo 130, in terms of a and b is: N = 40b + 91a (mod 130).