(a) Determine the number of incongruent residues that have an inverse modulo 310.
(b) Show that the probability of a given residue $a \pmod {p^n}$ has a multiplicative inverse is $1 - \frac{1}{p}$ where $p$ is prime.
(a) By Proposition (3.21), a residue $a$ has an inverse modulo $n$ if and only if $\gcd(a,n)=1$
The number of incongruent residues modulo 310 which are coprime to 310 is
$$ \phi(310) = \phi(2 \times 5 \times 31) = \phi(2) \times \phi(5) \times \phi(31) = (2-1)(5-1)(31-1) = 120 $$
So there are 120 incongruent residues that have an inverse modulo 310.
(b) The probability of a given residue $a \pmod {p^n}$ has a multiplicative inverse is the same as the probability of it being coprime to $p^n$, which is
$$ \frac{\phi(p^n)}{p^n} = \frac{p^{n-1}(p-1)}{p^n} = \frac{p-1}{p} = 1 - \frac{1}{p}$$