MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity?

Given $M$ and $N$, is there a good way to find a prime $R$ such that $M$ is cubic non-residue modulo $R$ and $N$ is cubic residue modulo $R$?

Update after David Speyer's answer: Does the probability estimate hold good if $R$ is restricted to be between $M$ and $N$ and $M < 2N$ or $N < 2M$?

share|cite|improve this question

closed as unclear what you're asking by Felipe Voloch, Theo Johnson-Freyd, David White, Andrés E. Caicedo, Chris Godsil Jul 11 '13 at 1:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

What does $N$ have to do with it? – Steven Landsburg Jul 10 '13 at 16:43
Off topic. BTW $a_i = M^{-1}$ is a counterexample to (1). – Felipe Voloch Jul 10 '13 at 17:07
Do not make your question into a moving target. You already got two correct answers to two versions of your question. Accept one of them, try to learn what they mean and think about your problem some more. Then ask in a new question what you really want to ask. – Felipe Voloch Jul 10 '13 at 20:08
up vote 2 down vote accepted

Assuming that $M$, $N$, $M N$ and $M N^2$ are noncubes, for a random prime $p$, the probability that $p \equiv 1 \bmod 3$ and $M$ is a cube mod $p$ and $N$ is not a cube is $1/9$. Trying some random primes and checking as Igor Rivin describes is probably faster than trying to be clever.

Proof of the probability claim: The hypotheses imply that the splitting field of $\mathbb{Q}(\sqrt[3]{M}, \sqrt[3]{N})$ has Galois group $\mathbb{Z}/2 \ltimes (\mathbb{Z}/3)^2$. Here, writing $\zeta$ for a primitive cube root of unity, this group acts by $$\pm 1 \ltimes (a,b) \ : \ (\zeta, \sqrt[3]{M}, \sqrt[3]{N}) \mapsto (\zeta^{\pm 1}, \zeta^a \sqrt[3]{M}, \zeta^b \sqrt[3]{N}).$$

Let $\epsilon_p \ltimes (a_p,b_p)$ be the (conjugacy class of) the frobenius at $p$. Then $p \equiv 1 \bmod 3$ if and only if $\epsilon_p=1$; the numbers $M$ and $N$ are a cubic residue and non-residue respectively if and only if $a_p=0$ and $b_p \neq 0$. By the Cebatarov density theorem, we see that the proportion of primes which obey these properties is $2/18 = 1/9$.

share|cite|improve this answer
Thankyou. Does the same probability hold if the prime has to be between $M$ and $N$ if $N < 2M$ or $M < 2N$? – Turbo Jul 10 '13 at 19:07
I am unfamiliar with the density theorem. Could you provide the details for $2/18$ step? – Turbo Jul 10 '13 at 19:24
To your first question, I don't know. To the second question: Cebatarov density states that, for $C$ a conjugacy closed subset of a Galois group $G$, the probability that $Frob(p)$ will be in $C$ is $|C|/|G|$. In this case, the Galois group has $18$ elements and $2$ of them work. For the Cebatarov density theorem, see an "advanced" textbook in algebraic number theory, such as Janusz (Algebraic Number Fields) or Neukirch (Algebraic Number Theory). – David Speyer Jul 10 '13 at 19:28
Yes, that's it. – David Speyer Jul 10 '13 at 19:30
Sorry, my opinion is that I don't know. If you held $M$ and $N$ fixed and looked at primes between $T$ and $2T$, you'd be right, but I don't know enough about the error bounds in Cebatarov to know what happens when you link the endpoints of your interval to the cubic extension. But there are plenty of experts here! – David Speyer Jul 10 '13 at 19:33

I am a bit confused by the connection between the first question and the numbered questions. Presumably if $R\equiv 2 \mod 3,$ then everything is a cubic residue, while if $R\equiv 1 \mod 3,$ then $x$ is a residue iff $x^{(R-1)/3} \equiv 1 \mod R.$ This test is quite efficient. I assume (but haven't bothered to check) that this test will answer the numbered questions.

share|cite|improve this answer
Removed the trivial part – Turbo Jul 10 '13 at 17:43
Thankyou this solves most of my initial questions. – Turbo Jul 10 '13 at 17:49
what about for higher residues? – Turbo Jun 15 at 7:44

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