Let $f(x)$ be squarefree polynomial with integer coefficients.

For integer $n$ define "small root modulo $n^2$" integer $a$ satisfying $1 \le a \le n$ and $f(a) \equiv 0 \pmod{n^2}$ and $f(a) \ne 0$.

If $f(x)$ is quadratic there are infinitely many small roots coming from $C f(x)=\square$. Ilya Bogdanov showed this claim is wrong.

Is it true that for all $f(x)$ with $\deg(f) \ge 3$ there are infinitely many $n$ for which small roots modulo $n^2$ exist?

What is computational approach to finding small roots given $f(x)$?

  • 1
    $\begingroup$ It seems that you need an irreducible polynomial, rather than squarefree. I think there are finitely many such $n$ for a polynomial $x(x+1)$. $\endgroup$ – Ilya Bogdanov Sep 19 '17 at 13:48
  • $\begingroup$ @IlyaBogdanov How so? $2 x (x+1) = y^2$ has infinitely many solutions. This works if f(x) has quadratic factor. I don't think irreducible is necessary. $\endgroup$ – joro Sep 19 '17 at 14:13
  • $\begingroup$ If $1\leq a\leq n$ and $n^2\mid a(a+1)$, then $a^2+a\geq n^2$, i.e., $a=n$. This does not work for $n>1$. I don't know how to treat your argument: if $2x(x+1)=y^2$ then $x(x+1)$ is divisible only by $(y/2)^2$, and $x>y/2$, so what?.. $\endgroup$ – Ilya Bogdanov Sep 19 '17 at 14:19
  • 1
    $\begingroup$ @IlyaBogdanov Thanks. I am wrong, indeed there is problem. Similar argument appears to work for $x^2+2$ AFAICT, so the bug is deeper. $\endgroup$ – joro Sep 19 '17 at 14:35
  • $\begingroup$ Perhaps, you need $a\leq \mu n$ where $\mu$ is a constant (which does not depend on $n$ but may depend on the polynomial)? $\endgroup$ – Ilya Bogdanov Sep 19 '17 at 14:45

If one imagines that $f(a) \bmod n^2$ is about uniformly distributed (for most large enough $n$ ) then the probability of having a small root $\bmod n^2$ is $1/n$ so that would point to infinitely many small roots but very sparsely distributed.

At least up to $n=10000$ there are no small roots $\bmod n^2$ for $f(x)=x^3+2$.

LATER $f(34697)= 53\cdot239\cdot57425^2$

An indication that maybe things are not so random, at least for this polynomial, are these interesting cases with $\frac{a}{n}$ reasonably small.

$f(208)=6\cdot131\cdot107^2$ with $\frac{a}{n} \approx 1.944.$

$f(224)=22\cdot43\cdot109^2$ with $\frac{a}{n} \approx 2.055.$

$f(3440)=2\cdot27329\cdot863^2$ with $\frac{a}{n} \approx 3.986.$

$f(3472)=6\cdot9323\cdot865^2$ with $\frac{a}{n} \approx 4.014.$

$f(17472)=2\cdot313848\cdot2915^2$ with $\frac{a}{n} \approx 5.99383.$

$f(17520)=2\cdot251\cdot1259\cdot2917^2$ with $\frac{a}{n} \approx 6.00617.$

These three pairs have some remarkable properties which I can't explain. Among them are

$107,109=2^23^3\pm1$ and $208,224=2^33^3\pm1\cdot2^3$

$863,864=2^53^3\pm1$ and $3440,3472=2^73^3\pm2\cdot2^3$

$2915,2917=2^73^6\pm1$ and $17472,17520=2^33^7\pm3\cdot2^3$

One other case not in a pair like this is

$f(2272)=6\cdot1019\cdot1385^2$ with $\frac{a}{n} \approx 1.64.$

It is true that $2272=2^83^2-8\cdot2^3$ but $f(2^83^2+8\cdot2^3)$ is square free.


The previous results (except $(a,n)=(34697,57425))$ were unintelligent brute force. Slightly more intelligent is the fact that there is code to solve $f(x) \mod m$ (so here $m=n^2$.) Using that I found the mentioned solution and, as expected, a fourth and fifth pair with $\frac{a}{n}$ very close to $8$ and to $10$.

The $(a,n)$ pairs are



  • 1
    $\begingroup$ also $111977^2 \mid 461563^3 + 2$, and no further examples of $n^2 \mid a^3 + 2$ with $n > a$ and $a < 10^6$ (result of a three-minute gp calculation). $\endgroup$ – Noam D. Elkies Sep 19 '17 at 22:03
  • $\begingroup$ Those example pairs are crazy! Perhaps they are related to aurifeuillian factorizations. $\endgroup$ – Greg Martin Sep 19 '17 at 23:25
  • 1
    $\begingroup$ Your three pairs generalize to $(a,n) = (216 k^4 \pm 8k, n = 108 k^3 \pm 1)$. If the residual factor $864 k^6 \pm 80 k^3 + 2$ happens to itself have a large square factor $f^2$ then you can replace $n$ by $fn$, which might occasionally exceed $a$. The first example is $k = -15010$, for which $f = 91669$ and $a/n$ is about $.3274$; there are no others with $|k| < 2^{15}$, though $k = -1671$ comes close: $a/n > 1.07$). $\endgroup$ – Noam D. Elkies Sep 20 '17 at 3:12
  • $\begingroup$ @NoamD.Elkies Are there constructions based on chinese remainder? (possibly with several linear factors). $\endgroup$ – joro Sep 20 '17 at 13:43
  • $\begingroup$ Thanks Aaron. I think better quality than $a/n$ is $\log{a}/\log{n}$. With few linear factors the log quality can be low too. $\endgroup$ – joro Sep 20 '17 at 13:46

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.