I have an equation in $x$ and I would like to determine if it has any solutions modulo a large prime $p$. Suppose $p$ is large enough that I can factor numbers up to $p$, but I cannot test all values up to $p$. (Actually, so far, I have been doing just that -- but I'd like to avoid this as it takes a long time. If you can avoid factoring, all the better.)

The particular equation I have is $$ x^4-x^2\equiv4\pmod p $$ but I would be interested in

  1. Solutions to this particular problem, or more generally
  2. Solutions to other quadratics$\pmod p$ in $x^2$, or more generally
  3. Solutions to quartics$\pmod p$.

I'm familiar with quadratic reciprocity but not with cubic or biquadratic. (It's not clear to me if this can be transformed so they can be used; if so, demonstrating the transformation and giving a pointer to a good source on higher reciprocity would suffice as an answer.)


Qiaochu gives a nice general answer. For this particular problem, we can get our hands dirty to determine whether there's a solution.

Since $p>2$, you can apply the quadratic formula to see that $x^2 = \frac{1}{2}(1 \pm \sqrt{17})$. Now, if you are working with a specific large prime $p$, you can use quadratic reciprocity to determine whether $\sqrt{17}$ exists, and then use quadratic reciprocity again to see whether a solution $x$ exists.

  • $\begingroup$ So this is really a solution for any $ax^4+bx^2\equiv c$, right? Very easy and useful. $\endgroup$ – Charles Nov 11 '12 at 23:35

The product of the linear factors of a polynomial $f(x) \in \mathbb{F}_p[x]$ is given by

$$\gcd(x^p - x, f(x))$$

over $\mathbb{F}_p[x]$, which can be quickly computed for small $p$ by the Euclidean algorithm. For larger $p$, you can instead compute $x^p \bmod f(x)$ (thinking of $f(x)$ as an element of $\mathbb{F}_p[x]$) by binary exponentiation, being careful to reduce $\bmod f(x)$ at every step.

The problem of explicitly describing the set of primes $p$ for which some polynomial has a root $\bmod p$ requires higher reciprocity laws. When the Galois group of the polynomial is abelian, my understanding is that these can be deduced from general results in class field theory. When the Galois group is nonabelian, my understanding is that higher reciprocity laws are open problems, closely related to the Langlands program. A very explicit example is the following: let

$$f(x) = x^3 - x - 1.$$

Then the splitting behavior of $f(x) \bmod p$ is determined by the $p^{th}$ coefficient of the modular form

$$q \prod_{n=1}^{\infty} (1 - q^n) (1 - q^{23n}).$$

See this MO question for some details.

Edit: in this particular case, the Galois group is the Klein four group $C_2 \times C_2$, which is abelian. By the Kronecker-Weber theorem, we then know that the splitting field of $f(x) = x^4 - x^2 = 4$ embeds into some cyclotomic field $\mathbb{Q}(\zeta_n)$, which implies that with finitely many exceptions the primes $p$ such that $f$ has a root $\bmod p$ are precisely the primes in some finite collection of arithmetic progressions with common difference $n$. To figure out exactly what these arithmetic progressions are one would need more specific information about the embedding into a cyclotomic field.


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.