Una maledetta equazione di Pell
Sto cercando di risolvere questa equazione da ieri sera con il metodo delle frazioni continue, e, mentre tutte le altre mi hanno dato, questa proprio no... Potreste risolvermela (possibilmente passaggio per passaggio)?
$ x^2-125y^2 =1 $
$ x^2-125y^2 =1 $
Risposte
Non mi trovo nemmeno io. Forse in qualche caso il metodo tradizionale non funziona, o forse sono semplicemente io che non ci riesco.
Non vado fiero del mio modo di risolverla, ma eccolo:
Ovviamente tralasciamo le soluzioni banali $x = pm 1$ e $y = 0$
Sviluppiamo $sqrt(125)$ in frazione continua: $[11, \bar(5, 1, 1, 5, 22)]$.
Consideriamo ora le convergenze $A_(2n+1)/B_(2n+1)$.
[list=0]
[*:2nov6c0h] $11/1$[/*:m:2nov6c0h]
[*:2nov6c0h] $56/5 => 56^2-125*5^2 = 11$[/*:m:2nov6c0h]
[*:2nov6c0h] $67/6$[/*:m:2nov6c0h]
[*:2nov6c0h] $123/11 => 123^2-125*11^2 = 4$[/*:m:2nov6c0h]
[*:2nov6c0h] $682/61$[/*:m:2nov6c0h]
[*:2nov6c0h] $15127/1353 => 15127^2 - 125*1353^2 = 4$[/*:m:2nov6c0h]
[*:2nov6c0h] $76317/6826$[/*:m:2nov6c0h]
[*:2nov6c0h] $91444/8179 => 91444^2 - 125*8179^2 = 11$[/*:m:2nov6c0h]
[*:2nov6c0h] $167761/15005$[/*:m:2nov6c0h]
[*:2nov6c0h] $930249/83204 => 930249^2 - 125*83204^2 = 1$[/*:m:2nov6c0h][/list:o:2nov6c0h]
Quindi abbiamo le soluzioni $x=pm 930249,\ y=pm 83204$.
Ovviamente tralasciamo le soluzioni banali $x = pm 1$ e $y = 0$
Sviluppiamo $sqrt(125)$ in frazione continua: $[11, \bar(5, 1, 1, 5, 22)]$.
Consideriamo ora le convergenze $A_(2n+1)/B_(2n+1)$.
[list=0]
[*:2nov6c0h] $11/1$[/*:m:2nov6c0h]
[*:2nov6c0h] $56/5 => 56^2-125*5^2 = 11$[/*:m:2nov6c0h]
[*:2nov6c0h] $67/6$[/*:m:2nov6c0h]
[*:2nov6c0h] $123/11 => 123^2-125*11^2 = 4$[/*:m:2nov6c0h]
[*:2nov6c0h] $682/61$[/*:m:2nov6c0h]
[*:2nov6c0h] $15127/1353 => 15127^2 - 125*1353^2 = 4$[/*:m:2nov6c0h]
[*:2nov6c0h] $76317/6826$[/*:m:2nov6c0h]
[*:2nov6c0h] $91444/8179 => 91444^2 - 125*8179^2 = 11$[/*:m:2nov6c0h]
[*:2nov6c0h] $167761/15005$[/*:m:2nov6c0h]
[*:2nov6c0h] $930249/83204 => 930249^2 - 125*83204^2 = 1$[/*:m:2nov6c0h][/list:o:2nov6c0h]
Quindi abbiamo le soluzioni $x=pm 930249,\ y=pm 83204$.
Grazie. Si doveva perseverare fino al diciannovesimo convergente.
Non capisco però perché debba andare così avanti (abbiate pazienza, sono solo in terza superiore)
Non conosco il metodo delle frazioni continue, ma porre [tex]z=5y[/tex] non aiutava?
"Martino":
Non conosco il metodo delle frazioni continue, ma porre [tex]z=5y[/tex] non aiutava?
In effetti...
@Xavi96 La piu' piccola soluzione non banale dell'equazione $x^2-dy^2=1$ di Pell
cresce piu' o meno come $\exp(\sqrt{d})$, quando $d\rightarrow+\infty$. Quindi
solo per scriverla ci vogliono $\sqrt(d)$ cifre. Non esiste quindi un algoritmo che
produce la piu' piccola soluzione in tempi essenzialmente piu' brevi.
Visto che il numero di passi dell'algoritmo delle frazioni continue
cresce anche come $\sqrt{d}$, c'e' poco da fare nel caso generale $\ldots$.
Pero', esistono algoritmi molto migliori che in un certo senso producono una soluzione
scritta in modo "economico". Questi algoritmi sfruttano il fatto che l'insieme dei numeri
$\{x+y\sqrt{d}: x,y\in ZZ\ e\ x^2-dy^2=1\}$ e' un gruppo. Questo fatto permette di "saltare"
la stramaggioranza dei passi del algoritmo delle frazioni continue. Si veda
http://www.ams.org/notices/200202/fea-lenstra.pdf
Nel caso $x^2-125y^2 = 1$ pero', tutto questo non e' molto rilevante.
Come dice @Martino, va usato il fatto che $125$ e' divisibile per il quadrato $25$.
Sia $d=5$. Basta esibire $x+y\sqrt{5}$ con $x,y\in ZZ$ e $y$ divisibile per $5$.
E' utile introdurre la norma $N(x+y\sqrt{5})=(x+y\sqrt{5})(x-y\sqrt{5})=x^2-5y^2$.
Trovare la piu' piccola soluzione per $d=5$ e' facile: Il numero $2+\sqrt{5}$ ha
norma $x^2-5y^2=-1$. Il suo quadrato $(2+\sqrt{5})^2=9+4\sqrt{5}$ ha quindi norma $+1$.
Per trovare un numero $x+y\sqrt{5}$ di norma $+1$ con $y$ divisibile per $5$ prendiamo
la quinta potenza. In questo modo ritroviamo la soluzione
$(9+4\sqrt{5})^5=930249+416020\sqrt{5}$ di @PIanoth.
cresce piu' o meno come $\exp(\sqrt{d})$, quando $d\rightarrow+\infty$. Quindi
solo per scriverla ci vogliono $\sqrt(d)$ cifre. Non esiste quindi un algoritmo che
produce la piu' piccola soluzione in tempi essenzialmente piu' brevi.
Visto che il numero di passi dell'algoritmo delle frazioni continue
cresce anche come $\sqrt{d}$, c'e' poco da fare nel caso generale $\ldots$.
Pero', esistono algoritmi molto migliori che in un certo senso producono una soluzione
scritta in modo "economico". Questi algoritmi sfruttano il fatto che l'insieme dei numeri
$\{x+y\sqrt{d}: x,y\in ZZ\ e\ x^2-dy^2=1\}$ e' un gruppo. Questo fatto permette di "saltare"
la stramaggioranza dei passi del algoritmo delle frazioni continue. Si veda
http://www.ams.org/notices/200202/fea-lenstra.pdf
Nel caso $x^2-125y^2 = 1$ pero', tutto questo non e' molto rilevante.
Come dice @Martino, va usato il fatto che $125$ e' divisibile per il quadrato $25$.
Sia $d=5$. Basta esibire $x+y\sqrt{5}$ con $x,y\in ZZ$ e $y$ divisibile per $5$.
E' utile introdurre la norma $N(x+y\sqrt{5})=(x+y\sqrt{5})(x-y\sqrt{5})=x^2-5y^2$.
Trovare la piu' piccola soluzione per $d=5$ e' facile: Il numero $2+\sqrt{5}$ ha
norma $x^2-5y^2=-1$. Il suo quadrato $(2+\sqrt{5})^2=9+4\sqrt{5}$ ha quindi norma $+1$.
Per trovare un numero $x+y\sqrt{5}$ di norma $+1$ con $y$ divisibile per $5$ prendiamo
la quinta potenza. In questo modo ritroviamo la soluzione
$(9+4\sqrt{5})^5=930249+416020\sqrt{5}$ di @PIanoth.
Grazie mille, molto gentile... Come detto sono solo in terza superiore, e mi sto avvicinando a questi argomenti solo per passione e interesse, per cui più dispense ricevo meglio è.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo