4
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why ? $x^2-992y^2=1$ The first solution. $x=63$ ; $y=2$ Know? $\endgroup$ – individ Jul 27 '14 at 17:15
  • $\begingroup$ 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. $\endgroup$ – punctured dusk Jul 27 '14 at 17:20
  • $\begingroup$ That's not what I asked. You know how to find the first decision without degradation in continued fractions? $\endgroup$ – individ Jul 27 '14 at 17:29
  • $\begingroup$ There are several algorithms, yes, but what is your question really? $\endgroup$ – punctured dusk Jul 27 '14 at 17:30
  • $\begingroup$ Several? For example? Not continued fractions. $\endgroup$ – individ Jul 27 '14 at 17:33
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I guess it depends what "almost always" means... $\endgroup$ – G Tony Jacobs Jul 27 '14 at 17:43
  • 1
    $\begingroup$ In this sort of context, "almost always" means something like $0$ asymptotic density. $\endgroup$ – André Nicolas Jul 27 '14 at 17:48
  • $\begingroup$ Gotcha, and I had misread your answer initially. Makes perfect sense. $\endgroup$ – G Tony Jacobs Jul 27 '14 at 17:54
3
$\begingroup$

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$ 
$\endgroup$

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.