# Primitive roots modulo a prime number

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$

Then,

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

I have proven that if $p=2^k +1$ then k must be a power of two....so 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.

-
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

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

-
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