7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Iwillnotexist Idonotexist Jul 4 '16 at 4:23
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ any other solution which not consists any recurrence relation. $\endgroup$ – user157835 Jul 3 '16 at 20:40
  • $\begingroup$ @user157835 This reccurence relation gives us all the solutions. $\endgroup$ – Stefan4024 Jul 3 '16 at 20:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Will Jagy Jul 3 '16 at 22:18
  • 2
    $\begingroup$ @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$. $\endgroup$ – Stefan4024 Jul 3 '16 at 22:21
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Oop, my answer is redundant with yours... but maybe I'll leave it, nevertheless, ... $\endgroup$ – paul garrett Jul 3 '16 at 21:15
  • $\begingroup$ Yes but your English is much better than mine which is very bad (without Google translator I am death). Regards. $\endgroup$ – Piquito Jul 3 '16 at 23:01
  • $\begingroup$ We will not mention my non-existent Spanish... Best regards! $\endgroup$ – paul garrett Jul 3 '16 at 23:03
  • $\begingroup$ 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.) $\endgroup$ – Piquito Jul 3 '16 at 23:43
  • $\begingroup$ Tous va bien. :) $\endgroup$ – paul garrett Jul 4 '16 at 3:08
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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:~$ 
| cite | improve this answer | |
$\endgroup$

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.