1
$\begingroup$

Suppose I have a solution of a Pell's equation $y_1,x_1$, then I can find the subsequent solutions by recursively using the relation $(y_{i},x_{i})=x_{i-1}y_1+y_{i-1}x_1,x_{i-1}x_1+Dy_{i-1}y_1$ i.e. $(x_1+y_1\sqrt{D})^i$. But, if I have ONLY the $i^{th}$ solution, is there a way to get the first solution easily? It is straightforward if $i=2$, but for any number above that, if I solve by Wolfram, the expression for the solution seems to explode. So, is there an easy recursive way to get back the first solution, given the $i^{th}$ solution?

$\endgroup$
  • $\begingroup$ WA gives a clean solution. Note that the denominator is $\pm 1$. $\endgroup$ – lhf Jul 13 '19 at 11:21
  • $\begingroup$ Well, that is for $i=2$ as I mentioned in the original question. For i>2, knowing only the $i^{th}$ solution makes it a painful process to revert. $\endgroup$ – silvestre_dubois Jul 13 '19 at 11:25
0
$\begingroup$

From $$ y_{i}=x_{i-1}y_1+y_{i-1}x_1, \qquad x_{i}=x_{i-1}x_1+Dy_{i-1}y_1 $$ we get $$ x_1 = \frac{x_{i-1} x_{i} - y_{i-1} y_{i} D}{x_{i-1}^2 - y_{i-1}^2 D}, \qquad y_1 = \frac{x_{i-1} y_{i} - x_{i} y_{i-1}}{x_{i-1}^2 - y_{i-1}^2 D} $$ Note that the denominator is $\pm1$.

Therefore, given two consecutive solutions, we can find the first one.

If you're only given $z=x_i+y_i\sqrt{D}=(x_1+y_1\sqrt{D})^i$, then you could take the $i$-th root of $z$ and compare its fractional part with the fractional part of the integer multiples of $\sqrt{D}$. This will give $y_1$ and then $x_1$. But you may need high-precision approximation of $\sqrt{D}$.

$\endgroup$
  • $\begingroup$ The point is I know only the $i^{th}$ solution and nothing else. Therefore, my original question. $\endgroup$ – silvestre_dubois Jul 13 '19 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.