11
$\begingroup$

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?

$\endgroup$
  • $\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. Mar 12 '17 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 Trimble Mar 12 '17 at 20:14
11
$\begingroup$

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 $$ enter image description here

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 $$ enter image description here

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. enter image description here

$\endgroup$
  • $\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$ – i87456 Mar 12 '17 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$ – Will Jagy Mar 12 '17 at 22:11
6
$\begingroup$

Yes, but it is not easy. Check out John Robertson's book.

$\endgroup$
6
$\begingroup$

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

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