# 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?

-
Hint: If $G$ is a finite cyclic group, then the set of generators of $G$ can only be a subgroup if $|G| = 1$. –  Tobias Kildetoft Nov 20 '12 at 10:46
can you explain a bit more your answer ? –  USer22999299 Nov 20 '12 at 10:48
Recall that there is a specific element of any group that has to be present in a subset in order for that subset to be a subgroup. Notice that this element will only be a generator in the case I mentioned. –  Tobias Kildetoft Nov 20 '12 at 10:52
Sometimes you write 'generators', sometimes 'non generators' that form (or not) a subgroup.. I guess, the 'non generators' is the real exersize. –  Berci Nov 20 '12 at 10:53
the exersize have 2 section , the first one is the one i solved and describe above . im looking for a hint for the second one for the non-generators –  USer22999299 Nov 20 '12 at 10:54

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.$$

-
some thing dose not add up for me , lets take p=17 p-1=16 3 is a generator of this group , m=16 gcd(16,16)=16 –  USer22999299 Nov 20 '12 at 10:52
Ok , so if im going on that way , the list of the generators and i can get from discovering that 3 is a generator and use gcd (m,p-1) is 3,10,5,11,14,7,12,6 that 8 generators , so i need to fine 1 more generators and from him to get another list of generators? and like that to find at least 12 generators? –  USer22999299 Nov 20 '12 at 11:11

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.

-

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.

-