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?

  • 1
    Hint: If $G$ is a finite cyclic group, then the set of generators of $G$ can only be a subgroup if $|G| = 1$.2012-11-20
  • 0
    can you explain a bit more your answer ?2012-11-20
  • 0
    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.2012-11-20
  • 0
    Sometimes you write 'generators', sometimes '*non generators*' that form (or not) a subgroup.. I guess, the 'non generators' is the real exersize.2012-11-20
  • 0
    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-generators2012-11-20
  • 0
    Tobias - i read it again and i got it , its true. but how do i show that the set of all elements that are NOT-GENERATORS are a sub-group ?2012-11-20
  • 0
    For the non-generator part: The group in question is cclic of prime power order. So what is the condition for an element to not be a generator?2012-11-20
  • 0
    2 is not a generator of $\Bbb Z^*_17$. 2^1=2 2^2=4 2^3=8 2^4=16 2^5=15 2^6=13 2^7=9 2^8=1. and $\Bbb Z^*_17$ ={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}2012-11-20
  • 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
    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)=162012-11-20
  • 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