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$
  • $\begingroup$ I don't suppose you would accept "systematic search" as an answer? $\endgroup$ – Gerry Myerson Jul 21 '15 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 '15 at 0:34
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$
  • $\begingroup$ @GerryMyerson I apologize, what exactly would Chebotarev's be applied to? $\endgroup$ – Alex Jan 11 '16 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 '16 at 19:50

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.