# On Cubic Non-Residues Modulo a Prime [closed]

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$?

• 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

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{M}, \sqrt{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{M}, \sqrt{N}) \mapsto (\zeta^{\pm 1}, \zeta^a \sqrt{M}, \zeta^b \sqrt{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$.

• Thankyou. Does the same probability hold if the prime has to be between $M$ and $N$ if $N < 2M$ or $M < 2N$? – 1.. Jul 10 '13 at 19:07
• I am unfamiliar with the density theorem. Could you provide the details for $2/18$ step? – 1.. 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 E Speyer Jul 10 '13 at 19:28
• Yes, that's it. – David E 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 E 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.

• Removed the trivial part – 1.. Jul 10 '13 at 17:43
• what about for higher residues? – 1.. Jun 15 '16 at 7:44