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 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 Im asking is how they get this value. Can someone help?

share|improve this question
    
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 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 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 at 14:41
2  
@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 at 15:09

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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 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.

share|improve this answer
    
Im sorry but ring $z[√3]$?... rest I can mostly understand –  Greevil Jan 23 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 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 at 15:14
1  
Note that $N(zw) = N(z)N(w)$ is Brahmagupta's identity stated in ring-theoretic terms :). –  Erick Wong Jan 23 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 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.

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.