Pagina 1 di 2

Frazioni continue e equazioni di Pell...

Inviato: 08 feb 2008, 14:44
da piever
Visto che se ne è un po' parlato su questo forum, volevo chiedere a qualche anima pia se mi risolve questo (di)lemma:

è vero che le soluzioni di un'equazione di Pell si ottengono stoppando a un certo punto la frazione continua di $ \sqrt d $? E perché?

E l'antico algoritmo indiano come e perché funziona??

Grazie in anticipo...

ciau!!!


(si lo so che ho sbagliato sezione ma non credo che questa roba sia Teoria di Base e neanche MnE e, spero, nemmeno Birreria...)

Inviato: 09 feb 2008, 11:49
da FrancescoVeneziano
È vero, ma bisogna sapere qual è il punto giusto per "stopparla" :)
Siccome per la dimostrazione servono un po' di cose, proviamo a trasformare il thread in un minicorso sulle frazioni continue, quindi:

Col termine "frazione continua" si intende un'espressione—finita o infinita—della forma$ q_0+\cfrac{1}{q_1+ \cfrac{1}{q_2+ \cfrac{1}{q_3+\dotsb}}} $ che for notation's sake indichiamo con $ \ q_0+\frac{1}{q_1+}\frac{1}{q_2+}\frac{1}{q_3+}\dotsb $.
Data una frazione continua definiamo "convergenti" le frazioni $ q_0+\frac{1}{q_1+}\frac{1}{q_2+}\dotsm\frac{1}{q_m} $ ottenute troncandola prima della fine.

Il nostro primo obbiettivo è trovare un'espressione comoda per i convergenti; data una successione, finita o infinita, $ \ q_0,q_1,\dotsc $ con $ q_0 $ intero e i $ q_i $ interi positivi per $ \ i\geq 1 $, definiamo due successioni nel modo seguente: $ \ A_0=q_0, B_0=1, A_1=q_0q_1+1, B_1=q_1 $ e
$ \ A_m=q_m A_{m-1}+A_{m-2}, \ B_m=q_m B_{m-1}+B_{m-2} $.

Dimostrate ora che

1) $ \ \frac{A_m}{B_m}=q_0+\frac{1}{q_1+}\frac{1}{q_2+}\dotsm\frac{1}{q_m} $

2) $ \ A_m B_{m-1}- B_m A_{m-1}=(-1)^{m-1} $

Inviato: 14 feb 2008, 11:58
da piever
Grazie Francesco per la "dimostrazione guidata" alla mia domanda, cercherò di non snervarti troppo...

Visto che voglio farmi del male (e che nessuno sembra particolarmente interessato a questa roba, come è comprensibile tra persone normali...) ecco delle pseudodimostrazioni ai due lemmini:

1) Dimostriamo che "1)" vale scegliendo $ q_0 $ reale generico e i $ q_i $ (con i>0) reali positivi. Facciamolo per induzione...

Per m=o e m=1 la tesi si verifica facilmente. Assumiamo vera la tesi per m e dimostriamola per m+1. Possiamo usare l'ipotesi induttiva in questo modo: costruiamo la (m+1)-upla (si dice davvero così?) $ p_0,...,p_m $ in questo modo:

$ p_i=q_i $ per i<m e $ p_m=\frac{q_mq_{m+1}+1}{q_{m+1}} $

Ora, chiamiamo $ C_i $ e $ D_i $ la successione dei convergenti della frazione continua generata da questi numeri. (per intenderci, C sarebbe A e D sarebbe B)

$ q_0+\frac{1}{q_1+}\frac{1}{q_2+}\dotsm\frac{1}{q_m+1}=p_0+\frac{1}{p_1+}\frac{1}{p_2+}\dotsm\frac{1}{p_m} $$ =\frac{C_{m}}{D_{m}}=\frac{A_{m-1}\frac{q_mq_{m+1}+1}{q_{m+1}}+A_{m-2}}{B_{m-1}\frac{q_mq_{m+1}+1}{q_{m+1}}+B_{m-2}}= $

$ =\frac{A_{m-1}(q_mq_{m+1}+1)+A_{m-2}q_{m+1}}{B_{m-1}(q_mq_{m+1}+1)+B_{m-2}q_{m+1}} $$ =\frac{q_{m+1}(A_{m-1}q_m+A_{m-2})+A_{m-1}}{q_{m+1}(B_{m-1}q_m+B_{m-2})+B_{m-1}} $$ =\frac{q_{m+1}A_{m}+A_{m-1}}{q_{m+1}B_{m}+B_{m-1}} $$ =\frac{A_{m+1}}{B_{m+1}} $

Inviato: 14 feb 2008, 12:10
da piever
2) anche questo per induzione: il caso base si può fare a mano. Supponiamo la tesi vera per m-1 e dimostriamola per m:

$ A_mB_{m-1}-B_mA_{m-1} $$ =(q_mA_{m-1}+A_{m-2})B_{m-1}-(q_mB_{m-1}+B_{m-2})A_{m-1}= $

$ =A_{m-2}B_{m-1}-B_{m-2}A_{m-1}=(-1)^{m-1} $

Inviato: 14 feb 2008, 13:03
da FrancescoVeneziano
Benissimo. Analogamente al (2) si può dimostrare
3) $ \ A_m B_{m-2}-A_{m-2}B_m = (-1)^m q_m $
e, per curiosità e per sveltire i calcoli, si può dimostrare anche
4) $ \ A_m $ può essere ottenuto con questo algoritmo: Si prenda il prodotto di tutti i $ \ q_0,\dotsc,q_m $, si aggiungano tutti i prodotti ottenuti escludendo due $ \ q_i $ con indici consecutivi, si aggiungano ancora tutti i prodotti ottenuti escludendo due coppie di $ \ q_i $ con indici consecutivi, e così via fino a escludere $ \left\lfloor\frac{m+1}{2}\right\rfloor $ coppie. $ \ B_m $ si ottiene applicando lo stesso algoritmo a $ \ q_1,\dotsc,q_m $.
Esempio: $ \ A_3=q_0q_1q_2q_3+q_2q_3+q_0q_3+q_0q_1+1 $ e $ \ B_3=q_1q_2q_3+q_3+q_1 $.

Come ha giustamente osservato piever, per le proposizioni 1,2,3,4 non serve che i $ \ q_i $ siano interi, e in effetti non serve nemmeno assumere che siano reali, si tratta semplicemente di uguaglianze algebriche che sono sempre vere; se avete fegato potete considerarle identità in un campo di funzioni razionali $ \ \mathbb{Q}(q_0,q_1,\dotsc) $.

Se utilizziamo le ipotesi che aveva usato piever, cioè $ \ q_0 $ reale e $ \ q_i $ reale positivo per tutti gli indici positivi, possiamo dimostrare qualcosa sulla successione dei convergenti, precisamente
5) I convergenti pari $ \ \frac{A_{2m}}{B_{2m}} $ sono una successione monotona crescente; i convergenti dispari $ \ \frac{A_{2m+1}}{B_{2m+1}} $ sono una successione monotona decrescente; ogni convergente dispari è maggiore di ogni convergente pari.

Se in più aggiungiamo che i $ \ q_i $ sono interi, tornando all'ipotesi che avevo chiesto inizialmente, possiamo dimostrare che
6) La successione $ \ B_m $ è monotona crescente; $ \ B_m\geq m $, e la successione $ \ \frac{A_{m}}{B_{m}} $ tende ad un limite, che chiamiamo il valore della frazione continua.

Inviato: 14 feb 2008, 16:20
da FeddyStra
Provo a concludere il discorso.

Punto 5).
Divido la 3) per $ B_mB_{m-2} $ e ottengo
$ \displaystyle\frac{A_m}{B_m}-\frac{A_{m-2}}{B_{m-2}}=\frac{(-1)^mq_m}{B_mB_{m-2}} $.

Ponendo ora $ m=2n $ si trova
$ \displaystyle\frac{A_{2n}}{B_{2n}}-\frac{A_{2(n-1)}}{B_{2(n-1)}}=\frac{(-1)^{2n}q_{2n}}{B_mB_{m-2}}=\frac{q_{2n}}{B_mB_{m-2}}>0 $,
quindi la sequenza degli $ \frac{A_{2n}}{B_{2n}} $ è crescente.

Ponendo ora $ m=2n+1 $ si trova
$ \displaystyle\frac{A_{2n+1}}{B_{2n+1}}-\frac{A_{2n-1}}{B_{2n-1}}=\frac{(-1)^{2n+1}q_{2n+1}}{B_mB_{m-2}}=-\frac{q_{2n+1}}{B_mB_{m-2}}<0 $,
quindi la sequenza degli $ \frac{A_{2n+1}}{B_{2n+1}} $ è decrescente.

Utilizzando analogamente l'identità 2) si possono confrontare i convergenti pari con quelli dispari e si vede che
$ \displaystyle\frac{A_{2n+1}}{B_{2n+1}}-\frac{A_{2n}}{B_{2n}}= $$ \displaystyle-\frac{1}{B_{2n+1}B_{2n}}\le 0 $ (*)
quindi ogni convergente dispari è più piccolo di ogni convergente pari.

Punto 6).
La successione dei convergenti pari è decrescente e limitata inferiormente, quindi converge. Allo stesso modo, converge la successione dei convergenti dispari.
Rimane da dimostrare che questo limite è lo stesso.
In base a come è definita, la successione$ B_n $ è crescente: infatti $ B_n=q_nB_{n-1}+B_{n-2}>q_nB_{n-1}>B_{n-1} $, quando i $ q_i $ sono interi. Proprio perchè si tratta di numeri interi, la successione sarà non solo crescente, ma anche divergente a $ +\infty $.
Dalla (*) si vede allora che la differenza delle due successioni tende a $ 0 $, quindi esse convergono al medesimo limite.

Inviato: 14 feb 2008, 18:26
da FrancescoVeneziano
Fino ad ora abbiamo associato ad una successione, finita o infinita, $ \ q_0,\dotsc $ un numero reale, associando ad ogni successione finita l'ultimo dei convergenti e ad ogni successione infinita il limite dei convergenti. Mostriamo adesso come invertire questa funzione e costruire a partire da un numero reale una successione di $ \ q_i $ come nelle nostre ipotesi.
Sia $ \ \alpha\in\mathbb{R} $, e definiamo $ \ \alpha_0=\alpha $, $ \ q_0=\lfloor\alpha\rfloor $ e
$ \ \alpha_{n+1}=\frac{1}{\alpha_n-q_n} $
$ \ q_{n+1}=\lfloor\alpha_{n+1}\rfloor $
in modo che si abbia sempre
$ \displaystyle \alpha_n=q_n+\frac{1}{\alpha_{n+1}}. $
Questo procedimento può arrestarsi dopo un numero finito di passi se si raggiunge un $ \ \alpha_i $ intero, o andare avanti all'infinito se ciò non avviene mai.
Osserviamo che a parte $ \ \alpha_0 $ e $ \ q_0 $, per tutti i termini successivi si ha che $ \ 0 < \alpha_i < 1 $ e $ \ q_i\geq 1 $ e quindi la successione dei $ \ q_i $ dà luogo ad una frazione continua, che chiamiamo sviluppo di $ \ \alpha $ in frazione continua.
Notiamo anche la relazione
7)$ \displaystyle \alpha=\frac{\alpha_{n+1}A_n+A_{n-1}}{\alpha_{n+1}B_n+B_{n-1}} $.
Se lo sviluppo di $ \ \alpha $ è finito, è ovvio che l'ultimo convergente sia proprio uguale ad $ \ \alpha $; è vero anche
8) Se lo sviluppo di $ \ \alpha $ è infinito, i convergenti $ \ \frac{A_n}{B_n} $ tendono ad $ \ \alpha $.

È naturale a questo punto chiedersi quando lo sviluppo in frazione continua è finito, e se è unico; è un buon esercizio dimostrare
9) $ \ \alpha\in\mathbb{Q}\Leftrightarrow $ lo sviluppo di $ \ \alpha $ in frazione continua è finito.

Inviato: 14 feb 2008, 19:48
da FeddyStra
Per quanto riguarda il punto 9), non riesco a capire se sia più difficile di quello che sembra, o se sembri più difficile di quello che è...

Assumiamo infatti che $ \alpha\in\mathbb Q $.
La frazione continua, come definita da te, si trova con un procedimento equivalente all'algoritmo euclideo applicato al numeratore e al denominatore di $ \alpha $. Dimostrare che lo sviluppo della frazione continua è finito si riduce quindi a dimostrare che l'algoritmo euclideo ha termine, il che è (abbastanza) chiaro.
Quindi abbiamo stabilito che
$ {\alpha\in\mathbb Q\Leftrightarrow\mbox{lo sviluppo è finito}} $.

Assumiamo ora che $ \text{lo sviluppo è finito} $.
Qui è proprio evidente vedere che la frazione continua si riduce a una frazione ordinaria (intendo "a due piani" e non più "a torre"...), la quale rappresenta (per definizione) un numero razionale.
Quindi è dimostrato anche che
$ {\mbox{lo sviluppo è finito}\Leftrightarrow\alpha\in\mathbb Q} $.

Inviato: 14 feb 2008, 20:04
da FrancescoVeneziano
Che se lo sviluppo è finito il numero sia razionale è assolutamente ovvio; l'altra implicazione si riconduce, come hai osservato, all'algoritmo euclideo ma questo passaggio non è poi così evidente e vale la pena osservarlo in modo più esplicito, anche perché mostra legami con l'identità di Bezout e le diofantee lineari. Quando avremo finito tutto il discorso, conto di riorganizzare il thread nel glossario quindi preferisco evidenziare i punti che sono più importanti per il seguito ma anche quelli più "didattici".

Inviato: 16 feb 2008, 11:50
da piever
Allora, 7) viene per induzione (tanto per cambiare), è solo questione di farsi i conti che, effettivamente, tornano...

8 ) $ |\frac{A_n}{B_n}-\frac{\alpha_{n+1}A_n+A_{n-1}}{\alpha_{n+1}B_n+B_{n-1}}| $$ =|\frac{A_nB_{n-1}-B_nA_{n-1}}{B_n(\alpha_{n+1}B_n+B_{n-1})}|=\frac{1}{B_n(\alpha_{n+1}B_n+B_{n-1})} $ che tende a zero visto che il numeratore è costante e il denominatore tende a infinito.

9) Cerco di dire in maniera più esplicita (usando abbondantemente il suggerimento di Federico :roll: ) per quale ragione se $ \alpha $ è razionale, a un certo punto $ \alpha _n $ diventa intero.

Poniamo $ \alpha _0=\frac{a}{b} $

Ora, come si passa da $ \alpha _0 $ a $ \alpha _{1} $ ?? Prendiamo l'intero nonnegativo c tale che: c<b e b|(a-c). Ora abbiamo che $ \alpha _1= \frac{b}{c} $. Lo stesso passaggio è valido per andare da n a n+1 (anziché da 0 a 1). La successione dei denominatori è strettamente decrescente nei naturali, quindi a un certo punto si ferma.

Inviato: 18 feb 2008, 00:33
da FrancescoVeneziano
Continuiamo con un lemma
10) La parte intera (grazie, piever) di $ \ q_0+\frac{1}{q_1+}\dotsm\frac{1}{q_m} $ è uguale a $ \ q_0 $ tranne che nel caso $ \ m=1,q_1=1 $, in questo caso è $ \ q_0+1 $.

L'ostacolo per dimostrare l'unicità dello sviluppo è che in effetti lo sviluppo in frazione continua NON è unico. Per esempio $ \ 1+\cfrac{1}{1+\cfrac{1}{1}}=1+\cfrac{1}{2} $ e quindi il numero 3/2 ha due sviluppi, uno dato da [1,1,1] e uno dato da [1,2]
(Indico con $ \ [q_0,q_1\dotsc] $ la frazione continua data da quella successione)

Questa è l'unica ambiguità possibile, in un certo senso analoga all'ambiguità che esiste nell'espressione decimale dei razionali che terminano con infiniti 0 o con infiniti 9.
Abbiamo che
11) I numeri razionali hanno esattamente due sviluppi in frazione continua, le loro lunghezze differiscono di uno, ed esattamente uno di essi termina con 1; sono dati da $ \ [q_0,\dotsc,q_n,1]=[q_0,\dotsc,q_n+1] $. I numeri irrazionali hanno un unico sviluppo in frazione continua.


Dopo aver dimostrato che i numeri con uno sviluppo finito sono razionali, ci chiediamo quali numeri irrazionali hanno uno sviluppo periodico, cioè dato da un antiperiodo $ \ q_0,\dotsc,q_n $ seguito da un periodo $ \ p_1,\dotsc,p_m $ che si ripete infinite volte (indichiamo con $ \ [q_0,\dotsc,q_n,\overline{p_1,\dotsc,p_m}] $ questa frazione continua).

Abbiamo che
12) Le frazioni continue periodiche rappresentano irrazionali quadratici, cioè radici di polinomi irriducibili di secondo grado a coefficienti interi (cioè numeri della forma $ \ a+b\sqrt{d} $ con $ \ a,b\in\mathbb{Q} $ e d intero libero da quadrati).

Inviato: 18 feb 2008, 10:39
da piever
Alura, continuando a farsi del male:

10) Con frazionaria intendi intera, vero? (è inutile, non mi vengono più battute decenti da anni...)

Comunque, supponiamo che la parte intera della frazione sia diversa da $ q_0 $. Visto che i convergenti dispari sono strettamente decrescenti e maggiori dei convergenti pari, il primo deve essere maggiore o uguale di $ q_0+1 $ e, imponendo questo, si ottiene $ q_1\le 1 $, ma tutti i $ q_i $ sono interi positivi, per cui $ q_1=1 $

In questo modo si ha l'uguaglianza, per cui se la frazione continuasse oltre, diminuirebbe (data la decrescenza stretta dei convergenti dispari e il fatto che sono sempre maggiori dei convergenti pari), quindi questo è l'unico controesempio.

"10)"==>"11)" in maniera abbastanza evidente, e questo si capisce più facilmente ragionando sul problema, che non leggendo i miei deliri, per cui è meglio se evito di scriverlo.

12) Intanto notiamo che i numeri della forma $ a+b\sqrt d $ restano di quella forma se li invertiamo o se ci sommiamo un razionale, per cui possiamo considerare direttamente il caso $ [0,\overline{p_1,\dotsc,p_m}] $

Poniamo $ \beta =[0,p_1,\dotsc,p_m] $ (dove, per quanto detto in qualche altro post, $ \beta $ è un razionale positivo)

Ora, evidentemente, $ [0,\overline{p_1,\dotsc,p_m}]=[0,\overline{\beta}] $ (al solito, la frazione continua posso farla pure se i $ q_i $ non sono interi, anche se si perdono alcune proprietà..)

Ponendo $ \alpha =[0,\overline{p_1,\dotsc,p_m}] $ abbiamo che $ \alpha=\frac{1}{\beta +\alpha} $ cioè $ \alpha ^2+\beta\alpha=1 $

Infine, ponendo $ \beta=\frac{p}{q} $ con p e q interi, otteniamo che $ q\alpha ^2 +p\alpha -q=0 $ che è (un po' a modo suo) la tesi.

Inviato: 18 feb 2008, 12:46
da FrancescoVeneziano
Mi sembra di vedere un problema col tuo (12)
Perché $ \ [0,\overline{p_1,\dotsc,p_m}]=[0,\overline{\beta}] $ ?

Inviato: 18 feb 2008, 17:16
da piever
FrancescoVeneziano ha scritto:Mi sembra di vedere un problema col tuo (12)
In effetti sembra anche a me... Riparto da dove ero arrivato, rinunciando alla soluzione elegante (è preferibile che sia corretta in effetti..)

Passiamo quindi a una simpatica dimostrazione per "induzione dall'alto".

VERITA' CALATA DALL'ALTO:

Poniamo $ x=[0,\overline{p_1,\dotsc,p_m}] $

Poniamo:

$ a_0=1 $ e $ a_1=-p_1 $

$ b_0=0 $ e $ b_1=1 $

$ a_{n+1}=-p_{n+1}a_n+a_{n-1} $

$ b_{n+1}=-p_{n+1}b_n+b_{n-1} $

Si ha che:

$ x=\frac{a_{m}x+b_{m}}{a_{m-1}x+b_{m-1}} $

Come ogni altra verità calata dall'alto, questo si dimostra per induzione (nel nostro caso induzione su m, ma in genere è su n)

Quindi segue che $ a_{m-1}x^2+(b_{m-1}-a_{m})x-b_m=0 $

Sempre per induzione possiamo far vedere che $ (-1)^n a_n>0 $ per cui, ponendo n=m-1, abbiamo che $ a_{m-1}\neq 0 $ e quindi il nostro polinomio è davvero di secondo grado e non è (come magari uno abituato a perder punti in gara si sarebbe aspettato) il polinomio nullo.

Domandone: è vero anche il contrario, cioè che le radici di polinomi di secondo grado irriducibili hanno uno sviluppo periodico in frazione continua?

Inviato: 18 feb 2008, 17:53
da FrancescoVeneziano
Forse ho intuito cosa hai fatto, ma devo dire che ancora la dimostrazione non mi è chiara. Come dimostri l'identità $ \ x=\frac{a_{m}x+b_{m}}{a_{m-1}x+b_{m-1}} $? m è la lunghezza del periodo, non una variabile. Cerco di riordinare un po'.
Chiamiamo $ \ y=[\overline{q_0,\dotsc,q_n}] $ facendo partire il periodo da subito, senza lasciare uno 0 come antiperiodo.
I modi per procedere sensati adesso sono due (che in realtà sono lo stesso):

Ovviamente abbiamo $ \ y=[q_0,\dotsc,q_n,y] $ quindi possiamo vedere y come una frazione finita, il cui valore è $ \ y=\frac{A_{n+1}}{B_{n+1}}=\frac{y A_n +A_{n-1}}{y B_n +B_{n-1}} $

Oppure possiamo tornare all'identità (7), osservando che se prendiamo come $ \ \alpha $ y, anche $ \ \alpha_{n+1}=y $ ed ottenere di nuovo la stessa uguaglianza, che è $ \ B_n y^2 + (B_{n-1}-A_n)y-A_{n-1}=0 $ che dimostra la tesi (i B_i sono positivi e crescenti, quindi non è il polinomio nullo e, volendo evitare un altro modo di perdere punti, non può neanche essere il quadrato di un fattore lineare perché y è irrazionale)