• Given n and m are coprime, show that there exist integer n' such that nn' mod m=1.
• The extended Euclid's algorithm is given below without proof, which may be useful in your proof.

(I'm too lazy to type out the algorithm again, so look at the image yourself)