Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
You need to assume that $n$ is not a perfect square –  Cocopuffs Apr 9 '13 at 21:03
4  
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
1  
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 2

up vote 3 down vote accepted

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.

share|improve this answer
1  
I'm not really sure what you're doing, never seen this before. –  Coffee_Table Apr 9 '13 at 21:24
1  
@Coffee_Table, I'm editing in some previous problems where I did this, some books. –  Will Jagy Apr 9 '13 at 21:44
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.