# Small roots of $f(x) \equiv 0 \pmod{n^2}$

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

• 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)$. – Ilya Bogdanov Sep 19 '17 at 13:48
• @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. – joro Sep 19 '17 at 14:13
• 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?.. – Ilya Bogdanov Sep 19 '17 at 14:19
• @IlyaBogdanov Thanks. I am wrong, indeed there is problem. Similar argument appears to work for $x^2+2$ AFAICT, so the bug is deeper. – joro Sep 19 '17 at 14:35
• Perhaps, you need $a\leq \mu n$ where $\mu$ is a constant (which does not depend on $n$ but may depend on the polynomial)? – 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.

LATER

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

$(2^83^3\pm1,2^{11}3^3\pm4\cdot2^3)$

$(2^23^35^3\pm1,2^33^35^4\pm2^35^1)$

• 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). – Noam D. Elkies Sep 19 '17 at 22:03
• Those example pairs are crazy! Perhaps they are related to aurifeuillian factorizations. – Greg Martin Sep 19 '17 at 23:25
• 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$). – Noam D. Elkies Sep 20 '17 at 3:12
• @NoamD.Elkies Are there constructions based on chinese remainder? (possibly with several linear factors). – joro Sep 20 '17 at 13:43
• 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. – joro Sep 20 '17 at 13:46