# $x^2+1$ is almost always square free

It seems like $x^2+1$ is almost always square free. Any research or heuristics why?

I tried breaking the problem into solving $$x^2-ky^2=1$$ For various $k$, and I conjecture that for every $k$ there are at most finitely many solutions to the Diophantine equation. I'm pretty sure this is correct but dont know how to prove it. Any ideas on my two problems?

The equation $$x^2-ky^2=1$$ for non-square $k$ is known as Pell's equation. Lagrange proved that every Pell's equation has infinitely many solutions. Moreover, if $(x_0,y_0)$ is the smallest non-trivial positive solution, all integer solutions are implicitly given by $$x+y\sqrt k=\pm\,(x_0+y_0\sqrt k)^n\;, \qquad n\in\mathbb Z.$$ As you can see, the solutions generated by this formula quickly become very large, making it natural to conjecture that there are only finitely many solutions. For $k=991$, the smallest solution is $$y=12,055,735,790,331,359,447,442,538,767,$$ which illustrates that the smallest solution can still be extremely big. (found here, actually Joseph Rotman's A First Course in Albegra: with applications)
Note that for square $k=m^2$ the equation becomes $(x+my)(x-my)=1$, which has at most $2$ solutions.

Regarding the square-freeness of $x^2+1$, I found this paper by D.R. Heath-Brown on arXiv, giving asymptotics for the number of $x$ for which $x^2+1$ is square-free. It turns out that such numbers have non-zero asymptotic density equal to $$\frac12\prod_{p\equiv1\pmod4}\left(1-\frac2{p^2}\right).$$

• Why ? $x^2-992y^2=1$ The first solution. $x=63$ ; $y=2$ Know? – individ Jul 27 '14 at 17:15
• I did not claim that the smallest solution grows quickly, of course it doesn't. For $k=99999999$ the smallest solution is only $x=10000$, $y=1$. I said that the solutions to a particular, fixed, equation grow quickly. – punctured dusk Jul 27 '14 at 17:20
• That's not what I asked. You know how to find the first decision without degradation in continued fractions? – individ Jul 27 '14 at 17:29
• There are several algorithms, yes, but what is your question really? – punctured dusk Jul 27 '14 at 17:30
• Several? For example? Not continued fractions. – individ Jul 27 '14 at 17:33

It is not true that $x^2+1$ is almost always square-free. For if $x\equiv 7\mod{25}$, then $x^2+1$ is divisible by $25$.

• I guess it depends what "almost always" means... – G Tony Jacobs Jul 27 '14 at 17:43
• In this sort of context, "almost always" means something like $0$ asymptotic density. – André Nicolas Jul 27 '14 at 17:48

Note that $x^2 + 1$ is never divisible by $4$ or by any prime $q \equiv 3 \pmod 4,$ therefore not by $q^2$ for such $q.$ However, for any prime $p \equiv 1 \pmod 4,$ there are two square roots of $-1 \pmod {p^2},$ and for such a number, call it $k,$ not only is $k^2 + 1$ divisible by $p^2,$ for any integer $n$ we have $(k + n p^2)^2 + 1$ is divisible by $p^2.$

Here are the $x^2 + 1$ for $x \leq 500$ that are divisible by a square larger than $1.$ As you can see, for $x = 7,18 + 25n$ we get $x^2 + 1 \equiv 0 \pmod {5^2}.$ For $x = 70,99 + 169n$ we get $x^2 + 1 \equiv 0 \pmod {13^2}.$ For $x = 38,251 + 289n$ we get $x^2 + 1 \equiv 0 \pmod {17^2}.$ For $x = 41,800 + 841n$ we get $x^2 + 1 \equiv 0 \pmod {29^2}.$ For $x = 117,1252 + 1369n$ we get $x^2 + 1 \equiv 0 \pmod {37^2}.$

7  50 = 2 cdot 5^2
18  325 = 5^2 13
32  1025 = 5^2 41
38  1445 = 5 cdot 17^2
41  1682 = 2 cdot 29^2
43  1850 = 2 cdot 5^2 37
57  3250 = 2 cdot 5^3 13
68  4625 = 5^3 37
70  4901 = 13^2 29
82  6725 = 5^2 269
93  8650 = 2 cdot 5^2 173
99  9802 = 2 cdot 13^2 29
107  11450 = 2 cdot 5^2 229
117  13690 = 2 cdot 5 cdot 37^2
118  13925 = 5^2 557
132  17425 = 5^2 cdot 17 41
143  20450 = 2 cdot 5^2 409
157  24650 = 2 cdot 5^2 cdot 17 29
168  28225 = 5^2 1129
182  33125 = 5^4 53
193  37250 = 2 cdot 5^3 149
207  42850 = 2 cdot 5^2 857
218  47525 = 5^2 1901
232  53825 = 5^2 2153
239  57122 = 2 cdot 13^4
243  59050 = 2 cdot 5^2 1181
251  63002 = 2 cdot 17^2 109
257  66050 = 2 cdot 5^2 1321
268  71825 = 5^2 cdot 13^2 17
282  79525 = 5^2 3181
293  85850 = 2 cdot 5^2 cdot 17 101
307  94250 = 2 cdot 5^3 cdot 13 29
318  101125 = 5^3 809
327  106930 = 2 cdot 5 cdot 17^2 37
332  110225 = 5^2 4409
343  117650 = 2 cdot 5^2 cdot 13 181
357  127450 = 2 cdot 5^2 2549
368  135425 = 5^2 5417
378  142885 = 5 cdot 17 cdot 41^2
382  145925 = 5^2 cdot 13 449
393  154450 = 2 cdot 5^2 3089
407  165650 = 2 cdot 5^2 3313
408  166465 = 5 cdot 13^2 197
418  174725 = 5^2 cdot 29 241
432  186625 = 5^3 1493
437  190970 = 2 cdot 5 cdot 13^2 113
443  196250 = 2 cdot 5^4 157
457  208850 = 2 cdot 5^2 4177
468  219025 = 5^2 8761
482  232325 = 5^2 9293
493  243050 = 2 cdot 5^2 4861
500  250001 = 53^2 89
jagy@phobeusjunior:~$ The easiest program for Pell's equation is the Lagrange-Gauss cycle method, no decimal accuracy is required and no "cycle detection" is needed. In all other ways it is the same as continued fractions. Here is$991:$jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 991

0  form   1 62 -30   delta  -2
1  form   -30 58 5   delta  12
2  form   5 62 -6   delta  -10
3  form   -6 58 25   delta  2
4  form   25 42 -22   delta  -2
5  form   -22 46 21   delta  2
6  form   21 38 -30   delta  -1
7  form   -30 22 29   delta  1
8  form   29 36 -23   delta  -2
9  form   -23 56 9   delta  6
10  form   9 52 -35   delta  -1
11  form   -35 18 26   delta  1
12  form   26 34 -27   delta  -1
13  form   -27 20 33   delta  1
14  form   33 46 -14   delta  -3
15  form   -14 38 45   delta  1
16  form   45 52 -7   delta  -8
17  form   -7 60 13   delta  4
18  form   13 44 -39   delta  -1
19  form   -39 34 18   delta  2
20  form   18 38 -35   delta  -1
21  form   -35 32 21   delta  2
22  form   21 52 -15   delta  -3
23  form   -15 38 42   delta  1
24  form   42 46 -11   delta  -4
25  form   -11 42 50   delta  1
26  form   50 58 -3   delta  -20
27  form   -3 62 10   delta  6
28  form   10 58 -15   delta  -4
29  form   -15 62 2   delta  31
30  form   2 62 -15   delta  -4
31  form   -15 58 10   delta  6
32  form   10 62 -3   delta  -20
33  form   -3 58 50   delta  1
34  form   50 42 -11   delta  -4
35  form   -11 46 42   delta  1
36  form   42 38 -15   delta  -3
37  form   -15 52 21   delta  2
38  form   21 32 -35   delta  -1
39  form   -35 38 18   delta  2
40  form   18 34 -39   delta  -1
41  form   -39 44 13   delta  4
42  form   13 60 -7   delta  -8
43  form   -7 52 45   delta  1
44  form   45 38 -14   delta  -3
45  form   -14 46 33   delta  1
46  form   33 20 -27   delta  -1
47  form   -27 34 26   delta  1
48  form   26 18 -35   delta  -1
49  form   -35 52 9   delta  6
50  form   9 56 -23   delta  -2
51  form   -23 36 29   delta  1
52  form   29 22 -30   delta  -1
53  form   -30 38 21   delta  2
54  form   21 46 -22   delta  -2
55  form   -22 42 25   delta  2
56  form   25 58 -6   delta  -10
57  form   -6 62 5   delta  12
58  form   5 58 -30   delta  -2
59  form   -30 62 1   delta  62
60  form   1 62 -30

disc   3964
Automorph, written on right of Gram matrix:
5788591406539787767296194303  361672073709940783423276163010
12055735790331359447442538767  753244210407084073508733597857

Pell automorph
379516400906811930638014896080  11947234168218377212415555918097
12055735790331359447442538767  379516400906811930638014896080

Pell unit
379516400906811930638014896080^2 - 991 * 12055735790331359447442538767^2 = 1

=========================================

991       991

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus\$