Question: In the paragraph preceding the proof of Theorem we said that if a number is a multiple of the prime p and the prime q, then it is a multiple of pq. We will see how that is proved here.
(a) What equation in the integers does Euclid's extended GCD algorithm solve for us when m and n are relatively prime?
(b) Suppose that m and n are relatively prime and that k is a multiple of each one of them; that is, k = bm and k = cn for integers b and c. If you multiply both sides of the equation in part (a) by k, you get an equation expressing k as a sum of two products. By making appropriate substitutions in these terms, you can show that k is a multiple of mn. Do so. Does this justify the assertion we made in the paragraph preceding the proof of Theorem?
Theorem: The RSA procedure for encoding and decoding messages works correctly.