Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.