Trying to prove that a set of non-generators element are not a subgroup of $\Bbb Z^*_p$ Let $p$ be a prime of the from $p= 2^k +1$ where $k$ is natural number.
The first question that was asked is to prove that the set of all generators of  $\Bbb Z^*_p$ is not a subgroup of  $\Bbb Z^*_p$.
By brute force and Euler's theorem, I saw that the possible sizes of the subgroup are $1$, $2$ and $4$ for $k =2$ and $p=5$.
Then I saw that $1$ always would not be a generator of any group, and because of that, the set of all the generators will not include $1$, which means that the identity element will not be included and therefore it could not be a subgroup.
I was trying to show that the set of all elements of $\Bbb Z^*_p$ that are not generators is a subgroup of $\Bbb Z^*_p$.
I can easily see that in $\Bbb Z^*_5$ it's true. I started checking it for $\Bbb Z^*_{17}$, but it's a lot of work. I saw that $2$ is not a generator and $3$ is a generator. It's a lot of work.
Is there any way to quickly check the list of the generators of  $\Bbb Z^*_{17}$ ?
How do I prove it?
 A: Since you are asking a quastion that only involves the abstract group structure (does the set of non-generators form a subgroup), you can use the fact that $\Bbb Z_p^*$ is abstractly just a cyclic group of order $p-1$ (this is why it has any generators at all), and therefore isomorphic to the additive group $\Bbb Z_{p-1}$.
Now in the additive group $\Bbb Z_n$ the generators are the elements that are (more precisely whose representatives in $\Bbb Z$ are) relatively prime to $n$. Whenver $n$ has at least two distinct prime divisors, those divisors define non-generating elements of $\Bbb Z_n$, but being relatively prime one can form $1$ as a linear combination of them (Bezout's lemma), so together they generate all of $\Bbb Z_n$, and the non-generating elements do not form a subgroup. On the other hand if $n$ has exactly $1$ prime factor $q$ (it is a prime power $q^k$ with $k>0$) then the non-generating elements are those (represented by a number) divisible by $q$, and these form a subgroup of $\Bbb Z_{q^k}$ of order $q^{k-1}$. So the non-generating elements of a cyclic group of order $n$ form a subgroup if and only if $n$ is a prime power (we exclude $n=1$, since the trivial group $\Bbb Z_1$ has no non-generating elements at all).
So for which primes $p$ does it happen that $p-1=q^k$ is a prime power? Well, one of $p,q$ must be even and therefore equal to $2$ and $p=2$ doesn't work since we saw the trivial group is not good. Therefore one must have $p=2^k+1$, and this implies (see the link) that $k$ itself is a power of $2$, and $p$ is a Fermat prime, which means it is one of $3,5,17,257,65537$, or maybe an as yet undiscovered, necessarily extremely large, Fermat prime.
A: Since $\Bbb Z_p$ is a finite field, its multiplicative group is cyclic, and is of order $p-1$. So, if you happened to find one generator, say $a$, then $a^m$ is a generator iff $\gcd(m,p-1)=1$.
In your case, where $p=2^k+1$, it only means that $m$ is odd. So, for $\Bbb Z^*_{17}$, if you showed that $3$ is a generator, then the list of generators is:
$$3, \ 3^3, \ 3^5,\ 3^7,\ 3^9, 3^{11}, 3^{13}, 3^{15} $$
That is, 
$$ 3, -7, 5, -6, -3, 7, -5, 6.$$
A: Let $G$ be a group and $S=\{x\in G\mid \langle x\rangle \ne G\}$.
For which $G$ is $S$ a subgroup of $G$?
If $G$ is trivial, then $S=\emptyset$ and is not a group.
If $G$ is not cyclic, then $S=G$ is a group.
If $G$ is cyclic of order $n=p^k$ for some prime $p$ with $k\ge 1$, then $S$ contains precisely the elements of order $\le p^{k-1}$, i.e. those elements with $x^{p^{k-1}}=1$. Since $G$ is abelian, we have $(xy)^{p^{k-1}}=x^{p^{k-1}}y^{p^{k-1}}=1$ if $x,y\in S$, hence $S$ is closed under the group operation. $S$ is also closed under taking inverses and nonempty (because $k\ge1$). Therefore $S$ is a group.
Remains the case that $G=\langle g\rangle$ is cyclic of order $n$, where $n$ is composite and not a prime power. Then we can write $n=ab$ with $a,b>1$ and $\gcd(a,b)=1$.
We have $g^a,g^b\in S$ because these have order $b$ and $a$, respectively.
From $\gcd(a,b)=1$ we find integers $u,v$ such that $ua+vb=1$.
Hence if $S$ were a group, then we'd have $g=g^{ua+vb}=(g^a)^u(g^b)^v\in S$, but of course $g\notin S$. Therefore $S$ is not a group.
In summary, $S$ is a group iff $G$ is cyclic of nontrivial prime power order or not cyclic.
