1

In the answer to this previous question , Noam D. Elkies proved that for any integer $x$, $x^3-x^2-2x+1$ can only have a divisors equal to $-1$, $0$, or $1$ modulo $7$. I would like to know what is known about this type of questions in general.

Most generally, is there an algorithm that, given a polynomial $P$ in variables $z_1,\dots,z_n$ with integer coefficients, and integers $m,a,b$, determines where there exist integers $z_1,\dots,z_n$ such that $P(z_1,\dots,z_n)=x \cdot y$ for $x \equiv a \, (\text{mod} \, m)$ and $y \equiv b \, (\text{mod} \, m)$? This is equivalent to Hilbert 10-th problem for the equations of the form $(mx+a)(my+b)=P(z_1,\dots,z_n)$.

In particular, is there an algorithm that, given a polynomial $P$ as above, and integers $m,a,b$, determines where there exist integers $z_1,\dots,z_n$ such that $P(z_1,\dots,z_n)$ has a divisor $x$ such that $x \equiv a \, (\text{mod} \, m)$ ?

As a special case, what if $P(z)$ is a polynomial in one variable?

An even more special case, what if $P(z)$ is (a) cubic, or (b) quartic?

Bogdan Grechuk
  • 5,947
  • 1
  • 25
  • 42
  • 3
    Characterizing primes dividing values of a polynomial is a deep and complicated subject - it leads quite directly to class field theory as well as its nonabelian variants, tying even to Langlands program. Assuming $P$ is univariate and irreducible, then those primes can be characterized in terms of factorization of primes in the splitting field $K$ of $P$, and the congruence conditions mod $m$ can be seen by considering the extension $K\mathbb Q(\zeta_m)$. Using Chebotarev density theorem you should be able to characterize all the possibilities. – Wojowu Oct 16 '22 at 17:15
  • I apologize the above ended up being mostly throwing a lot of big words at you! I hope someone else will be able to turn that into a proper answer. Algorithmic algebraic number theory is quite well developed, so it definitely should be possible. – Wojowu Oct 16 '22 at 17:16
  • 1
    your given polynomial is a bit special, monic cubic with discriminant a square. These are in table B.4, pages521-523, Henri Cohen, A Course in Computational Number Theory. The Galois group is then cyclic.... next are $x^3-3x-1, ; ; ; $ and $x^3-x^2-4x-1$ see http://zakuski.math.utsa.edu/~jagy/cox_galois_Gaussian_periods.pdf – Will Jagy Oct 17 '22 at 02:28
  • see also Reuschle, https://archive.org/details/tafelncomplexer00unkngoog/page/6/mode/2up whole $\lambda = 9$ starts page 173. Then $n=63$ starts page 284, goes to 304. Interesting footnotes; note that two cubics are involved, $x^3-21 x -28$ and $x^3 - 21 x +35$ Found online, https://www.lmfdb.org/NumberField/?degree=3&galois_group=C3&search_type=List – Will Jagy Oct 17 '22 at 02:56

1 Answers1

2

The first several examples similar to your cubic. For any one with discriminant $n^2,$ factor several values of the cubic and checking each prime modulo that $n.$

enter image description here

Will Jagy
  • 25,349