# General solution of Pell's equation

If we know the minimal solution or any specific solution of Pell's equation $x^2-ny^2=1$ , is there is any general formula to write all solution of Pell's equation?

• See Chakravala method, which is what @Stefan4024 describes but didn't give the name for. A very elegant algorithm, discovered by Hindu mathematicians hundreds, nay, a thousand years before European attempts. Fermat and Lagrange could not articulate a comparable algorithm; It really seems that Chakravala is "the right way" to solve Pell's equation. – Iwillnotexist Idonotexist Jul 4 '16 at 4:23

It's well know that the solution of the Pell's equation satisfy the reccurence relation:

$$x_{k+1} = x_1x_k + y_1ny_k$$ $$y_{k+1} = y_1x_k + x_1y_k$$

This was found by Brahmagupta and it holds because:

$$1 = (x_1 - ny_1)(x_k - ny_k) = (x_1x_k + y_1ny_k) - n(y_1x_k + x_1y_k)$$

• any other solution which not consists any recurrence relation. – user157835 Jul 3 '16 at 20:40
• @user157835 This reccurence relation gives us all the solutions. – Stefan4024 Jul 3 '16 at 20:47
• Stefan, if you have a related question $x^2 - n y^2 = T,$ for fixed integer $T,$ you get a finite number of orbits of solutions, under the action you describe. – Will Jagy Jul 3 '16 at 22:18
• @WillJagy Yeah, but I think that's far more than the OP has asked for. Also in the Pell's Equation we always have that $T=1$. – Stefan4024 Jul 3 '16 at 22:21

$$a^2-db^2=\pm1\iff(a+b\sqrt d)(a-b\sqrt d)=\pm1\iff(a\pm b\sqrt d)\text{ are units in } \mathbb Q(\sqrt d)$$Hence the elementary theory of algebraic numbers gives all the solutions $(a_n,b_n)$ are given by the equations $$(a_n+b_n\sqrt d)=(a_0+b_0\sqrt d)^n$$ and $$(a_n+b_n\sqrt d)=2^{1-n}(a_0+b_0\sqrt d)^n$$ according if $d\equiv 2,3\pmod 4$ and $d\equiv 1\pmod 4$ respectively and where $a_0+b_0\sqrt d$ is the fondamental unit of the ring of integers of the quadratic field $\mathbb Q(\sqrt d)$.

• Oop, my answer is redundant with yours... but maybe I'll leave it, nevertheless, ... – paul garrett Jul 3 '16 at 21:15
• Yes but your English is much better than mine which is very bad (without Google translator I am death). Regards. – Piquito Jul 3 '16 at 23:01
• We will not mention my non-existent Spanish... Best regards! – paul garrett Jul 3 '16 at 23:03
• Mais selon votre nom, vous devez bien gérer le français de Descartes et Poincaré, il est pas vrai? Mes meilleurs voeux. (It will be good not answer me this comment.) – Piquito Jul 3 '16 at 23:43
• Tous va bien. :) – paul garrett Jul 4 '16 at 3:08

Another way to understand this is that the solutions $(a,b)$ to $a^2-db^2=1$ are a subgroup of the group of units in the ring $\mathbb Z[\sqrt{d}]$, because the property $a^2-db^2=1$ is the assertion that the Galois norm $N(a+b\sqrt{d})$ of $a+b\sqrt{d}$ is $1$. The Galois norm is multiplicative, meaning that $N(\alpha\cdot \beta)=N(\alpha)\cdot N(\beta)$. It is a very special case of Dirichlet's Units Theorem that the group of such things, disregarding $\pm 1$, is a free abelian group on one generator. That is, everything of norm $1$ in that ring is $\pm(a_o+b_o\sqrt{d})^N$ for one fixed $a_o+b_o\sqrt{d}$ and integer exponent $N$. (This $a_o+b_o\sqrt{d}$ is called the "fundamental unit".)

Then the $a,b$ of solutions to Pell's equation are the rational part and coefficient of the irrational part in that power of the fundamental unit.

Ummm; if you have $u,v$ the smallest positive (nonzero) solution to $u^2 - n v^2 = 1,$ then as in the answer by Stefan4024, all solutions are obtained from the $(1,0)$ solution by the mapping $$(x,y) \mapsto (ux + nvy, \; v x + u y).$$ The Cayley-Hamiltion Theorem says that we can write separate linear recurrences for $x,y.$ That is $$x_0 = 1, x_1 = u, x_2 = 2 u^2 - 1,$$ and $$x_{n+2} = 2 u x_{n+1} - x_n.$$

$$y_0 = 0, y_1 = v, y_2 = 2 u v,$$ and $$y_{n+2} = 2 u y_{n+1} - y_n.$$

The full proof that this gives all solutions is rather long. Maybe I should just draw attention to alternatives. All solutions to $x^2 - 5 y^2 = 6061$ make up a rather more complicated set; in the sense discussed above, there are eight orbits, not just one.

jagy@phobeusjunior:~$./Pell_Target_Fundamental Automorphism matrix: 9 20 4 9 Automorphism backwards: 9 -20 -4 9 9^2 - 5 4^2 = 1 x^2 - 5 y^2 = 6061 Sun Jul 3 14:58:33 PDT 2016 x: 79 y: 6 ratio: 13.1667 SEED KEEP +- x: 81 y: 10 ratio: 8.1 SEED KEEP +- x: 129 y: 46 ratio: 2.80435 SEED KEEP +- x: 159 y: 62 ratio: 2.56452 SEED KEEP +- x: 191 y: 78 ratio: 2.44872 SEED BACK ONE STEP 159 , -62 x: 241 y: 102 ratio: 2.36275 SEED BACK ONE STEP 129 , -46 x: 529 y: 234 ratio: 2.26068 SEED BACK ONE STEP 81 , -10 x: 591 y: 262 ratio: 2.25573 SEED BACK ONE STEP 79 , -6 x: 831 y: 370 ratio: 2.24595 x: 929 y: 414 ratio: 2.24396 x: 2081 y: 930 ratio: 2.23763 x: 2671 y: 1194 ratio: 2.23702 x: 3279 y: 1466 ratio: 2.2367 x: 4209 y: 1882 ratio: 2.23645 x: 9441 y: 4222 ratio: 2.23614 x: 10559 y: 4722 ratio: 2.23613 x: 14879 y: 6654 ratio: 2.2361 x: 16641 y: 7442 ratio: 2.23609 x: 37329 y: 16694 ratio: 2.23607 x: 47919 y: 21430 ratio: 2.23607 x: 58831 y: 26310 ratio: 2.23607 x: 75521 y: 33774 ratio: 2.23607 x: 169409 y: 75762 ratio: 2.23607 x: 189471 y: 84734 ratio: 2.23607 x: 266991 y: 119402 ratio: 2.23607 x: 298609 y: 133542 ratio: 2.23607 x: 669841 y: 299562 ratio: 2.23607 x: 859871 y: 384546 ratio: 2.23607 x: 1055679 y: 472114 ratio: 2.23607 x: 1355169 y: 606050 ratio: 2.23607 x: 3039921 y: 1359494 ratio: 2.23607 x: 3399919 y: 1520490 ratio: 2.23607 x: 4790959 y: 2142582 ratio: 2.23607 x: 5358321 y: 2396314 ratio: 2.23607 x: 12019809 y: 5375422 ratio: 2.23607 x: 15429759 y: 6900398 ratio: 2.23607 x: 18943391 y: 8471742 ratio: 2.23607 x: 24317521 y: 10875126 ratio: 2.23607 Sun Jul 3 14:59:13 PDT 2016 x^2 - 5 y^2 = 6061 jagy@phobeusjunior:~$
jagy@phobeusjunior:~\$