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