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.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't suppose you would accept "systematic search" as an answer? $\endgroup$
    – Gerry Myerson
    Commented 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
    Commented Jul 21, 2015 at 0:34

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ @GerryMyerson I apologize, what exactly would Chebotarev's be applied to? $\endgroup$
    – Alex
    Commented 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
    Commented Jan 11, 2016 at 19:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .