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