Consider a Pell-type equation of the form:
$$x^2-ay^2=b$$
where $a,b\in\mathbb{Z}$. Does there exist a method to exclude the existence of integer solutions to such an equation?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ You can check the equation modulo $n$ for various $n$. For example, there are no integer solutions when $a \equiv 0 \!\!\!\mod \!3$ and $b \equiv 2 \!\!\!\mod \!3$. $\endgroup$– D. Ror.Commented Mar 12, 2017 at 19:56
-
1$\begingroup$ Expanding on the previous comment, an obvious necessary condition for existence is that $b$ is a square modulo $a$, where one can then apply quadratic reciprocity, etc. $\endgroup$– Todd TrimbleCommented Mar 12, 2017 at 20:14
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
For a specific problem, there is a finite check to decide whether any solutions exist to $x^2 - a y^2 = b.$ Find the minimum integers $u,v > 0$ such that $u^2 - a v^2 = 1.$ Any solution to your problem, say with $x,y$ positive, creates an infinite sequence of solutions by $$ (x,y) \mapsto (ux + av y, \; vx + u y). $$ This will increase the entries. In the other direction, that of decreasing one or both entries, $$ (x,y) \mapsto (ux - av y, \; -vx + u y). $$ Repeating this mapping gets us to a solution with both $x,y> 0$ but one of the entries in the left neighbor nonpositive, either $$ ux - ay \leq 0 \; \; \; \mbox{OR} \; \; \; -vx + uy \leq 0. $$ If you draw some picture, including the hyperbola $x^2 - a y^2 = b,$ you see how one or the other of $ux \leq ay$ or $uy \leq vx$ gives a bounded arc of the hyperbola. If there are no integer solutions in that arc, there are no solutions at all.
More generally, one may draw the Conway topograph for an indefinite form $a x^2 + bxy + c y^2.$ His "climbing lemma" shows how we need investigate only a finite region of the diagram to decide whether there is a (primitive) solution to $a x^2 + bxy + c y^2= n.$
$$ x^2 - 2 y^2 = 7 \cdot 17 \cdot 23 $$
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
Automorphism matrix:
3 4
2 3
Automorphism backwards:
3 -4
-2 3
3^2 - 2 2^2 = 1
x^2 - 2 y^2 = 2737
Sun Mar 12 14:48:31 PDT 2017
x: 53 y: 6 ratio: 8.83333 SEED KEEP +-
x: 55 y: 12 ratio: 4.58333 SEED KEEP +-
x: 57 y: 16 ratio: 3.5625 SEED KEEP +-
x: 73 y: 36 ratio: 2.02778 SEED KEEP +-
x: 75 y: 38 ratio: 1.97368 SEED BACK ONE STEP 73 , -36
x: 107 y: 66 ratio: 1.62121 SEED BACK ONE STEP 57 , -16
x: 117 y: 74 ratio: 1.58108 SEED BACK ONE STEP 55 , -12
x: 135 y: 88 ratio: 1.53409 SEED BACK ONE STEP 53 , -6
x: 183 y: 124 ratio: 1.47581
x: 213 y: 146 ratio: 1.4589
x: 235 y: 162 ratio: 1.45062
x: 363 y: 254 ratio: 1.42913
x: 377 y: 264 ratio: 1.42803
x: 585 y: 412 ratio: 1.4199
x: 647 y: 456 ratio: 1.41886
x: 757 y: 534 ratio: 1.4176
x: 1045 y: 738 ratio: 1.41599
x: 1223 y: 864 ratio: 1.41551
x: 1353 y: 956 ratio: 1.41527
x: 2105 y: 1488 ratio: 1.41465
x: 2187 y: 1546 ratio: 1.41462
x: 3403 y: 2406 ratio: 1.41438
x: 3765 y: 2662 ratio: 1.41435
x: 4407 y: 3116 ratio: 1.41431
x: 6087 y: 4304 ratio: 1.41427
x: 7125 y: 5038 ratio: 1.41425
x: 7883 y: 5574 ratio: 1.41424
x: 12267 y: 8674 ratio: 1.41423
x: 12745 y: 9012 ratio: 1.41423
x: 19833 y: 14024 ratio: 1.41422
x: 21943 y: 15516 ratio: 1.41422
x: 25685 y: 18162 ratio: 1.41422
x: 35477 y: 25086 ratio: 1.41422
x: 41527 y: 29364 ratio: 1.41421
x: 45945 y: 32488 ratio: 1.41421
x: 71497 y: 50556 ratio: 1.41421
x: 74283 y: 52526 ratio: 1.41421
x: 115595 y: 81738 ratio: 1.41421
x: 127893 y: 90434 ratio: 1.41421
x: 149703 y: 105856 ratio: 1.41421
x: 206775 y: 146212 ratio: 1.41421
x: 242037 y: 171146 ratio: 1.41421
x: 267787 y: 189354 ratio: 1.41421
x: 416715 y: 294662 ratio: 1.41421
x: 432953 y: 306144 ratio: 1.41421
x: 673737 y: 476404 ratio: 1.41421
x: 745415 y: 527088 ratio: 1.41421
x: 872533 y: 616974 ratio: 1.41421
x: 1205173 y: 852186 ratio: 1.41421
x: 1410695 y: 997512 ratio: 1.41421
x: 1560777 y: 1103636 ratio: 1.41421
x: 2428793 y: 1717416 ratio: 1.41421
x: 2523435 y: 1784338 ratio: 1.41421
x: 3926827 y: 2776686 ratio: 1.41421
x: 4344597 y: 3072094 ratio: 1.41421
x: 5085495 y: 3595988 ratio: 1.41421
x: 7024263 y: 4966904 ratio: 1.41421
x: 8222133 y: 5813926 ratio: 1.41421
x: 9096875 y: 6432462 ratio: 1.41421
x: 14156043 y: 10009834 ratio: 1.41421
x: 14707657 y: 10399884 ratio: 1.41421
Sun Mar 12 14:48:51 PDT 2017
x^2 - 2 y^2 = 2737
$$ x^2 - 2 y^2 = - 7 \cdot 17 \cdot 23 $$
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
Automorphism matrix:
3 4
2 3
Automorphism backwards:
3 -4
-2 3
3^2 - 2 2^2 = 1
x^2 - 2 y^2 = -2737
Sun Mar 12 14:50:52 PDT 2017
x: 1 y: 37 ratio: 0.027027 SEED KEEP +-
x: 25 y: 41 ratio: 0.609756 SEED KEEP +-
x: 31 y: 43 ratio: 0.72093 SEED KEEP +-
x: 41 y: 47 ratio: 0.87234 SEED KEEP +-
x: 65 y: 59 ratio: 1.10169 SEED BACK ONE STEP -41 , 47
x: 79 y: 67 ratio: 1.1791 SEED BACK ONE STEP -31 , 43
x: 89 y: 73 ratio: 1.21918 SEED BACK ONE STEP -25 , 41
x: 145 y: 109 ratio: 1.33028 SEED BACK ONE STEP -1 , 37
x: 151 y: 113 ratio: 1.33628
x: 239 y: 173 ratio: 1.3815
x: 265 y: 191 ratio: 1.38743
x: 311 y: 223 ratio: 1.39462
x: 431 y: 307 ratio: 1.40391
x: 505 y: 359 ratio: 1.40669
x: 559 y: 397 ratio: 1.40806
x: 871 y: 617 ratio: 1.41167
x: 905 y: 641 ratio: 1.41186
x: 1409 y: 997 ratio: 1.41324
x: 1559 y: 1103 ratio: 1.41342
x: 1825 y: 1291 ratio: 1.41363
x: 2521 y: 1783 ratio: 1.41391
x: 2951 y: 2087 ratio: 1.41399
x: 3265 y: 2309 ratio: 1.41403
x: 5081 y: 3593 ratio: 1.41414
x: 5279 y: 3733 ratio: 1.41414
x: 8215 y: 5809 ratio: 1.41418
x: 9089 y: 6427 ratio: 1.41419
x: 10639 y: 7523 ratio: 1.4142
x: 14695 y: 10391 ratio: 1.4142
x: 17201 y: 12163 ratio: 1.41421
x: 19031 y: 13457 ratio: 1.41421
x: 29615 y: 20941 ratio: 1.41421
x: 30769 y: 21757 ratio: 1.41421
x: 47881 y: 33857 ratio: 1.41421
x: 52975 y: 37459 ratio: 1.41421
x: 62009 y: 43847 ratio: 1.41421
x: 85649 y: 60563 ratio: 1.41421
x: 100255 y: 70891 ratio: 1.41421
x: 110921 y: 78433 ratio: 1.41421
x: 172609 y: 122053 ratio: 1.41421
x: 179335 y: 126809 ratio: 1.41421
x: 279071 y: 197333 ratio: 1.41421
x: 308761 y: 218327 ratio: 1.41421
x: 361415 y: 255559 ratio: 1.41421
x: 499199 y: 352987 ratio: 1.41421
x: 584329 y: 413183 ratio: 1.41421
x: 646495 y: 457141 ratio: 1.41421
x: 1006039 y: 711377 ratio: 1.41421
x: 1045241 y: 739097 ratio: 1.41421
x: 1626545 y: 1150141 ratio: 1.41421
x: 1799591 y: 1272503 ratio: 1.41421
x: 2106481 y: 1489507 ratio: 1.41421
x: 2909545 y: 2057359 ratio: 1.41421
x: 3405719 y: 2408207 ratio: 1.41421
x: 3768049 y: 2664413 ratio: 1.41421
x: 5863625 y: 4146209 ratio: 1.41421
x: 6092111 y: 4307773 ratio: 1.41421
x: 9480199 y: 6703513 ratio: 1.41421
x: 10488785 y: 7416691 ratio: 1.41421
x: 12277471 y: 8681483 ratio: 1.41421
x: 16958071 y: 11991167 ratio: 1.41421
Sun Mar 12 14:51:24 PDT 2017
x^2 - 2 y^2 = -2737
$$ x^2 - 2 y^2 = -15 $$
no integer solutions; prohibited by local conditions.
answered Mar 12, 2017 at 21:46
-
$\begingroup$ Thank you very much. How does this work if $b$ is negative? For instance, I am trying to understand $x^2-2y^2 = -15$ ? $\endgroup$– i87456Commented Mar 12, 2017 at 22:08
-
$\begingroup$ @i87456 I included two examples, one with $b$ negative. Yours has no integer solutions as there are prime factors that are $\pm 3 \pmod 8$ to odd exponents. Let me add the output for $-15.$ $\endgroup$ Commented Mar 12, 2017 at 22:11
$\begingroup$
$\endgroup$
Yes, but it is not easy. Check out John Robertson's book.
answered Mar 12, 2017 at 19:53
$\begingroup$
$\endgroup$
Yes. First if there are no solutions in $\mathbb{R}$ or in $\mathbb{Z}_p$ for some prime $p$, then there are no solutions in $\mathbb{Z}$.
This condition is not sufficient in general; there could be a Brauer-Manin obstruction to the Hasse principle. For more about the Brauer-Manin obstruction for integral solutions to quadratic equations, see: https://www.math.u-psud.fr/~colliot/CTXuCompositio2009.pdf
answered Mar 12, 2017 at 19:53