Solving diophantine equations of the form $x^2 - ay^2 = b$

Question

Solving $x^2 - ay^2 = b$

$a, b$ are given integers with a squarefree and $b$ prime, and I need to find pairs of integers $(x,y)$ that is a solution.

I try writing $a$ as $(\sqrt{a})^2$ , so the equation becomes $(x^2 - (\sqrt{a}\cdot y)^2)$. This is a difference of squares so I can write as $(x+y \sqrt{a}) (x - y \sqrt{a})$.

This means that I am factoring b in the ring $Z[\sqrt{a}]$. I can factor the ideal generated by $b$:

$Z[\sqrt{a}]/(b) = Z[x]/(x^2 -a, b) = Z/(b) [x] / (x^2 -a)$, and factoring $(x^2 -a)$ in the field (since $b$ is prime) $Z/(b)$ gives me a factorization of the ideal $(b)$. If $x^2 -a$ is irreducible, then $(b)$ cannot be factored, so there are no solutions.

The thing that I am stuck on is how to turn a factorization of the ideal $(b)$ into a factorization of $b$, and thus a solution to the diophantine equation?

Answer 1

Your quadratic form $\langle 1, 0, -a \rangle$ has discriminant $4a.$ If there is a solution, with prime $p,$ to $$ \beta^2 \equiv 4 a \pmod {4p}, $$ then we have an integer $t$ with $$ \beta^2 = 4a + 4pt, $$ whence form $$ \langle p, \beta, t \rangle. $$

Lagrange's methods reduce this to some form. The full cycle of this form is then calculated. If this form represents $1,$ it is, indeed, the principal form, and inverting some two by two matrix tells us how to solve $x^2 - a y^2 = p.$ There is, however, no guarantee that it is the principal form we find, when the class number is larger than one. Further, it is usually impossible to tell ahead of time which reduced form is found. For example, $x^2 - 229 y^2$ does not represent either prime $3$ or $11,$ but there is no way to predict this merely by congruences.

Same for these primes, which are not represented by $x^2 - 229 y^2,$ rather by $3 x^2 + 28 xy - 11 y^2$ and $11 x^2 + 28 xy - 3 y^2.$ These are equivalent to $3 x^2 + 2 xy - 76 y^2$ and $76 x^2 + 2 xy - 3 y^2$

     3     5    11    17    19    43    61    71    83    97
   103   149   151   167   181   233   271   277   293   307
   311   337   367   373   397   401   409   421   431   433
   457   463   467   491   557   569   587   631   641   661
   673   683   701   733   743   751   757   769   787   821
   859   863   883   911   919   941   953   971   991   997

The odd primes $p,$ with $(229|p)=1,$ that can actually be written as $x^2 - 229 y^2$ are those for which there are three roots to $$ z^3 - 4z + 1 \equiv 0 \pmod p. $$ Also $229$ itself. For the primes above, the cubic is irreducible

? factormod( z^3 - 4 * z + 1 , 3 )
%2 = 
[Mod(1, 3)*z^3 + Mod(2, 3)*z + Mod(1, 3) 1]

? factormod( z^3 - 4 * z + 1 , 5 )
%3 = 
[Mod(1, 5)*z^3 + Mod(1, 5)*z + Mod(1, 5) 1]

? factormod( z^3 - 4 * z + 1 , 11 )
%4 = 
[Mod(1, 11)*z^3 + Mod(7, 11)*z + Mod(1, 11) 1]

? factormod( z^3 - 4 * z + 1 , 17 )
%5 = 
[Mod(1, 17)*z^3 + Mod(13, 17)*z + Mod(1, 17) 1]

? factormod( z^3 - 4 * z + 1 , 19 )
%6 = 
[Mod(1, 19)*z^3 + Mod(15, 19)*z + Mod(1, 19) 1]

? factormod( z^3 - 4 * z + 1 , 43 )
%7 = 
[Mod(1, 43)*z^3 + Mod(39, 43)*z + Mod(1, 43) 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

These primes can be written as $x^2 - 229 y^2:$

    37    53   173   193   229   241   347   359   383   439
   443   449   461   503   509   541   593   607   617   619
   643   691   907   967   977  1019  1051  1063  1097  1109
  1249  1277  1291  1303  1321  1399  1429  1583  1667  1741
  1783  1993  1997  2003  2087  2137  2143  2333  2347  2351
  2371  2381  2393  2503  2579  2657  2677  2687  2699  2729
  2749  2767  2791  2803  2897

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

? factormod( z^3 - 4 * z + 1 , 37 )
%1 = 
[Mod(1, 37)*z + Mod(21, 37) 1]

[Mod(1, 37)*z + Mod(24, 37) 1]

[Mod(1, 37)*z + Mod(29, 37) 1]

? factormod( z^3 - 4 * z + 1 , 53 )
%2 = 
[Mod(1, 53)*z + Mod(24, 53) 1]

[Mod(1, 53)*z + Mod(34, 53) 1]

[Mod(1, 53)*z + Mod(48, 53) 1]

? factormod( z^3 - 4 * z + 1 , 173 )
%3 = 
[Mod(1, 173)*z + Mod(9, 173) 1]

[Mod(1, 173)*z + Mod(17, 173) 1]

[Mod(1, 173)*z + Mod(147, 173) 1]

? factormod( z^3 - 4 * z + 1 , 193 )
%4 = 
[Mod(1, 193)*z + Mod(42, 193) 1]

[Mod(1, 193)*z + Mod(157, 193) 1]

[Mod(1, 193)*z + Mod(187, 193) 1]

? factormod( z^3 - 4 * z + 1 , 229 )
%5 = 
[Mod(1, 229)*z + Mod(58, 229) 1]

[Mod(1, 229)*z + Mod(200, 229) 2]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Not sure about the prime $2,$ for odd primes $q$ when $(229|q) = -1,$ we get one root, factors as a linear times a quadratic:

? factormod( z^3 - 4 * z + 1 , 2 )
%8 = 
[Mod(1, 2)*z + Mod(1, 2) 1]

[Mod(1, 2)*z^2 + Mod(1, 2)*z + Mod(1, 2) 1]

? factormod( z^3 - 4 * z + 1 , 7 )
%9 = 
[Mod(1, 7)*z + Mod(3, 7) 1]

[Mod(1, 7)*z^2 + Mod(4, 7)*z + Mod(5, 7) 1]

? factormod( z^3 - 4 * z + 1 , 13 )
%10 = 
[Mod(1, 13)*z + Mod(5, 13) 1]

[Mod(1, 13)*z^2 + Mod(8, 13)*z + Mod(8, 13) 1]

? factormod( z^3 - 4 * z + 1 , 23 )
%11 = 
[Mod(1, 23)*z + Mod(12, 23) 1]

[Mod(1, 23)*z^2 + Mod(11, 23)*z + Mod(2, 23) 1]

? factormod( z^3 - 4 * z + 1 , 29 )
%12 = 
[Mod(1, 29)*z + Mod(16, 29) 1]

[Mod(1, 29)*z^2 + Mod(13, 29)*z + Mod(20, 29) 1]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=