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?
 A: 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.
A: 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.
