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

Question

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.

Answer 1

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$ 

Answer 2

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.