(a) Prove that there is no primitive root modulo $2^n$ for any $n\geq3$, where $\bar{a}\in(\mathbb{Z}/2^n\mathbb{Z})^\ast$ is a primitive root modulo $2^n$ if the order of $\bar{a}$ is $\varphi(2^n)$ ($\varphi$ denotes the Euler phi-function).

(b) Prove that $(\mathbb{Z}/2^n\mathbb{Z})^\ast$ is generated by $5$ and $-1$, where $(\mathbb{Z}/2^n\mathbb{Z})^\ast$ is the multiplicative group of congruence classes $\bar{a}$ with $(a,n)=1$.

Motivation: This question is from Stein's Elementary Number Theory: Primes, Congruences, And Secrets (you can find a free legal copy of it here on the author's website), on p. 47, and it was asked in a previous homework of a number theory class I am currently taking.

Part (a) can be proved at least in two ways. The TA for the course gave an inductive argument that shows that $\forall \bar{a}\in(\mathbb{Z}/2^n\mathbb{Z})^\ast:(\bar{a})^{2^{n-2}}=\bar{1}$, from which the result follows immediately since $\varphi(2^n)=2^{n-1}$. This argument goes like this: The statement holds for $n=3$ since any nontrivial element has order $2$. Suppose the statement is true for $n=k\geq3$, that is, $\forall \bar{a}\in(\mathbb{Z}/2^n\mathbb{Z})^\ast: (\bar{a})^{2^{k-2}}=\bar{1}$. Let $a\in\mathbb{Z}$. Then $a^{2^{k-2}}=1+q2^{k}$ for some integer $q$. Squaring both sides gives $a^{2^{k-1}}=1+(q+q^22^{k-1})2^{k+1}$.

Another proof is outlined as a hint in the book, which goes like this (I guess): If for some $n\geq3$ there were a primitive root $\bar{p}$ modulo $2^n$, then $\bar{p}$ would be a generator of $(\mathbb{Z}/2^n\mathbb{Z})^\ast$, as by definition $|(\mathbb{Z}/2^n\mathbb{Z})^\ast|=\varphi(2^n)$. Then $\forall m\in\mathbb{Z},\exists k,l\in\mathbb{Z}:p^k=m+l2^n$, which, reducing modulo $2^3$, gives a contradiction as $(\mathbb{Z}/8\mathbb{Z})^\ast$ has no generators.

I am aware that this question has been asked around one year ago (see here), but I could not make use of the hints provided back then. Also I have a relatively good background in undergraduate algebra, so group theoretic proofs are welcomed as well (for the both parts if you can come up with a different proof for (a)). Finally I wanted to ask about the significance of this question. In particular what is the importance of $(\mathbb{Z}/2^n\mathbb{Z})^\ast$?

  • 2
    $\begingroup$ The point is that $\Bbb Z/2^n\Bbb Z^*$ is not cyclic, so by definition there is no primitive root, since such a thing is a generator of the group, but non-cyclic groups have more than one generator. $\endgroup$ – Adam Hughes Jan 30 '15 at 2:31

A simple proof for seeing there is no primitive root $\bmod 2^n$ is that the powers of $x$ are congruent to $1$ or $x\bmod 8$, so you are missing at least half of the elements.

Now lets prove all elements $\bmod 2^n$ are generated by $5$ and $-1$. There are $2^{n-1}$ congruence classes relatively prime to $2^n \bmod 2^n$. We will prove that the order of $5$ is $2^{n-2}$, if we do this we will have proved $2^ {n-2}$ generates all of the congruence classes that are $1$ or $5\bmod 8$.

The order of $5$ is the smallest positive integer $j$ so that $5^j\equiv 1 \bmod 2^n$ , in other words the smallest power $n$ so that $2^n|5^j-1$ . By the lifting the exponent lemma the largest power of $2$ dividing $2^k-1$ is the largest power of $2$ dividing $k$ plus the largest exponent of $2$ dividing $5-1=4$. Therefore the maximum exponent of $2$ dividing $2^k-2$ is the maximum exponent of $2$ dividing $k$ plus $2$. This tells us the order of $5$ is $2^{n-2}$, since if we want $2^j-1$ to be a multiple of $2^n$, $j$ must be a multiple of $2^{n-2}$.

Then the order of $5$ is $2^{n-2}$ so we can generate all of the residue classes congruent to $1$ or $5$. From here we can generate the other classes by multiplying by $-1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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