4
$\begingroup$

I've been discussing a problem recently

Let $p, q$ be primes. If $x^q\equiv2\pmod p$ has no solution then $p\equiv1\pmod q.$

This is not a bi-equivalence (though it is "nearly" one): there are 811 primes below a million which are 1 mod $q=97,$ of which $x^q\equiv2\pmod p$ has no solution in 803 cases. (There are no cases below a million without a solution unless $p\equiv1\pmod{97}.$) There's nothing special about 97; other primes have similar behavior.

So:

  1. Is the statement true?
  2. Can the exceptional primes ($p\equiv1\pmod q$ but $x^q\equiv2\pmod p$ has a solution) be characterized?

1 Answers 1

6

The statement is true. To prove it, we use the standard result that if $a$ is not divisible by $p$, then the congruence $x^k \equiv a \pmod{p}$ has a solution iff $a^{(p-1)/\gcd(k,p-1)}\equiv 1\pmod{p}$.

In particular, let $k=q$, and suppose that $a=2$, or more generally any number not divisible by $p$. If $a^{(p-1)/\gcd(q,p-1)}\not\equiv 1\pmod{p}$, then by Fermat's Theorem we must have $\gcd(q,p-1)\gt 1$. Since $q$ is prime, it must divide $p-1$.

The second problem is more difficult. Suppose that $q$ divides $p-1$, and let $p-1=bq$. The congruence $x^q \equiv 2 \pmod{p}$ has a solution iff $2^b\equiv 1 \pmod{p}$.

One can reword this condition in terms of the order of $2$ modulo $p$. Further progress can be made in certain cases by using facts about quadratic residues.

However, a simple condition that is not essentially tautologous may be hard to find. Although technically $2^b\equiv 1\pmod{p}$ is an answer to the second problem, it is not really a satisfactory one.