Find all x ∈ $(Z/17Z)^×$ such that $⟨x⟩ = (Z/17Z)^×$ Find all $x ∈ (Z/17Z)^×$ such that $⟨x⟩ = (Z/17Z)^×$
So I know I'm trying to find all the generators for $(Z/17Z)^×$ and I know that since 17 is prime that the order of $(Z/17Z)^×$ is 16, is there a faster way to find all the generators or do I need to check 1 to 16?
Also since 17 is prime would the generators for $(Z/17Z)^×$ be the same as the generators for $(Z/17Z)$?
 A: Since $17$ is a prime of the form $2^k+1$, all the quadratic non-residues $\!\!\pmod{17}$ are generators of the multiplicative group and vice-versa. The least quadratic non-residue $\!\!\pmod{17}$ can be found by brutal inspection:
$$\left(\frac{2}{17}\right)=1,\quad \left(\frac{3}{17}\right)=\left(\frac{2}{3}\right)=-1$$
(we only need to check primes since the least non-quadratic residue is always a prime) Once we have that $3$ is a generator of the multiplicative group, all the other generators are given by the odd powers of 3, or, equivalently, by the set of quadratic residues multiplied by $3$. The quadratic residues are $1^2,2^2,\ldots,8^2$, so the generators are
$$ \{3\cdot 1^2, 3\cdot 2^2,\ldots,3\cdot 8^2\} = \{3, 5, 6, 7, 10, 11, 12, 14\}.$$
A: You can easily check that $(\mathbb Z/17\mathbb Z)^\times$ is generated by $3$. In other words$$\begin{array}{ccc}(\mathbb Z/16\mathbb Z,+)&\longrightarrow&(\mathbb Z/17\mathbb Z)^\times\\n&\mapsto&3^n\end{array}$$is a group homomorphism. So, which elements of $(\mathbb Z/16\mathbb Z,+)$ generate that group?
