Równanie Pella

Z Wikipedii

Równanie Pella jest równaniem diofantycznym postaci

$x^2-Dy^2=1\,$

gdzie $D$ jest liczbą całkowitą dodatnią. Równanie to dla $D$ będącego kwadratem liczby całkowitej posiada jedynie rozwiązania $(1,0)$ oraz $( - 1,0)$ , zaś dla $D$ nie będącego kwadratem liczby całkowitej posiada nieskończenie wiele rozwiązań.

Dla $D = n 2$ , gdzie $n\in\mathbb Z$ otrzymujemy równanie $x 2 - n 2 y 2 = 1$ , czyli $(x - n y)(x + n y) = 1$ , co jak łatwo zauważyć faktycznie w liczbach całkowitych posiada jedynie rozwiązania $(1,0)$ oraz $( - 1,0)$ .

Dla $D$ nie będącego kwadratem liczby całkowitej istnieje algorytm konstruujący nieskończenie wiele rozwiązań.

[edytuj] Znajdowanie rozwiązań

Niech $\frac{l_n}{m_n}$ będzie ciągiem ułamków łańcuchowych dla liczby $\sqrt D$ . Sprawdzamy pary liczb $(l n, m n)$ aż któraś z nich będzie spełniać równanie Pella, taki moment nastąpi o ile $D$ nie jest kwadratem liczby całkowitej (teraz tego nie będę dowodzić). Z tej pary liczb (oznaczmy ją jako $(x 1, y 1)$ ) można wygenerować nieskończenie wiele innych (istotne jest to, że w tej parze $y_1\neq 0$ , w przeciwnym razie jako parę początkową można by brać parę $(1,0)$ ).

Zauważmy, że skoro $x_1^2-Dy_1^2=1$ , to $(x_1-y_1\sqrt{D})(x_1+y_1\sqrt{D})=1$ . Oznaczmy przez $x n$ i $x n$ liczby spełniające równanie $(x_1+y_1\sqrt{D})^n=x_n+y_n\sqrt{D}$ . Wówczas spełnione będzie równanie $(x_1-y_1\sqrt{D})^n=x_n-y_n\sqrt{D}$ , gdyż współczynnik całkowity wyrażenia po lewej stronie pozostanie taki sam jak był, a współczynnik przy $\sqrt{D}$ jedynie zmieni znak. Zatem

$x_n^2-Dy_n^2=(x_n+y_n\sqrt{D})\cdot (x_n-y_n\sqrt{D})=(x_1+y_1\sqrt{D})^n\cdot (x_1-y_1\sqrt{D})^n=(x_1^2-Dy_1^2)^n=1^n=1$ .

Z pewnością pary $(x n, y n)$ są parami różne (gdyż $x_1+y_1\sqrt{D}\neq 1$ ), a zatem istotnie dostajemy nieskończenie wiele różnych rozwiązań równania Pella.

[edytuj] Przykład

Znajdźmy kilka rozwiązań równania Pella dla $D = 3$ . Generowane ułamki łańcuchowe to $\frac{1}{1},\frac{2}{1},\frac{5}{3},\ldots$ . Już para $(x, y) = (2,1)$ spełnia równanie $x 2 - 3 y 2 = 1$ . Mamy zatem $(x 1, y 1) = (2,1)$ .

Podnosimy więc do kolejnych potęg wyrażenie $(2+\sqrt 3)$ . Mamy zatem:

$(2+\sqrt 3)^2=7+4\sqrt 3, (x_2,y_2)=(7,4)$ , faktycznie $7^2-3\cdot 4^2=49-3\cdot 16=1$
$(2+\sqrt 3)^3=26+15\sqrt 3, (x_3,y_3)=(26,15)$ , faktycznie $26^2-3\cdot 15^2=676-3\cdot 225=1$