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

Suppose $p$ is a prime number. I want to show that if integers $a,b$ are such that $p$ does not divide $b$ and for any $y$ which has the properties

(1) $y$ is not divisible by $p$ and not a primitive root mod $p$

(2) $a+by$ IS a primitive root mod $p$


$p=2^{2^n} +1$

I have proven that if $p=2^k +1$ then k must be a power of that narrows down the search a bit, but am stuck up to here. I have been trying to count possibilities but I am getting lost in this method.

share|cite|improve this question
you mean, any $y$ for (1) satisfies (2)? Or what is the conclusion of the hypothesis? – Berci Oct 27 '12 at 23:14
@Berci yes....if 1 is true, then 2 is true. Sorry for any confusion – Math2012pc Oct 27 '12 at 23:17
up vote 1 down vote accepted

Note that since $b$ has an inverse modulo $p$, the function $a+by$ is a one to one function modulo $p$.

Let $p=2m+1$. Suppose first that there is a quadratic non-residue of $p$ which is not a primitive root of $p$. Then there are at least $m+1$ numbers, distinct modulo $p$, that satisfy condition (1). For among the numbers satisfying condition (1) are the $m$ quadratic residues. Thus condition (2) cannot be satisfied for all of them: there are not enough primitive roots.

So every quadratic non-residue of $p$ is a primitive root. We show that if every quadratic non-residue of $p$ is a primitive root, then $p$ must be of the shape $2^{2^n}$.

In general a prime $p$ has $\varphi(\varphi(p))$ primitive roots. But $\varphi(p)=2m$. So if every quadratic non-residue is a primitive root, we must have that $\varphi(2m)=m$. This is only possible if $m$ is a power of $2$.

Finally, suppose that $2^w+1$ is an odd prime. Then $w$ must be a power of $2$. For suppose to the contrary that $w$ is divisible by an odd number $k\gt 1$. Then $w=kx$ for some $x$, and $2^{kx}+1=(2^x)^k+1$, which implies that $2^x+1$ is an proper divisor of $2^w+1$. (This last paragraph was for completeness only: the OP indicates that you had proved this part.)

share|cite|improve this answer
Is there any way to do this proof avoiding quadratic residues? – Math2012pc Oct 28 '12 at 4:30
@Math2012pc: Well, we could do the same thing without using the word. Let $g$ be a primitive root of $p$. Then the $m$ even powers of $g$ satisfy (1). So if there is an odd power of $g$ which is not a primitive root, then $\dots$ (exactly same argument, QR not mentioned explicitly). – André Nicolas Oct 28 '12 at 5:27

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.