Note: Need typed solution only

14. [6 marks] Using the method shown in class which first uses the Euclidean algorithm and then goes back up the list of equations, express the god(35, 78) as a linear combination of 35 and 78. Show your work. 15. [2 marks] Based on your answer to the previous problem, can you find an inverse of 35 modulo 78? 16. [4 marks] (a) Find an inverse of 2 modulo 17 that is between 0 and 17. (b) Using the answer for part (a), solve the congruence 2x = 7 (mod 17). Find a solution for x that is between 0 and 17. 17. [4 marks] Suppose Alice has her public key PA and her private key SA, and Bob has his public key Ps and his private key Ss, as part of the RSA public key cryptosystem. Alice wants to send a message M to Bob so that he knows for sure that she sent it. Describe what Alice does and what Bob does