General solution of Pell's equation

Question

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?

Answer 1

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)$$

Answer 2

$$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)$.

Answer 3

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.

Answer 4

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:~$