(i) Describe Euclid's algorithm.

Find, in the RSA algorithm, the deciphering key corresponding to the enciphering key 7,527 .

(ii) Explain what is meant by a primitive root modulo an odd prime $p$.

Show that, if $g$ is a primitive root modulo $p$, then all primitive roots modulo $p$ are given by $g^{m}$, where $1 \leqslant m<p$ and $(m, p-1)=1$.

Verify, by Euler's criterion, that 3 is a primitive root modulo 17 . Hence find all primitive roots modulo 17 .