# Primes having 2 as a primitive root

Let $$p$$ a prime and $$a$$ a quadratic residue of $$p$$. If there exists some positive integer $$y$$ satisfying $$a\equiv2^y \pmod{p}$$, prove or disprove that $$2$$ is a primitive root of $$p$$. My progress is that if 2 is not a primitive root then the set $$\{2^0, 2^1, ..., 2^\frac{p-1}{2}\}$$ is exactly the set of quadratic residues. Also $$ord_p(2)=\frac{p-1}{2}$$ or $$p-1$$.

• Unfortunately, your two assertions are not true in general: take $p=31$ for example. – Greg Martin Jun 13 '19 at 7:24

As the comments point out whether $$2$$ is a primitive root of $$p$$ depends on $$p$$, $$a$$ and $$y$$, this answer is trying to figure out WHEN $$2$$ is a primitive root of $$p$$.

As $$a\equiv 2^y \pmod{p},$$ where $$a$$ is a quadratic residue of $$p$$ and $$p$$ is a prime number, it is clear that

Proposition 1: $$2$$ is NOT a primitive root of $$p$$ if $$p=2$$ or $$y=1$$.

In the following, assume that $$p>2$$ is an odd prime number and $$2\le y \le p-2$$. We assert that

Proposition: $$2$$ is NOT a primitive root of $$p>2$$ if $$y$$ is odd.

Proof: Let $$g$$ be a primitive root of $$p$$. Then there exist integers $$1\le k \le p-1,0\le s\le \frac{p-1}{2}$$ such that $$2=g^k,a=g^{2s}.$$ Then it follows from $$a=2^y$$ that $$g^{2s}=g^{ky}$$. Note that the order of $$g$$ is $$p-1$$. So we have $$ky\equiv 2s \pmod{p-1}.$$ Since $$2s$$ and $$p-1$$ are even, $$ky$$ must be even too. If $$y$$ is odd, then $$k$$ must be even, i.e., $$2\mid k$$. Then $$\mathrm{Ord}(2)=\frac{p-1}{\gcd(p-1,k)}=\frac{p-1}{2}\cdot \frac{1}{\gcd(\frac{p-1}{2},\frac{k}{2})}\le \frac{p-1}{2}.$$ Therefore, $$2$$ can be a primitive root of $$p$$. QED.

However, it is not a sufficient condition. After observing the result of the magma script below, a conjecture is obtained.

Conjecture 1: $$2$$ is a primitive root of $$p$$ if $$y$$ is even and $$P(p)$$, where $$P(p)$$ is a proposition of $$p$$ only.

We know whether $$2$$ is a primitive root of $$p$$ is completely determinated by $$p$$. But so far as we know, it is hard to give a YES or NO when only given $$p$$. So The proposition $$P$$ in Conjecture 1 is expected to be much more simple.

gp:={}; bp:={};
for p in [i: i in [3..200] | IsPrime(i)] do
base:=ResidueClassRing(p);
g:=PrimitiveRoot(p);
for y in [1..p-2] do
for s in [0..((p-1) div 2)] do
a:=g^(2*s);
if a eq (base!2)^y then
flag:=IsPrimitive(base!2);
if flag and not (y mod 2 eq 0) then
end if;
if flag and (y mod 2 eq 0) then
gp join:= {p};
end if;
if not flag and (y mod 2 eq 0) then
bp join:= {p};
end if;
end if;

end for;
end for;
end for;

print bp meet gp;