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:
![](https://book.transtutors.com/qimg/4372700f-4b64-428d-b5e9-4790c67199af.png)
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
![](https://book.transtutors.com/qimg/d179fc2c-f14c-4eb2-b171-1406a53e2f93.png)
Find the solution x mod 45 to the equations x = 3 mod 5 and x = 1 mod 9.