0
$\begingroup$

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?

  • 0
    Beware of the term "non-generator"! As I understand, by "non-generator" you mean any element that doesn't generate the whole group. There is a different notion of non-generators: an element is a non-generator if it can be excluded from any generating set of the group. As far as I understand, this second definition is often used by group theorists. In this sense non-generators always form a subgroup, which is called the [Frattini subgroup](http://en.wikipedia.org/wiki/Frattini_subgroup).2012-11-20

3 Answers 3

0

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.

1

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.

0

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

  • 0
    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?2012-11-20