(i) Let $p$ be an odd prime and $k$ a strictly positive integer. Prove that the multiplicative group of relatively prime residue classes modulo $p^{k}$ is cyclic.

[You may assume that the result is true for $k=1$.]

(ii) Let $n=p_{1} p_{2} \ldots p_{r}$, where $r \geqslant 2$ and $p_{1}, p_{2}, \ldots, p_{r}$ are distinct odd primes. Let $B$ denote the set of all integers which are relatively prime to $n$. We recall that $n$ is said to be an Euler pseudo-prime to the base $b \in B$ if

$$b^{(n-1) / 2} \equiv\left(\frac{b}{n}\right) \bmod n .$$

If $n$ is an Euler pseudo-prime to the base $b_{1} \in B$, but is not an Euler pseudo-prime to the base $b_{2} \in B$, prove that $n$ is not an Euler pseudo-prime to the base $b_{1} b_{2}$. Let $p$ denote any of the primes $p_{1}, p_{2}, \ldots, p_{r}$. Prove that there exists a $b \in B$ such that

$$\left(\frac{b}{p}\right)=-1 \quad \text { and } \quad b \equiv 1 \bmod n / p$$

and deduce that $n$ is not an Euler pseudo-prime to this base $b$. Hence prove that $n$ is not an Euler pseudo-prime to the base $b$ for at least half of all the relatively prime residue classes $b \bmod n$.