Exercise 3.

Let p, q two different prime integers. Let a be another integer, not necessarily prime and such that a $\neq$ 0 and neither p nor q divides a.

1. Explain briefly why there exists two integers s, t such that sp + tq = 1 holds. How can we compute them?
2. Explain briefly why a has an inverse b modulo p and an inverse c modulo q. How can we compute them?
3. Explain briefly why a has an inverse d modulo pq.
4. Assume that s, t, b, c have been computed. Explain briefly at least two ways to compute d.
5. Which way do you feel to be the best one?

Answer 4