Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

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

share|cite|improve this answer
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

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.