questo metodo è conosciuto per risolvere l'equazione di Pell X^2-dY^2=-1 con l'algoritmo di Euclide generalizzato

[P_1_6]

Come risolvere l'equazione di Pell $X^2-dY^2=-1$ con l'algoritmo di Euclide generalizzato.

La condizione per questa risoluzione è che $d$ sia dispari e si possa scrivere nella forma $(a^2+b^2)$ conoscendo $a$ e $b$

$X=(a*x+b*y)$ ed $Y^2=(x^2+y^2)$

$1+(a*x+b*y)^2=3293*(x^2+y^2)^2$ , $1=a*y-b*x$

$b*x-a*y+1=0$ risolvendo con l'algoritmo di Euclide generalizzato si ottengono le soluzioni



Esempio

$x^2-3293*y^2=-1$ ; $3293=(53^2+22^2)$

$1+(53*x+22*y)^2=3293*(x^2+y^2)$ , $1=53*y-22*x$

$22*x-53*y+1=0$

Troviamo il massimo comun divisore $MCD( 22, -53) = 1$.

il massimo comun divisore è $1$ quindi non dobbiamo dividere l'equazione

applichiamo l'algoritmo di Euclide generalizzato

Step $1$: $1 * 22 + 0 * (-53) = 22$
Step $2$: $0 * 22 + 1 * (-53) = -53$
Step $3$: $1 * 22 + 1 * (-53) = -31$
Step $4$: $(-1) * 22 + 0 * (-53) = -22$
Step $5$: $2 * 22 + 1 * (-53) = -9$
Step $6$: $(-5) * 22 + (-2) * (-53) = -4$
Step $7$: $12 * 22 + 5 * (-53) = -1$

$x = 12 + 53 t$
$y = 5 + 22 t$

per $t=0$

quindi la soluzione sarà $X=(a*x+b*y)=746$ ed $Y^2=(x^2+y^2)=169$

$746^2-3293*13^2=-1$