Simplified Chinese remainder theorem:-
The proof of RSA used the fact that if x = m mod p and x = m mod q, then x = m mod pq. More generally, knowing x mod p and x mod q determines x mod pq. For example, consider the table below:
Knowing the second and third entries in a column determines the top element. A formula for the solution to x = a mod 3, x = b mod 5 is
Find the solution x mod 45 to the equations x = 3 mod 5 and x = 1 mod 9.