120k views
1 vote
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$?

User Ven Shine
by
8.1k points

1 Answer

4 votes

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

User Klaus Klein
by
8.1k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories