# How to prove that there exist infinitely many integer solutions to the equation $x^2-ny^2=1$ without Algebraic Number Theory

I learned in my Intro Algebraic Number Theory class that there exist infinitely many integer pairs $(x,y)$ that satisfy the hyperbola $x^2-ny^2=1$; just consider that there are infinitely many units in $\mathcal{O}_{\mathbb{Q}(\sqrt{n})}$, and their norms satisfy the desired equation. Although this is a nice connection, I was wondering if it is possible to reach the solution without using high-powered Algebraic Number Theory. And more generally, does the same result hold true for $x^2-ny^2=k$ where $k$ is any integer? And how would one solve that?

-
You need to assume that $n$ is not a perfect square – Cocopuffs Apr 9 '13 at 21:03
See the "History" section here: en.wikipedia.org/wiki/Pell%27s_equation. There are ancient proofs that there are infinitely many solutions! – Cocopuffs Apr 9 '13 at 21:08
I see...some good old-fashioned Number Theory! I need to read up more on this. Amazing that this was solved so long ago... – Coffee_Table Apr 9 '13 at 21:15
Translate back the result from ANT! Assume that $(x,y)$ is a solution. Therefore $u=x+ y\sqrt n$ has norm $1$. Therefore so does $u^\ell=x_\ell+y_\ell\sqrt n$. Therefore $(x_\ell,y_\ell)$ is also a solution. You get the numbers $(x_\ell,y_\ell)$ from the binomial formula. For example, $x_2=x^2+ny^2$, $y_2=2xy$, $x_3=x^3+3nxy^2$, $y_3=3yx^2+ny^3$ et cetera. Essentially you are combining the multiplicativity of the norm (can be proven without ANT) and the binomial theorem. So w/o any real ANT. – Jyrki Lahtonen Apr 10 '13 at 8:40
@JyrkiLahtonen : I see that the essential method you're using to generate the infinite solns is not ANT but rather NT; but do you mean the use of the norm is not ANT? What is it then, just general Abstract-Alg ? – Coffee_Table Apr 10 '13 at 19:11

## 2 Answers

EDIT: there have been many comments on my answers asking about the use of the word automorph. This is a real thing! I did not just make up a word. For a fixed quadratic form, you get a group of integral automorphs. In just two variables, there is a good recipe for finding all. In three or more variables, it is a mess. Sometimes this is called the orthogonal group of the form, or the isometry group. If you think about finding all real solutions of the basic matrix equation, $A^T F A = F,$ where $F$ is a symmetric matrix associated with a quadratic form, the group part may be clearer, especially when $F=I.$ If $F$ has all rational entries, it is reasonable to solve this with rational or $p$-adic entries in $A.$ Finally, when $F,$ or at least $2 F,$ has integer entries, it is reasonable to ask about $A$ with integer entries.

I would like people to know more about this. In dimension 2 this has considerable overlap with algebraic number theory for quadratic fields. In dimension 3 or more, the theory of quadratic forms, in this case indefinite forms, separates from algebraic number theory to a considerable extent.

ORIGINAL:Given nontrivial $\tau^2 - n \sigma^2 = 1,$ we get

$$\left( \begin{array}{cc} \tau & \sigma \\ n \sigma & \tau \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -n \end{array} \right) \left( \begin{array}{cc} \tau & n \sigma \\ \sigma & \tau \end{array} \right) = \left( \begin{array}{cc} 1 & 0 \\ 0 & -n \end{array} \right).$$

As a result, if $x^2 - n y^2 = k,$ then we get the same $k$ for $$\left( \begin{array}{cc} \tau & n \sigma \\ \sigma & \tau \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} \tau x + n \sigma y \\ \sigma x + \tau y \end{array} \right).$$

This 2 by 2 matrix is called an automorph of the quadratic form.

Every indefinite form $f(x,y) = a x^2 + b x y + c y^2$ where $\Delta = b^2 - 4 a c$ is positive but not a square, has such an automorph, leading to infinitely many solutions. Indeed, given $\tau^2 - \Delta \sigma^2 = 4,$ we get

$$\left( \begin{array}{cc} \frac{\tau - b \sigma}{2} & a \sigma \\ -c \sigma & \frac{\tau + b \sigma}{2} \end{array} \right) \left( \begin{array}{cc} a & \frac{b}{2} \\ \frac{b}{2} & c \end{array} \right) \left( \begin{array}{cc} \frac{\tau - b \sigma}{2} & -c \sigma \\ a \sigma & \frac{\tau + b \sigma}{2} \end{array} \right) = \left( \begin{array}{cc} a & \frac{b}{2} \\ \frac{b}{2} & c \end{array} \right).$$ Therefore, if we have $a x^2 + b x y + c y^2 = k,$ we have another with $$\left( \begin{array}{cc} \frac{\tau - b \sigma}{2} & -c \sigma \\ a \sigma & \frac{\tau + b \sigma}{2} \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} \frac{\tau - b \sigma}{2} x - c \sigma y \\ a \sigma x + \frac{\tau + b \sigma}{2} y \end{array} \right).$$

For previous answers in which I show how to use an automorph, see Solve the Diophantine equation $3x^2 - 2y^2 =1$

How to find solutions of $x^2-3y^2=-2$?

Books: H.E.Rose, A Course in Number Theory, chapter 9, section 3, especially pages 162-164 in the first edition.

Thomas W. Cusick and Mary E. Flahive, The Markoff and Lagrange Spectra appendix 3 on pages 91-92.

Duncan A. Buell, Binary Quadratic Forms chapter 3, section 2, pages 31-34.

William J. LeVeque, Topics in Number Theory, volume 2, pages 24-29. The two volumes are available as a one volume paperback, LeVeque Book

Leonard Eugene Dickson, Introduction to the Theory of Numbers, especially pages 111-112.

-
I'm not really sure what you're doing, never seen this before. – Coffee_Table Apr 9 '13 at 21:24
@Coffee_Table, I'm editing in some previous problems where I did this, some books. – Will Jagy Apr 9 '13 at 21:44
how lovely, nice resources. – Coffee_Table Apr 9 '13 at 21:51

See Wikipedia on Pell's equation, also MathWorld.

If there's one solution with $x,y\ge1$ then see Brahmagupta's method or the section "Additional solutions from the fundamental solution."

If $(x_1,y_1)$ and $(x_2,y_2)$ are solutions then $(x_1 x_2+n y_1 y_2,x_1y_2+x_2y_1)$ is another larger solution.

If $n$ is not a square then there's always a solution (and hence infinitely many), see MathWorld for how you can find it from a continued fraction expansion.

For $x^2-ny^2=k$ the same argument can get you infinitely many solutions given a fundamental one, but whether or not one exists is more complicated.

-