3
$\begingroup$

Reasonable exceptions allowed on $q$. Example solution: $n=2$.

Suppose $q$ is odd. Let $p$ be so $pq\equiv -1$ (mod 8). Then $q\neq$ 2nd power (mod $p$) is the same as $\left(\frac{q}{p}\right)=-1$. We can obtain this from quadratic reciprocity law: $$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)\equiv(-1)^{\frac{p-1}{2}\frac{q-1}{2}}=(-1)^{\frac{pq+1}{4}}(-1)^{\frac{p+q}{2}}=(-1)^{\frac{p+q}{2}}$$ where the last equality holds since $pq\equiv -1$ (mod 8) $\Rightarrow$ $\frac{pq+1}{4}\equiv 0$ (mod 2).

Then the condition $\left(\frac{q}{p}\right)=-1$ is equivalent to $\left(\frac{p}{q}\right)=-(-1)^{\frac{p+q}{2}} = -(-1)^{\frac{-q^{-1}+q}{2}}$, where the $q^{-1}$ is taken (mod 8). In particular, for any $p\equiv -(-1)^{\frac{q-q^{-1}}{2}}$ (mod $q$) and $pq\equiv -1$ (mod 8), we will have $q\neq$ 2nd power (mod $p$).


I was trying to repeat this argument for higher powers. I can find conditions so that, say, $n$-th residue symbol will equal to 1 (for certain $n$ anyways). However, that does not guarantee that $q$ will not be a $n$-th power (mod $p$).

Any thoughts appreciated.

$\endgroup$
2
  • $\begingroup$ I don't suppose you would accept "systematic search" as an answer? $\endgroup$ Jul 21, 2015 at 0:24
  • $\begingroup$ Well, that would work if there were a way to guarantee it would always return an answer. Not an optimal solution obviously. $\endgroup$
    – Alex
    Jul 21, 2015 at 0:34

1 Answer 1

3
$\begingroup$

This is an elaboration on Gerry Myerson's comment. By Chebotarev's (or Frobenius') density theorem, there is a positive proportion of primes for which $x^n-q$ has no linear factor (assuming $q$ is such that this is irreducible over $\mathbb{Q}).$ In fact, this proportion is not too hard to estimate, but this will lead us too far afield. So, systematic search succeeds, and usually pretty quickly (for each $p$ use Berlekamp's algorithm, or some variant thereof, to factor).

$\endgroup$
2
  • $\begingroup$ @GerryMyerson I apologize, what exactly would Chebotarev's be applied to? $\endgroup$
    – Alex
    Jan 11, 2016 at 18:58
  • $\begingroup$ Chebotarev is applied to the polynomial $x^n-q.$ Mod most primes this has no linear factor, so $q$ is not an $n$-th power. $\endgroup$
    – Igor Rivin
    Jan 11, 2016 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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