Proof that the equation $x^2 - 3y^2 = 1$ has infinite solutions for $x$ and $y$ being integers I have seen the Pell's equation wiki page but I need to prove this from scratch without mentioning any formula. I have also seen multiple answers on this site but the answers tend to skip over and assume formulas.
This is what people do -> $x^2 - 3y^2 = 1$ has solution 1, 0.
Next they say we "observe" that $$(x',y') = (2x + 3y, x + 2y)$$ is also a solution.
What I'm asking is how they get this value. Can someone help?
 A: I see a couple issues that may prove to be stumbling blocks. First you might have had problems verifying the solution $\,(\bar x,\bar y) = (2x+3y,x+\color{#c00}3y)\,$ because it is incorrect: the $\color{#c00}3$ should be $2.\,$ Now one can may verify that $\,(\bar x,\bar y)\,$ is also a solution using no more than simple integer arithmetic
$$\begin{eqnarray} 
\bar x^2 &=&\quad\ (2x+3y)^2 &=&\,\ \ \ 4x^2\,+\ 9y^2 +\, 12xy\\
-3\,\bar y^2&=&-3(x^2+2y)^2 &=&\, -3x^2-12y^2-12xy \\
\hline
\bar x ^2 -\, 3\bar y^2&& &=& \ \ \ \ x^2\ -\ 3y^2 =\, 1
\end{eqnarray}\qquad\qquad  $$
Though some explanations of the genesis of this composition law on the solution space may utilize ideas that you have not yet learned (such as the multiplicativity of the norm map on quadratic felds), the above direct proof that $\,(\bar x, \bar y)\,$ is a solution does not require such methods. Rather, it is a simple calculation using only integer arithmetic.
Said composition law is a special case of the fact that one may compose (multiply) any two solutions using the Brahmagupta–Fibonacci identity below. Above is the special case $\,a,b = 2,1.$
$$\begin{eqnarray} (a^2-3b^2)(x^2-3y^2) &\,=\,& (ax+3by)^2- 3(ay+bx)^2\\
(a+b\sqrt{3})(x+y\sqrt{3})\, &\,=\,& \ \,ax+3by\ \ +\,\ \  (ay+bx)\sqrt{3}
\end{eqnarray}\qquad$$
Again, though the composition law may be intuitively derived by taking the norm of the quadratic integers listed below it, you can verify the integer identity above it using only integer arithmetic - independent of "irrational" numbers, quadratic fields, norms, etc.
A: Based on a similar result I know for $x^2 -2y^2 = 1$, I would bet solid gold it falls out of abstract algebra in the study of the ring $\mathbb{Z}[\sqrt{3}] = \{ a + \sqrt{3}b \ | \ a, b \in \mathbb{Z} \}$.
We define a function $N: \mathbb{Z}[\sqrt{3}] \to \mathbb{Z}$ modeled on the complex norm, which multiplies a number by its complex conjugate.
$N(x + \sqrt{3}y) := (x +\sqrt{3}y)(x - \sqrt{3}y) = x^2 -3y^2$
Now, it just so happens that this shares a nice property of the complex norm.
For any two elements $z, w \in \mathbb{Z}[\sqrt{3}]$ we have $N(zw) = N(z)N(w)$. This isn't difficult to prove, just do the computation.
So, say we have some $x + \sqrt{3}y = z \in \mathbb{Z}[\sqrt{3}]$ with $N(z) = x^2 -3y^2 = 1$. It's easy to check that $(2, 1)$ is also a solution, and hence $N(2 + \sqrt{3}) = 1$.
Now we have $1 = N(z)N(2 + \sqrt{3}) = N((x + \sqrt{3}y)(2 + \sqrt{3})) = N((2x+3y) + \sqrt{3}(x + 2y))$.
But $N((2x+3y) + \sqrt{3}(x + 2y)) = 1$ means that $(2x+3y, x + 2y)$ is a solution.
If your initial values for x and y are both positive, then the solution they generate must be larger, so each new solution must be distinct.
A: The way I think about the Pell equation is like this:
$x^2 - 3y^2$ is an integer and it can't be $0$ because $\sqrt 3$ is irrational. So closest it can be to $0$ is $1$ (or $-1$, the other variant for Pell equation).
This leads us to search for good rational approximations for $\sqrt 3$. These we get from the continued fraction expansion of $\sqrt 3$.
All the solution of the Pell equation come from the continued fraction expansion. Now, since the expansion is periodic for $\sqrt d$ (general $d$ in Pell equation), we can derive a formula for the solutions.
A: In algebraic number theoretic terms, this means that there are infinitely many units in $\mathbb{Z}[\sqrt{3}]$. I'm hardly an expert on algebraic number theory (I only know that I know nothing), but I do know how to get this result using its basic methods (usually found in the first two or three chapters of most algebraic number theory textbooks).
This limited knowledge of the topic makes me want to start with $x = 2$, $y = 1$ as a prototypical solution rather than $x = 1$, $y = 0$. Verify that $2^2 - 3 \times 1^2 = 1$. Also verify that $(2 - \sqrt{3})(2 + \sqrt{3}) = 1$.
What if instead of multiplying $(2 + \sqrt{3})$ by $(2 - \sqrt{3})$ we multiply it by itself? We get $(2 + \sqrt{3})^2 = 7 + 4\sqrt{3}$. Notice that $7^2 - 3 \times 4^2 = 1$, and also notice that $(7 - 4\sqrt{3})(7 + 4\sqrt{3}) = 1$. And then $(2 + \sqrt{3})(7 + 4\sqrt{3}) = 26 + 15\sqrt{3}$, $26^2 - 3 \times 15^2 = 1$, $(26 - 15\sqrt{3})(26 + 15\sqrt{3}) = 1$.
What's going on here is that $2 + \sqrt{3}$ is a unit with a norm of 1. The norm is multiplicative, so if we multiply a number with a norm of 1 by any number that also has a norm of 1, the product will also have a norm of 1. And since this multiplication can be carried on infinitely, this means we can obtain as many numbers with a norm of 1 as we can calculate.
But... is computing $(2 + \sqrt{3})^n = x + y\sqrt{3}$ the most efficient way to get more pairs of $x$ and $y$? Is there some kind of pattern we could exploit to obtain new values of $x$ and $y$ without having to invoke irrational numbers at all? So far we've obtained the first four values of two sequences: 1, 2, 7, 26; and 0, 1, 4, 15.
Can we figure out an obvious pattern for these two sequences? $x_1 = 1$, $x_2 = 2$, $x_n = 4x_{n - 1} - x_{n - 2}$; and $y_1 = 0$, $y_1 = 1$, $y_n = 4y_{n - 1} - y_{n - 2}$. Maybe this works, maybe it doesn't work, but regardless it would be better to figure out something in which the $x$ and $y$ are dependent on each other. With trial and error, and a little cleverness, we might figure out $x_n = 2x_{n - 1} + 3y_{n - 1}$ and $y = x_{n - 1} + 2y_{n - 1}$.
So, for example, plugging in $x_4 = 26$ and $y_4 = 15$ gives us $x_5 = 97$ and $y_5 = 56$. Let's check that this worked correctly: $97^2 - 3 \times 56^2 = 9409 - 3 \times 3136 = 9409 - 9408 = 1$; $(97 - 56\sqrt{3})(97 + 56\sqrt{3}) = 1$.

If you're still reading, I'd like to throw a couple more algebraic number theory concepts at you. A fundamental unit (what could be called the "prototypical" unit) can be proper or improper, meaning that its norm is 1 or $-1$. In $\mathbb{Z}[\sqrt{3}]$, it's proper. In $\mathbb{Z}[\sqrt{2}]$, it's improper: $(1 - \sqrt{2})(1 + \sqrt{2}) = -1$. This tells us that both $x^2 - 2y^2 = 1$ and $2y^2 - x^2 = 1$ have infinitely many solutions in integers. But, depending on how we go about it, solutions for one equation would alternate with solutions for the other.
A: More generally,
$(u^2-dv^2)(x^2-dy^2)
=(ux+dvy)^2-d(uy+vx)^2
$.
So
$(x^2-dy^2)^2
=(x^2+dy^2)^2-d(2xy)^2
$.
(Another totally unoriginal answer)
