# 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?

-
One gets the value by multiplication, $$(x+y\sqrt{3})(2+\sqrt{3}) = 2x+3y + (x+2y)\sqrt{3}.$$ How to see that without recourse to algebraic concepts that are probably beyond what you may use, I don't know, however. – Daniel Fischer Jan 23 '14 at 14:37
@Greevil Have you seen en.wikipedia.org/wiki/Brahmagupta%27s_identity ? It's unclear to me what you mean by "skip over and assume formulas". Might you be harboring the misconception that every step in a proof must be blindly mechanical? Proofs can be original and unexpected: it's fine to introduce new quantities, as long as you verify that they work. – Erick Wong Jan 23 '14 at 14:39
One of the requirements to this question in my Homework, I cant use Formulas, especially ones I cannot, as you put it, blindly mechanically prove – Greevil Jan 23 '14 at 14:41
@Greevil I cannot speak to your instructor's expectations, but this isn't how proofs work. There is nothing incomplete about verifying that $(2x+3y,x+3y)$ is a solution (by mechanically multiplying it out) without finding a deeper explanation of its origins. Please clarify the exact restrictions, else no one can help (and add the homework tag). – Erick Wong Jan 23 '14 at 15:09

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.

-
Gotta say thats a great way I never thought of. And Ill just edit the question, goodness knows maybe all this trouble was just because I copied 3 as 2... thank you :) – Greevil Jan 24 '14 at 9:46

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.

-
Im sorry but ring $z[√3]$?... rest I can mostly understand – Greevil Jan 23 '14 at 15:01
@Greevil Since I don't use any ring properties it's not necessary information - just think of it like any other set. – G. H. Faust Jan 23 '14 at 15:05
Okay :) Thanks, this is the closest to the answer I was looking for, will make this accepted after a day or two unless I get something better. – Greevil Jan 23 '14 at 15:14
Note that $N(zw) = N(z)N(w)$ is Brahmagupta's identity stated in ring-theoretic terms :). – Erick Wong Jan 23 '14 at 15:20
It suffices to show that absolute value $|x+y\sqrt d|=v\neq 1$. Then $|(x+y\sqrt d)^n|=v^n$ is always decreasing or increasing, so they must be distinct. The first part is clear, since $\sqrt d$ is irrational (unless $y=0$ corresponding to the trivial solutions $(\pm 1,0)$). Such an $u+v\sqrt d$ exists by Dirichlet's unit theorem: for real quadratic field all units are of the form $\pm \eta^n$ for some $|\eta|\neq 1$. This also explains why we find all solutions just by computing $\pm(u+v\sqrt d)^n$. – Yong Hao Ng Jan 24 '14 at 17:42

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.

-

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.

-

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)

-