# Why does the same convergent (relative to the period) of the continued fraction of $\sqrt{n}$ give solutions to the Pell equation?

Let $n$ be a natural number which isn't a square and $$\sqrt{n}=[a_0;\overline{a_1,a_2\dotsb a_r}]$$

then consider the convergents

$$\frac{x_1}{y_1}=[a_0;a_1,a_2\dotsb a_{r-1}]$$

$$\frac{x_2}{y_2}=[a_0;a_1,a_2\dotsb a_{r-1},a_r,a_1\dotsb a_{r-1}]$$

etc

I conjecture that $x_k^2-ny_k^2=\pm 1$. And that all solutions of the positive and negative Pell equations have this form.

If $p^2-nq^2=1$ then $0<\frac{p}{q}-\sqrt{n}<\frac{1}{2\sqrt{n}q^2}$. And if $p^2-nq^2=-1$ then $0<\sqrt{n}-\frac{p}{q}<\frac{1}{2\sqrt{n}q^2}$. In both cases $q^2\left|\frac{p}{q}-\sqrt{n}\right|<\frac{1}{2\sqrt{n}}$, so $\frac{p}{q}$ is in some sense a very good approximation of $\sqrt{n}$, and the last number in the period, $a_r$ seems to always be $2\lfloor\sqrt{n}\rfloor$ and larger than all of $a_1,a_2\dotsb a_{r-1}$, so the next best rational approximation of $\sqrt{n}$ would have a "much" bigger denominator than $q$, so it should make sense for the solutions to the Pell equation to appear before $a_r$.

$$\sqrt{397}=[19;\overline{1,12,3,4,9,1,2,1,2,1,1,2,1,2,1,9,4,3,12,1,38}]$$

$$\frac{20478302982}{1027776565}=[19;1,12,3,4,9,1,2,1,2,1,1,2,1,2,1,9,4,3,12,1]$$

This is the fundamental solution of the negative Pell equation $$20478302982^2-397\times 1027776565^2=-1$$

Getting the second convergent of this type $$\frac{838721786045180184649}{42094239791738433660}=[19;1,12,3,4,9,1,2,1,2,1,1,2,1,2,1,9,4,3,12,1,38,1,12,3,4,9,1,2,1,2,1,1,2,1,2,1,9,4,3,12,1]$$

Gives the fundamental solution to the positive Pell equation

$$838721786045180184649^2-397\times 42094239791738433660^2=1$$

It is hard not to prove by induction that the convergents of this form alternate between generating solutions to the positive and negative equations, although very laborious. I have also proven this for the first 20 naturals, 61, and 92. So that's a bit of computational evidence. Heuristically it seems far too unlikely that the conjecture isn't true.

If the conjecture is true then the numbers for which the negative Pell equation has a solution are those with an even number of numbers in their period, in particular primes congruent to 1 mod 4.

If $$u^2 - n v^2 = -1,$$ then $$(u^2 + n v^2 )^2 - n (2uv)^2 = 1.$$
The bit about the continued fraction "digits" being palindromic is true. Known to Lagrange, explicit in some things by Galois. The relationship with $x^2 - n y^2 = -1$ comes down to this: if it is possible, it happens at the end of one, umm, cycle. Another cycle takes us back to $x^2 - n y^2 = 1.$ A short proof that this is always possible for primes $n \equiv 1 \pmod 4$ is in Mordell, Diophantine Equations. The same proof applies when $n = pq,$ primes $p \equiv q \equiv 1 \pmod 4,$ AND Legendre symbol $(p|q) = (q|p) = -1,$ that is, they are mutual quadratic non-residues. Howeve, look at $n = 205$ or $n = 221,$ for which $x^2 - n y^2 = -1$ is impossible:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell 205 0 form 1 28 -9 delta -3 1 form -9 26 4 delta 6 2 form 4 22 -21 delta -1 3 form -21 20 5 delta 4 4 form 5 20 -21 delta -1 5 form -21 22 4 delta 6 6 form 4 26 -9 delta -3 7 form -9 28 1 delta 28 8 form 1 28 -9 disc 820 Automorph, written on right of Gram matrix: 881 24948 2772 78497 Pell automorph 39689 568260 2772 39689 Pell unit 39689^2 - 205 * 2772^2 = 1 ========================================= 4 PRIMITIVE 43^2 - 205 * 3^2 = 4 ========================================= 205 5 * 41 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell 221 0 form 1 28 -25 delta -1 1 form -25 22 4 delta 6 2 form 4 26 -13 delta -2 3 form -13 26 4 delta 6 4 form 4 22 -25 delta -1 5 form -25 28 1 delta 28 6 form 1 28 -25 disc 884 Automorph, written on right of Gram matrix: 97 2800 112 3233 Pell automorph 1665 24752 112 1665 Pell unit 1665^2 - 221 * 112^2 = 1 ========================================= 4 PRIMITIVE 15^2 - 221 * 1^2 = 4 ========================================= 221 13 * 17 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

Mathworld states the interesting inequality $$q_k^2\left|\sqrt{n}-\frac{p_k}{q_k}\right|>\frac{1}{a_{k+1}+2}$$ which is kind of a formalization of the heuristic I gave in the second paragraph. So, using the inequality I gave in the question, if $p_k^2-nq_k^2=\pm 1$ then $$\frac{1}{2\sqrt{n}}>q_k^2\left|\sqrt{n}-\frac{p_k}{q_k}\right|>\frac{1}{a_{k+1}+2}$$ $$a_{k+1}+2>2\sqrt{n}$$ But since $$a_{k+1}<2\sqrt{n}$$ The only values $a_{k+1}$ can take are $\lfloor 2\sqrt{n}\rfloor$ and $\lfloor 2\sqrt{n}\rfloor-1$. Since $a_r=2a_0=2\lfloor \sqrt{n}\rfloor$ then $p_{r-1}^2-nq_{r-1}^2=\pm 1$ indeed.