# Help answering Pell Equation questions

I understand the Pell equation is $$x^{2}-dy^{2}=1$$ However I don't understand how to use this to get $(x,y)$ for these questions.

1) Find a nontrivial solution of $x^{2} − 3y^{2} = 1.$

2) Find all positive solutions of $x^{2} − 3y^{2} = 1.$

Do I use the fact $\frac{x}{y}=\sqrt{\frac{1}{y^{2}}+3} \rightarrow 3$ then try and find some kind of answer from there?

I don't understand how to find the solutions. Any help would be appreciated thank you.

Here is a method that uses just integers. It is equivalent to continued fractions. However, when very large numbers are involved, the methods of Lagrange and Gauss are preferable as they make no use of decimal accuracy or cycle detection. The first nontrivial answer is $2^2 - 3 \cdot 1^2 = 1.$ To get from one solution $(x,y)$ to the next one, we apply the mapping $$(x,y) \mapsto (2x +3y, x + 2y).$$ That is, we get pairs $$(2,1); (7,4); (26,15);(97,56), \ldots$$ The Cayley-Hamilton Theorem from linear algebra tells us degree two linear recursions that are separate for $x$ and $y,$ those being $$x_{n+1} = 4 x_{n+1} - x_n,$$ $$y_{n+1} = 4 y_{n+1} - y_n.$$ The $x$ values, in order, are thus $$2, 7, 26, 97, 362, 1351, 5042, \ldots$$ $$1, 4, 15, 56, 209, 780, 2911, \ldots$$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell 3 0 form 1 2 -2 delta -1 1 form -2 2 1 delta 2 2 form 1 2 -2 disc 12 Automorph, written on right of Gram matrix: 1 2 1 3 Pell automorph 2 3 1 2 Pell unit 2^2 - 3 * 1^2 = 1 ========================================= 3 3 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


CAUTION: if you have $x^2 - d y^2 = c,$ there may be the need for more than on "seed" value, see If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution.

All the solutions are obtained finding first the fundamental unit of the ring of integers of the field $\mathbb Q(\sqrt d)$, say $a_0+b_0\sqrt d$, and then all the solutions $(a_n,b_n)$ are given by $$a_n+b_n\sqrt d=(a_0+b_0\sqrt d)^n$$ (I did not know the way you give).

• And the fundamental solution can be found by calculating the convergents to the continued fraction expansion of $\sqrt{d}$. en.wikipedia.org/wiki/… – Aritra Das Apr 14 '16 at 15:22
• @Aritra Das: Another way is remarking in the given equation of all solutions that $b_{n+1}=a_0b_n+b_0a_n$ and that the sequence $\{b_n\}$ is increasing (strictly) so you can write successively the integers $db^2$ with $b>1$, and stop at the first of these integers whose difference of a square $a_0^2$ is $\pm 1$. In this case, $a_0+b_0\sqrt d$ is the searched fundamental unit. An example given by Pierre Samuel in his classic book on algebraic number theory is $d=7$ so you have the numbers $db^2$ $7,28,63=8^2-1$ Hence you have $a_0+b_0\sqrt 7=8+3\sqrt 7$. – Piquito Apr 14 '16 at 15:58
• @Aritra Das: You can try with $\mathbb Q[\sqrt 2]$ finding $1+\sqrt 2$.(it was too long the other comment to put this exercise of verification) – Piquito Apr 14 '16 at 15:59
• Ohh wow! This method is very nice. I'll be sure to use it. Thank you very very much! – Aritra Das Apr 14 '16 at 16:02