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

  • $\begingroup$ Unfortunately, your two assertions are not true in general: take $p=31$ for example. $\endgroup$ – 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
for y in [1..p-2] do
for s in [0..((p-1) div 2)] do
if a eq (base!2)^y then
    if flag and not (y mod 2 eq 0) then
        print "bad1:", p,y,s,Order(base!2);
    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;

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.