Proof that the equation $x^2 - 3y^2 = 1$ has infinite solutions for $x$ and $y$ being integers

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.