[Math] Existence of Solution to Generalized Pell’s Equation

algebraic-number-theorydiophantine equationselementary-number-theorynumber theorypell-type-equations

Consider the generalized Pell's equation $x^2 – dy^2 = n$ for $d \in \mathbb{Z}_{> 0}$ and $n \in \mathbb{Z} \setminus \{0\}$. When does this equation have a solution for $x,y$ over $\mathbb{Z}$?

Here is what I know thus far:

  1. In the case $n = \pm 1$, there is a complete characterization of the solutions to Pell's equation in terms of fundamental units.
  2. When $n$ is a square, one obtains solutions to the generalized Pell's equation by scaling solutions to Pell's equation.
  3. When $\mathbb{Q}(\sqrt{d})$ has class number $1$, one can try to construct a product of prime ideals whose norms multiply to $|n|$ and then obtain a solution by taking the generator of the product ideal.
  4. When $|n| < \sqrt{d}$, there is a criterion for existence of solutions in terms of continued fraction convergents (see http://mathworld.wolfram.com/PellEquation.html).
  5. In general, one can reduce the problem of solving the generalized Pell's equation to testing a finite collection of possible solutions (see http://math.stanford.edu/~conrad/154Page/handouts/genpell.pdf).

Nonetheless, I am unaware of any general criterion on $d$ and $n$ that can be used to determine whether a solution to the generalized Pell's equation exists. Has such a criterion been discovered?

Note: In Conrad's article, he claims that there is "no chance" for such a general existence result.

Best Answer

Here is the sort of thing that is not immediately visible in the quadratic field viewpoint. Suppose we have target $n,$ say $\gcd(n,4d) = 1$ and suppose we are able to solve $$ u^2 \equiv 4 d \pmod {4n}, $$ $$ u^2 = 4d + 4 n t. $$ Then $$ u^2 - 4 n t = 4 d. $$ Thus we have constructed a quadratic form $$ \langle n,u,t \rangle $$ of discriminant $4d.$ I meant to guarantee that the form was primitive. By the reduction scheme of Gauss and Lagrange, this form reduces over $SL_2 \mathbb Z$ to some "reduced" form $ \langle a,b,c \rangle $ of the same discriminant, where reduced is equivalent to $ac <0, b > |a+c|.$ This need not be the principal form, and if $n$ is prime there is just one possible form and its "opposite" that represent $n.$

Here is a good one: we can represent $x^2 - 229 y^2 = p$ (for $p \neq 2,3, 229$) if and only if $z^3 - 4 z - 1 $ factors into three distinct factors $\pmod p.$ This is from an Henri Cohen book, appendix. The form class group, reduced, are

916    factored   2^2 *  229

    1.             1          30          -4   cycle length            10
    2.             3          28         -11   cycle length            18
    3.            11          28          -3   cycle length            18

  form class number is   3

=====================================================================

Small positive primes 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

parisize = 4000000, primelimit = 500509
? factormod( z^3 - 4 * z - 1, 37)
%1 = 
[Mod(1, 37)*z + Mod(8, 37) 1]

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

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

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

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

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

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

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

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

?

============================================

Monday, 19 Feb.: now i remember why I stuck with positive binary forms for my inhomogeneous examples; I just ran $$3 x^2 + 13 x y - 5 y^2 + z^3 - 4 z \neq \pm 1$$ which is very nice. However, in order to have the discriminant of $z^3 - 4 z + r$ to be a square multiple of that for $r=1,$ we get $27 r^2 + 229 w^2 = 256,$ so we get no more. Compare https://mathoverflow.net/questions/12486/integers-not-represented-by-2-x2-x-y-3-y2-z3-z and Kevin Buzzard's answer. The collection of related material, as pdfs, is now at ZAKUSKI INHOM

Probably enough. I like Buell, Binary Quadratic Forms. Similar in Dickson, Introduction to the Theory of Numbers (1929). Comparison of definitions of "reduced" is in Franz Lemmermeyer's 2010 book, page 37 (pdf 43) Theorem 1.36.

For actually finding all representations of some $n$ of intermediate size by an indefinite form, i like Conway's topograph method. It displays both the action of the (oriented) automorphism group of the form and the finite set of representations that are distinct under the group action. Here is one with pretty good illustrations, I found that drawing by hand on paper works best by drawing the "river" on one page (if it will fit) but then draw "trees" leaving the riverside to show the targets http://math.stackexchange.com/questions/739752/how-to-solve-binary-form-ax2bxycy2-m-for-integer-and-rational-x-y/739765#739765

http://www.maths.ed.ac.uk/~aar/papers/conwaysens.pdf and

https://www.math.cornell.edu/~hatcher/TN/TNbook.pdf and

http://www.springer.com/us/book/9780387955872

http://bookstore.ams.org/mbk-105/

Related Question