Find out all the generators of the Cyclic group U17?

Question

Where U_n denotes the group of integers relatively prime to n under multiplication modulo n. I can find the number of generators of U_17 and also, can find all the generators by way of hit and trial method. Is there any other way which I may use to find out all its generators?

Answer 1

$17$ is a Fermat prime: $17=2^4+1$. I claim that if $p$ is a Fermat prime, then $a$ is a generator of $U_p$ iff $a$ is a quadratic non-residue of $p$.

Write $p=2^m+1$ with $m$ a positive integer (which itself must be a power of $2$). Then $U_p$ has $2^m$ elements, and is cyclic, so has $\phi(2^m) =2^{m-1}$ generators. A generator must be a quadratic non-residue, since the powers of a quadratic residue are all quadratic residues. There are exactly $\frac12(p-1)=2^{m-1}$ quadratic residues modulo $p$, so these are precisely the generators of $U_p$.