2
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What does $N$ have to do with it? $\endgroup$
    – Steven Landsburg
    Commented Jul 10, 2013 at 16:43
  • 1
    $\begingroup$ Off topic. BTW $a_i = M^{-1}$ is a counterexample to (1). $\endgroup$
    – Felipe Voloch
    Commented Jul 10, 2013 at 17:07
  • 4
    $\begingroup$ 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. $\endgroup$
    – Felipe Voloch
    Commented Jul 10, 2013 at 20:08

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thankyou. Does the same probability hold if the prime has to be between $M$ and $N$ if $N < 2M$ or $M < 2N$? $\endgroup$
    – Turbo
    Commented Jul 10, 2013 at 19:07
  • $\begingroup$ I am unfamiliar with the density theorem. Could you provide the details for $2/18$ step? $\endgroup$
    – Turbo
    Commented Jul 10, 2013 at 19:24
  • 1
    $\begingroup$ 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). $\endgroup$
    – David E Speyer
    Commented Jul 10, 2013 at 19:28
  • 1
    $\begingroup$ Yes, that's it. $\endgroup$
    – David E Speyer
    Commented Jul 10, 2013 at 19:30
  • 1
    $\begingroup$ 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! $\endgroup$
    – David E Speyer
    Commented Jul 10, 2013 at 19:33
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Removed the trivial part $\endgroup$
    – Turbo
    Commented Jul 10, 2013 at 17:43
  • $\begingroup$ what about for higher residues? $\endgroup$
    – Turbo
    Commented Jun 15, 2016 at 7:44

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