i) Use the Euclidean Division Algorithm to show that 31 and 207 are relatively prime, and hence find integers x and y such that 1= 207x + 31y. Hence find the multiplicative inverse of 31 mod 207. Check your answer.

ii) Using the Euclidean Algorithm find the decipherment key, d, when p =53 and q=61 and the encryption exponent, e, is 29. (i.e. find the multiplicative inverse of 29 mod (p-1)(q-1)). Check your answer.