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).
