Metodo Chakravala

In matematica e più specificamente in aritmetica , il metodo chakravala è un algoritmo per risolvere l' equazione di Pell-Fermat . Questa equazione è un esempio di un'equazione diofantina , vale a dire con coefficienti interi e di cui si cercano soluzioni intere. Più precisamente, è l'equazione

x ^ {2} -ny ^ {2} = 1

dove n è un numero naturale non quadrato .

Questo metodo è stato sviluppato in India e le sue radici possono essere ricondotte al VI ° secolo con Aryabhata , seguito da Brahmagupta . Iniziato da Jayadeva (en) , è stato ulteriormente sviluppato da Bhāskara II .

Selenius lo valuta in questo modo: “Il metodo rappresenta un algoritmo di migliore approssimazione di lunghezza minima che, a causa di diverse proprietà di minimizzazione, produce automaticamente […], a minor costo […] ed evitando numeri grandi, soluzioni minime dell'equazione […] Il metodo chakravāla ha preceduto i metodi europei di oltre mille anni. Ma nessuna performance europea in tutto il campo dell'algebra , molto più tardi dopo Bhāskara [...], ha eguagliato la meravigliosa complessità e ingegnosità del chakravāla . "

Essa deve infatti aspettare il XVII ° secolo che gli europei, che hanno ignorato il lavoro dei matematici indiani stanno scoprendo algoritmi - meno efficienti - risolvere lo stesso problema.

Obiettivo

Una forma dell'equazione di Pell-Fermat è espressa come segue:

x ^ {2} -ny ^ {2} = 1,

dove n è un numero naturale non quadrato. L'equazione è Diofhantina, il che significa che le coppie ( x , y ) cercate sono coppie di numeri interi. Tutte le soluzioni sono espresse dalla coppia di soluzioni formata da due interi minimi in valore assoluto nell'insieme di soluzioni. Il metodo chakravala permette di ottenere un paio di questa natura.

La seguente uguaglianza è un esempio di una soluzione; Indiani Si sapeva del VII ° secolo:

1151 ^ {2} -92 \ times 120 ^ {2} = 1.

Storia

Matematica indiana

La matematica indiana interessava molto presto l'aritmetica. Aryabhata , un matematico del VI ° secolo , stabilisce le basi. Sviluppa un sistema numerico che mostra che probabilmente conosceva la notazione posizionale così come l'esistenza dello zero . Lavora sulle equazioni diofantiche e per risolvere l' identità di Bézout , sviluppa un algoritmo equivalente a quello di Euclide che chiama ku ṭ ṭ aka (कूटटक) e che significa spruzzatore perché scompone i numeri in interi più piccoli. Lavora anche su frazioni continue .

Il matematico indiano Brahmagupta ( 598 - 668 ) sembra essere il primo ad analizzare in profondità questa domanda. Capisce come, da due soluzioni, sia possibile costruirne una nuova. Ribadendo, ottiene così tante soluzioni distinte quante ne desidera. Questo metodo è chiamato samasa dai matematici indiani. Brahmagupta ne deduce tre algoritmi. Il primo gli permette di trovare una soluzione se ha una coppia di numeri interi ( x , y ) la cui immagine dall'equazione è –1. Ne trova una seconda che si occupa del caso in cui l'immagine è 2 in valore assoluto . Ne trova un terzo che dà lo stesso risultato se l'immagine è uguale a ± 4. È nato un metodo in bozza. Inizia con un tentativo ed errore finché non trova una coppia avente per immagine 1, 2 o 4 in valore assoluto, continua con uno dei tre algoritmi. Brahmagupta lo usa nel 628 nel suo libro Brahmasphuta siddhanta per risolvere la seguente equazione:

x ^ {2} -83y ^ {2} = 1.

Questo approccio è insufficiente per trattare casi complessi, può essere difficile trovare per tentativi ed errori una coppia che dia uno dei sei valori che consentono una conclusione. Nel XII ° secolo , Bhaskara si basa sui trattati precedenti e propone la forma finale del metodo chakravala . Corrisponde all'addizione di un algoritmo ciclico, ovvero dando una sequenza periodica di coppie contenente necessariamente una soluzione. L'algoritmo ciclico è equivalente a quello delle frazioni continue . Il metodo chakravala termina con i calcoli di Brahmagupta se si verifica uno dei valori –1, ± 2 e ± 4. Bhāskara II lo usa nel 1150 nel suo trattato Bijaganita per trovare una soluzione minima alla seguente equazione già trovata da Brahmagupta:

x ^ {2} -61y ^ {2} = 1.

La coppia di soluzione trovata è:

x = 1 \, 766 \, 319 \, 049 \ quad {\ text {e}} \ quad y = 226 \, 153 \, 980.

E 'improbabile che Bhaskara ha dimostrato il fatto che l'algoritmo offre sempre una soluzione, vale a dire per ogni valore di n perché la manifestazione, lunga e tecnica, richiede una raffinatezza di gran lunga superiore alla matematica XII ° secolo. Nuovi esempi vengono trattati in seguito dai matematici indiani. Nel XIV ° secolo il matematico chiamato Narayana studiare se n è pari a 103 nei suoi commenti sul libro Bijaganita di Bhaskara.

Europa

Nel febbraio 1657 (a seguito di un'altra sfida più famosa risalente al 3 gennaio dello stesso anno), Pierre de Fermat sfida Bernard Frénicle de Bessy e, attraverso di lui tutti i matematici europei, a risolvere (tra le altre cose) il problema per n = 61. Il La reazione inglese è rapida: William Brouncker trova un algoritmo. Frénicle de Bessy propone quindi una tabella contenente tutte le soluzioni per i valori di n meno di 150, che andranno definitivamente persi, poi John Wallis riscopre i risultati di Brahmagupta e li dimostra con rigore. Bessy's Frenicle sfida Brouncker con il valore n = 313; riceve in risposta non solo la soluzione, ma l'affermazione che il suo autore non ha avuto bisogno di più di "un'ora o due" per trovarla.

Le due domande teoriche sottostanti, ovvero se per qualsiasi numero naturale non quadrato n esiste una soluzione e se la soluzione trovata genera effettivamente tutte le altre, vengono finalmente risolte da Lagrange nel 1767, da un algoritmo meno efficiente di quello - quindi ignorato dagli europei - a causa di Bhāskara, ma la cui correzione è più facile da dimostrare. Nel 1930, AA Krishnaswami Ayyangar (in) afferma di essere il primo a provare quello di chakravala .

Contributi di Brahmagupta

Fondali

I metodi qui proposti utilizzano il potere del formalismo attuale. Se il contenuto matematico è analogo a quello di Brahmagupta, le tecniche espositive così come le dimostrazioni non riflettono il pensiero del matematico indiano. Le seguenti notazioni vengono utilizzate in tutto il resto dell'articolo. Considera la seguente equazione diofantina, dove n è un numero naturale non quadrato:

(1) \ quad x ^ {2} -ny ^ {2} = 1.

Lasciate Una sia l'anello di numeri della forma a + $\sqrt n$ b , dove a e b sono indicati due numeri interi, N l'applicazione che ad un elemento di A associa sua " norma " e Phi l'applicazione che ad un elemento di A associa sua " coniugato ":

{\ mathcal N} (a + {\ sqrt n} b) = a ^ {2} -nb ^ {2}, \ quad \ varphi (a + {\ sqrt n} b) = a - {\ sqrt n} b.

La funzione N corrisponde alla norma di A nel senso della teoria algebrica dei numeri . Un elemento a + $\sqrt n$ b di A è chiamato radice dell'equazione (1) se e solo se la sua norma è 1, cioè se ( a , b ) è una soluzione di (1).

La funzione φ ha anche proprietà utili. È un automorfismo di A :

\ forall \ alpha, \ beta \ in A \ quad \ varphi (\ alpha + \ beta) = \ varphi (\ alpha) + \ varphi (\ beta), \ quad \ varphi (\ alpha \ beta) = \ varphi ( \ alpha) \ varphi (\ beta), \ quad \ varphi (1) = 1.

La coniugazione φ è involutiva, vale a dire che composta due volte di seguito con se stessa, è uguale all'identità, oppure la sua reciproca biiezione è uguale a se stessa:

\ forall \ alpha \ in A \ quad (\ varphi \ circ \ varphi) (\ alpha) = \ alpha.

Infine, il prodotto di due elementi coniugati è uguale alla loro norma comune:

\ forall \ alpha \ in A \ quad {\ mathcal N} (\ alpha) = \ alpha \ varphi (\ alpha).

Se scriviamo α = a + $\sqrt n$ b , ciò è giustificato dal seguente calcolo:

{\ mathcal N} (\ alpha) = a ^ {2} -nb ^ {2} = (a + {\ sqrt n} b) (a - {\ sqrt n} b) = \ alpha \ varphi (\ alpha ).

Samasa

La prima proprietà utilizzata è:

Siano α e β due elementi di A , quindi:

{\ mathcal N} (\ alpha \ beta) = {\ mathcal N} (\ alpha) {\ mathcal N} (\ beta).

Se α = a 1 + $\sqrt n$ a 2 e β = b 1 + $\sqrt n$ b 2 , questa uguaglianza è scritta:

(a_ {1} b_ {1} + na_ {2} b_ {2}) ^ {2} -n (a_ {1} b_ {2} + a_ {2} b_ {1}) ^ {2} = ( a_ {1} ^ {2} -na_ {2} ^ {2}) (b_ {1} ^ {2} -nb_ {2} ^ {2}).

Questa uguaglianza, nota come identità di Brahmagupta , era chiamata dagli indiani Samasa . Per convincersi della sua accuratezza, basta esprimere N in funzione dell'automorfismo φ:

{\ mathcal N} (\ alpha \ beta) = \ alpha \ beta \ varphi (\ alpha \ beta) = \ alpha \ varphi (\ alpha) \ beta \ varphi (\ beta) = {\ mathcal N} (\ alpha ) {\ mathcal N} (\ beta).

Un caso speciale corrisponde a quello in cui β è un intero k , l'uguaglianza assume la seguente forma:

Siano α un elemento di A e k un numero intero, quindi:

{\ mathcal N} (k \ alpha) = {\ mathcal N} (k) {\ mathcal N} (\ alpha) = k ^ {2} {\ mathcal N} (\ alpha).

Conseguenze

Sia α un elemento di A di norma 1, allora φ (α) è inverso di α e di norma 1.
Se l'equazione (1) ammette una soluzione diversa da ± 1, allora ammette un'infinità di soluzioni distinte.

Infatti, N (α) = N (φ (α)) = αφ (α), e se α è una soluzione di (1) allora α k anche per qualsiasi numero naturale k (perché la norma di un prodotto è uguale al prodotto delle norme), ma le potenze di un reale diverso da 0, 1 e –1 sono tutte distinte.

Capire come Brahmagupta risolve l'equazione (1) dipende da tre proposizioni:

Sia α un elemento di A.

Se N (α) = ± 1 allora α 2 è una soluzione di (1).
Se N (α) = ± 2, quindi α 2 /2 è una soluzione di (1).
Se N (α) = 4ε con ε = ± 1 allora una soluzione di (1) è:
- se α è divisibile per 2: (α / 2) (3 - ε) / 2 ;
- se n è pari: α 2 /4;
- altrimenti: (α 3 /8) (3-ε) / 2 .

Dimostrazione

: immediato.
: se α = a + b $\sqrt n$ allora α 2 = a 2 + nb 2 + 2 ab $\sqrt n$ = N (α) + 2 nb 2 + 2 ab $\sqrt n$ è divisibile per 2 (e 2 2 N (α 2 / 2) = N (α 2 ) = (± 2) 2 pertanto N (α 2 /2) = 1).
: I primi due casi sono immediati e nella terza, n , un e b sono dispari, in modo che α 3 è divisibile per 8 perché ${\ begin {align} \ alpha ^ {3} & = (a + b {\ sqrt n}) ^ {3} = a ^ {3} + 3ab ^ {2} n + {\ sqrt n} (nb ^ {3} + 3a ^ {2} b) = a (a ^ {2} -nb ^ {2} + 4nb ^ {2}) + b {\ sqrt n} (3a ^ {2} -3nb ^ {2 } + 4nb ^ {2}) \\ & = a \ left ({\ mathcal N} (\ alpha) + 4nb ^ {2} \ right) + b {\ sqrt n} \ left (3 {\ mathcal N} (\ alpha) + 4nb ^ {2} \ right) = 4a \ left (\ varepsilon + nb ^ {2} \ right) + 4b {\ sqrt n} \ left (3 \ varepsilon + nb ^ {2} \ right ) \ quad {\ text {con}} \ quad \ varepsilon = \ pm 1. \ end {allineato}}$

Esempi

Esempio di Brahmagupta

Trattiamo con questo metodo il seguente esempio di Brahmagupta:

x ^ {2} -83y ^ {2} = 1.

Sia α = m + √ 83 , l'intero m essendo scelto in modo tale che la norma N (α) = m 2 - 83 sia la più piccola possibile in valore assoluto: m = 9, α = 9 + √ 83 , N (α) = –2. A precedenti spettacoli proposta che alfa 2 /2 è una soluzione. Effettivamente :

\ alpha ^ {2} = (9 ^ {2} +83 \ cdot 1) + {\ sqrt {83}} \ cdot 2 \ times 9 \ times 1 = 164 + {\ sqrt {83}} \ cdot 18 = 2 \ sinistra (82 + {\ sqrt {83}} \ cdot 9 \ destra)

82 ^ {2} -83 \ times 9 ^ {2} = 6 \, 724-6 \, 723 = 1.

Sfida Fermat

La sfida di Fermat si risolve allo stesso modo:

x ^ {2} -61y ^ {2} = 1.

Brahmagupta lo fa nel modo seguente: nota che se α = 39 + 5 √ 61 allora N (α) è uguale a –4. Ovviamente il formalismo Brahmagupta non ha nulla a che fare con quello qui usato, anche se i calcoli sono gli stessi. Calcola alfa 2 /2:

{\ frac {\ alpha ^ {2}} 2} = {\ frac 12} (39 + 5 {\ sqrt {61}}) ^ {2} = {\ frac 12} (39 ^ {2} + 5 ^ {2} \ times 61 + 2 \ times 5 \ times 39 {\ sqrt {61}}) = 1 \, 523 + 195 {\ sqrt {61}}.

Poi calcola α 3 /8 e il suo standard:

{\ frac {\ alpha ^ {3}} {8}} = {\ frac 14} (39 + 5 {\ sqrt {61}}) (1 \, 523 + 195 {\ sqrt {61}}) = 29 \, 718 + 3 \, 805 {\ sqrt {61}} \ quad {\ text {et}} \ quad {\ mathcal N} ({\ frac {\ alpha ^ {3}} 8}) = 29 \, 718 ^ {2} -61 \ times 3 \, 805 ^ {2} = - 1.

La soluzione è quindi α 6 /64, sia:

{\ frac {\ alpha ^ {6}} {64}} = (29 \, 718 + 3 \, 805 {\ sqrt {61}}) ^ {2} = 29 \, 718 ^ {2} +61 \ volte 3 \, 805 ^ {2} +2 \ volte 29 \, 718 \ volte 3 \, 805 {\ sqrt {61}} = 1 \, 766 \, 319 \, 049 + 226 \, 153 \, 980 { \ sqrt {61}}.

Il metodo è notevolmente economico per un algoritmo così vecchio.

Contributo di Bhāskara II

Principio del metodo

Una difficoltà con il metodo di Brahmagupta sta nel fatto che non è sempre facile trovare un numero α di A la cui norma sia uguale a ± 1, ± 2 o ± 4. Il contributo di Bhāskara II descritto nel Siddhanta Siroman consiste nell'arricchire il metodo con un algoritmo che infallibilmente finisce per fornire una “quasi-soluzione” di questa natura.

Bhāskara II costruisce per induzione una sequenza di elementi α j = a j + b j $\sqrt n$ di A come segue. Il primo elemento della successione è α 0 = 1, di norma k 0 = 1. Assumiamo la successione definita all'ordine j . Costruiamo un elemento β j = m j + $\sqrt n$ . L'intero naturale m j è tale che a j + m j b j è un multiplo della norma k j di α j - in altre parole tale che b j m j è congruente a - a j modulo k j - e m j minimizza il valore assoluto della norma m j 2 - n di β j . L'elemento α j + 1 è quindi definito da

\ alpha _ {{j + 1}} = a _ {{j + 1}} + b _ {{j + 1}} {\ sqrt n} = {\ frac {\ alpha _ {j} \ beta _ { j}} {| {\ mathcal N} (\ alpha _ {j}) |}} = {\ frac {a_ {j} m_ {j} + nb_ {j} + {\ sqrt n} (a_ {j} + m_ {j} b_ {j})} {| {\ mathcal N} (\ alpha _ {j}) |}}

\ alpha _ {{j + 1}} \ varphi (\ alpha _ {j}) = \ pm \ beta _ {j},

il ± corrispondente al segno di N (α j ) - il vantaggio di tenere conto di questo segno è che quindi a j e b j sono sempre positivi.

Vedremo più avanti che la condizione “ a j + m j b j multiplo di k j ” è equivalente a “ m j congruente a - m j –1 modulo k j ”, il che semplifica l'algoritmo.

Esempi

Sfida Fermat

Scegliamo di nuovo n uguale a 61. Il valore di m 0 è uguale a 8 per minimizzare | N (β 0 ) |. Infatti, √ 61 è compreso tra 7 e 8 e 8 2 - 61 = 3 <61 - 7 2 . L'intero m 1 viene quindi scelto tra quelli congruenti, modulo N (α 1 ) = N (8 + √ 61 ) = 8 2 - 61 = 3, a - m 0 = –8 quindi a 1. Dei due termini consecutivi 7 e 10 di questa sequenza aritmetica che circonda √ 61 , quella che minimizza | N (β 1 ) | è m 1 = 7, che dà:

\ alpha _ {2} = {\ frac {8 \ times 7 + 61} 3} + {\ frac {8 + 7} 3} {\ sqrt {61}} = 39 + 5 {\ sqrt {61}} \ quad {\ text {e}} \ quad {\ mathcal N} (\ alpha _ {2}) = - 4.

Il resto del metodo è quello di Brahmagupta . Il metodo chakravala ora rende possibile risolvere la sfida di Fermat senza tentativi ed errori e con un minimo di calcolo.

Esempio Narayana

Anche questo secondo esempio è tratto dal Siroman Siddhanta di Bhāskara II, annotato da Narayana. Per n = 103, m 0 = 10. L'intero m 1 viene quindi scelto congruente a –10 modulo N (α 1 ) = N (10 + √ 103 ) = 10 2 - 103 = –3. Come 8 < √ 103 <11 e 11 2 - 103 = 18 <103 - 8 2 , otteniamo m 1 = 11 e

\ alpha _ {2} = {\ frac {10 \ times 11 + 103} {3}} + {\ frac {10 + 11} {3}} {\ sqrt {103}} = 71 + 7 {\ sqrt { 103}} \ quad {\ text {e}} \ quad {\ mathcal N} (\ alpha _ {2}) = - 6.

Scegliamo quindi m 2 congruente a –11 modulo 6. Poiché 7 < √ 103 <13 e 103 - 7 2 = 54 <13 2 - 103, otteniamo m 2 = 7 - notate in questa occasione che “minimizza | m 2 - n | "Non sempre coincide con" minimizza | m - $\sqrt n$ | "- poi

\ alpha _ {3} = 203 + 20 {\ sqrt {103}} \ quad {\ text {e}} \ quad {\ mathcal N} (\ alpha _ {3}) = 9.

Allora, modulo 9, m 3 deve essere congruente a –7. Per ridurre al minimo | N (β 3 ) |, dobbiamo scegliere m 3 uguale a 11. Otteniamo

\ alpha _ {4} = 477 + 47 {\ sqrt {103}} \ quad {\ text {e}} \ quad {\ mathcal N} (\ alpha _ {4}) = 2.

Il calcolo di Brahmagupta ci permette di concludere: il valore cercato è

{\ frac {\ alpha _ {4} ^ {2}} 2} = {\ frac {(477 + 47 {\ sqrt {103}}) ^ {2}} 2} = 227 \, 528 + 22 \; 419 {\ sqrt {103}}.

Non unicità

L'esempio seguente mostra che il numero α j +1 definito da α j non è sempre unico: per n = 58, α 1 è uguale a 8 + √ 58 , di norma 6 quindi, per m 1 congruente a –2 modulo 6, il minimo di | m 1 2 - 58 | è 42, raggiunto per i due valori 4 e 10 di m 1 . I due valori corrispondenti per α 2 sono 15 + 2 √ 58 , con norma –7, e 23 + 3 √ 58 , con norma 7. Tuttavia, per il primo si trova quindi m 2 = 10 e per il secondo, m 2 = 4 quindi per entrambi, α 3 = 38 + 5 √ 58 , con norma –6, quindi m 3 = 8 e α 4 = 99 + 13 √ 58 , con norma –1. La biforcazione era quindi solo temporanea e le due suite danno la stessa soluzione.

Manifestazioni associate al contributo di Bhāskara II

Lemma

Un lemma dimostra l'esistenza della sequenza utilizzata da Bhaskara, sapendo che se k e b sono numeri primi l'uno all'altro , allora per ogni intero a , esistono interi m per cui un + bm è divisibile per k . Infatti, risolvendo l'identità di Bézout - che gli indiani già sapevano fare con l'algoritmo di Euclide - troviamo interi v per i quali 1 - bv è un multiplo di k , e basta porre m = - av .

Siano a , b coprimi e m , n due interi qualsiasi. Poniamo k = a 2 - nb 2 , c = am + bn e d = a + bm .

Se d è un multiplo di k allora anche c , e i due interi c / k e d / k sono coprimi.

Questo lemma è immediato notando che ad - bc = k e che b è primo con k . Applicato - con le notazioni del § “Principio del metodo” - ad a = a j e b = b j , mostra che in ogni fase della costruzione della successione (α j ), se m j è scelto secondo il metodo indicato allora α j β j è un multiplo di N (α j ), α j + 1 è un elemento di a e una j +1 e b j + 1 sono coprimi, che permette la costruzione di essere iterato.

Possiamo inoltre notare che il vincolo (nella scelta di m j ) " a j + b j m divisibile per N (α j )" è equivalente a " m congruente a - m j –1 modulo N (α j )". Infatti, b j è primo con N (α j ) e a j + b j (- m j –1 ) è divisibile per N (α j ) poiché φ (α j ) β j –1 = ± N (α j ) φ (α j –1 ).

Carattere ciclico

Una volta che abbiamo dimostrato che la sequenza (α j ) è ben definita, studiamo il suo comportamento. È "ciclico" in un certo senso. Più precisamente, annotando cl (α) la classe di equivalenza di α per la relazione "da associare " (cioè multipla l'una dell'altra da un elemento invertibile - in modo che tutti gli elementi di una classe abbiano la stessa norma in valore assoluto), la sequenza ( cl (α j )) è periodica da un certo rango. Questa proprietà è la conseguenza immediata di tre proposizioni:

La successione (| N (α j ) |) è limitata da $\sqrt n$ .
Per ogni reale C > 0, esiste un numero finito di classi di equivalenza standard in valore assoluto inferiore C .
Se, per due indici i e j , α i = εα j con ε invertibile in A , allora α i +1 = εα j +1 .

Dimostrazione

k j : = | N (α j ) | < $\sqrt n$ : mostriamolo per induzione. Abbiamo k 0 = 1 < $\sqrt n$ . Supponiamo che k j < $\sqrt n$ . Allora, esiste un intero m (necessariamente positivo) tale che m < $\sqrt n$ <m + k j e tale che m j sia uguale a m oppure a m + k j , a seconda che n - m 2 sia minore o maggiore di ( m k + j ) 2 - n , in altre parole a seconda se m 2 + k j m + k j 2 /2 - n è positivo o negativo. Confrontando m con la radice positiva di questo polinomio quadratico , possiamo facilmente dedurre che in entrambi i casi, | m j 2 - n | ≤ k j $\sqrt n - k j 2 /4$ < k j $\sqrt n$ , dove k j + 1 = | m j 2 - n | / k j < $\sqrt n$ .
Esiste solo un numero finito di classi di equivalenze di norma in valore assoluto inferiore a C : è sufficiente dimostrare che per ogni intero N > 0, esiste solo un numero finito di classi di norma in valore assoluto pari a N . Per questo, si noti innanzitutto che due elementi hanno la stessa classe se e solo se l' ideale principale che generano è lo stesso, e che qualsiasi ideale generato da un elemento il cui valore assoluto della norma è uguale a N è un gruppo subadditivo di Un contenente NA . È quindi sufficiente dimostrare che i sottogruppi additivi di A contenente NA sono in numero finito. Tuttavia, sono in biiezione con i sottogruppi del gruppo quoziente A / NA , che è finito (del cardinale N 2 ), che conclude.
Se α i = εα j con ε invertibile in A allora α i +1 = εα j +1 perché | N (α i ) | = | N (α j ) | e il β divisibile per φ (α i ) - che sono uguali a quelli divisibili per φ (α j ) - soddisfano α i β = εα j β.

Queste proprietà dimostrano solo la periodicità da un certo rango. Il paragrafo seguente mostra che questo rango è 0.

Struttura della suite

Il fatto che la sequenza sia periodica non indica a priori che raggiunga un punto di norma pari a 1 in valore assoluto. Questo è comunque ancora il caso:

Esiste un indice j > 0 tale che N (α j ) = ± 1 (quindi N (α 2 j ) = 1).
La sequenza ( cl (α k )) forma un " palindromo fino alla coniugazione": cl (α j –1 ) = cl (φ (α 1 )), cl (α j –2 ) = cl (φ (α 2 ) ), ecc.

Dimostrazione parziale

Lasciare che B sia l'insieme di elementi a + b $\sqrt n$ di A per cui un e b sono primi tra loro, e ψ essere la funzione da B a B definita da: un elemento α di B si associa un elemento β di forma m + $\sqrt n$ con m intero naturale tale che βα sia un multiplo della norma di α, di norma minima (abbiamo visto sopra che potrebbero essere due: possiamo per esempio scegliere sistematicamente in questo caso quello che corrisponde al minore tra i due valori di m ), quindi poniamo ψ (α) = αβ / | N (α) |. Il lemma e il paragrafo precedente mostrano che la mappa ψ è ben definita e così via

\ forall k \ in \ mathbb {N}, \ quad \ psi (\ alpha _ {k}) = \ alpha _ {{k + 1}}.

Questa funzione ha una simmetria rispetto alla funzione φ:

Viene verificata la seguente proprietà:

\ forall \ alpha, \ gamma \ in B \ quad \ psi (\ alpha) = \ gamma \ Rightarrow \ psi (\ varphi (\ gamma)) = \ pm \ varphi (\ alpha).

Più precisamente: ψ (φ (γ)) = ε 1 ε 2 φ (α), dove ε 1 (risp. Ε 2 ) denota il segno della norma di α (risp. Γ).

Infatti, se α ha per immagine per ψ il valore γ, esiste un unico elemento β della forma m + $\sqrt n$ con m intero naturale tale che

\ gamma = {\ frac {\ alpha \ beta} {| {\ mathcal N} (\ alpha) |}} = \ epsilon _ {1} {\ frac {\ alpha \ beta} {\ alpha \ varphi (\ alpha )}} = \ epsilon _ {1} {\ frac {\ beta} {\ varphi (\ alpha)}} \ quad {\ text {e}} \ quad (1) \ quad \ varphi (\ alpha) = \ epsilon _ {1} {\ frac {\ beta} {\ gamma}} = \ epsilon _ {1} \ epsilon _ {2} {\ frac {\ varphi (\ gamma) \ beta} {| {\ mathcal N} (\ varphi (\ gamma)) |}}.

L'elemento β è della forma m + $\sqrt n$ con m intero naturale tale che βφ (γ) è un multiplo della φ standard (γ) perché φ (α) appartiene A . Sia β 'un elemento che soddisfa queste proprietà e con una norma minore di β, l'uguaglianza γ = αβ' / N (β ') mostra che β' ha una norma maggiore di β . Si deduce che le norme di β e β 'sono uguali e si verifica il suo carattere minimo. L'uguaglianza (1) mostra quindi che ε 1 ε 2 φ (α) è effettivamente l'immagine di φ (γ) per ψ. La proposizione è dimostrata.

Si deduce che la funzione ψ è una biiezione B in B .

Esiste un indice j > 0 tale che N (α j ) = ± 1:

Secondo il precedente § “Carattere ciclico”, esistono due indici 0 ≤ k <k + j tali che cl (α k + j ) = cl (α k ). Dalla biiettività di ψ dimostrata sopra , deduciamo che cl (α j ) = cl (α 0 ), vale a dire che N (α j ) = ± 1. Inoltre, come b j > 0, la soluzione trovata non è banale .

La sequenza (α j ) forma un palindromo:

Da cl (ψ (α j –1 )) = cl (φ (α 0 )) deduciamo per induzione, dalla proprietà di ψ dimostrata sopra , che cl (ψ (α j –1– k )) = cl (φ (α k )).

Frazione continua

Il metodo chakravala è molto vicino a quello della frazione continua. L'obiettivo qui è quello di avvicinarsi alla radice di n mediante un'espressione ottimale della seguente natura:

{\ sqrt n} = f_ {0} + {\ cfrac 1 {f_ {1} + {\ cfrac {1} {f_ {2} + {\ frac 1 {f_ {3} + \, \ cdots}}} }}} \ quad {\ text {con}} \ quad f_ {i} \ in \ mathbb {Z}.

Approccio teorico

Sia n un numero naturale non quadrato. Definiamo per induzione due sequenze, ( f j ) j ≥0 con valori in ℤ e (θ j ) j ≥ - 1 in ℚ ( $\sqrt n$ ) con: θ –1 = $\sqrt n$ e per ogni j ≥ –1 , f j +1 è il numero intero (o il più piccolo dei due numeri interi) per il quale | N (θ j - f j +1 ) | è minimo e θ j +1 = 1 / (θ j - f j +1 ). Il fatto che $\sqrt n$ sia irrazionale mostra che θ j è sempre irrazionale; le successioni ( f j ) e (θ j ) sono quindi ben definite.

Questa definizione differisce dalla frazione continua tradizionale perché qui, θ j e f j non sono necessariamente positivi.

Siano ( h j ) e ( k j ) le successioni dei numeratori e dei denominatori delle riduzioni .

Se (α j ) e (β j ) denotano le sequenze definite in precedenza , sono soddisfatte le seguenti uguaglianze (con, per convenzione, m –1 = 0):

\ forall j \ in \ mathbb {N} \ quad f_ {j} = (- 1) ^ {j} {\ frac {m _ {{j-1}} + m_ {j}} {{\ mathcal N} (\ alpha _ {j})}}, \ quad \ theta _ {j} = (- 1) ^ {{j + 1}} {\ frac {\ varphi (\ beta _ {j})} {{\ mathcal N} (\ alpha _ {j})}} \ quad {\ text {e}} \ quad \ alpha _ {j} = \ pm (h _ {{j-1}} + k _ {{j- 1}} {\ sqrt n}).

Pertanto, il carattere ciclico e la proprietà palindromo di questa frazione continua consentono di dimostrare quelli del metodo chakravala e viceversa. Se l'algoritmo ricorsivo impone che β j sia di norma sistematicamente negativa, allora le dimostrazioni dell'articolo rimangono valide e le frazioni continue associate corrispondono alla definizione usuale.

Dimostrazione

f j = (–1) j ( m j –1 + m j ) / N (α j ) e θ j = (–1) j +1 N (α j ) / φ (β j ): mostriamolo risultato per ricorrenza su j . Per definizione, f 0 = m 0 e $\ theta _ {0} = {\ frac 1 {{\ sqrt n} -m_ {0}}} = {\ frac 1 {- \ varphi (\ beta _ {0})}} = - {\ frac {{ \ mathcal N} (\ alpha _ {0})} {\ varphi (\ beta _ {0})}}.$ Supponi il risultato stabilito all'ordine j - 1 e mostra che è vero all'ordine j . $(-1) ^ {j} \ sinistra (f_ {j} + {\ frac 1 {\ theta _ {j}}} \ right) = (- 1) ^ {j} \ theta _ {{j-1} } = {\ frac {{\ mathcal N} (\ alpha _ {{j-1}})} {\ varphi (\ beta _ {{j-1}})}} = {\ frac {{\ mathcal N } (\ alpha _ {{j-1}}) \ beta _ {{j-1}}} {\ varphi (\ beta _ {{j-1}}) \ beta _ {{j-1}}} } = {\ frac {{\ mathcal N} (\ alpha _ {{j-1}}) \ beta _ {{j-1}}} {{\ mathcal N} (\ pm \ alpha _ {j} \ varphi (\ alpha _ {{j-1}}))}} = {\ frac {\ beta _ {{j-1}}} {{\ mathcal N} (\ alpha _ {j})}} = { \ frac {m _ {{j-1}} + m_ {j}} {{\ mathcal N} (\ alpha _ {j})}} - {\ frac {\ varphi (\ beta _ {j})} {{\ mathcal N} (\ alpha _ {j})}}$ e per scelta di β j , l'intero f = ( m k –1 + m k ) / N (α k ) è quello per cui il valore assoluto della norma di (β j –1 / N (α j )) - f è minimo. È quindi uguale a (–1) j f j e il resto, –φ (β j ) / N (α j ), a (–1) j / θ j .
α j = ± ( h j –1 + k j –1 $\sqrt n$ ): notando ε j il segno di N (α j ) abbiamo, per ogni j > 0: $(-1) ^ {j} f_ {j} {\ mathcal N} (\ alpha _ {j}) = m_ {j} + m _ {{j-1}} = \ beta _ {j} + \ varphi (\ beta _ {{j-1}}) = \ varepsilon _ {j} \ alpha _ {{j + 1}} \ varphi (\ alpha _ {j}) + \ varepsilon _ {{j-1}} \ varphi (\ alpha _ {j}) \ alpha _ {{j-1}}$ cioè $(-1) ^ {j} f_ {j} \ alpha _ {j} = \ varepsilon _ {j} \ alpha _ {{j + 1}} + \ varepsilon _ {{j-1}} \ alpha _ { {d-1}}$ o ancora, mettendosi in posa $\ varepsilon '_ {j} = (- 1) ^ {{j (j-1) / 2}} \ prod _ {{0 \ leq i <j}} \ varepsilon _ {i} ~: \ quad \ varepsilon '_ {{j + 1}} \ alpha _ {{j + 1}} = f_ {j} \ varepsilon' _ {j} \ alpha _ {j} + \ varepsilon '_ {{j-1}} \ alpha _ {{j-1}}.$ Le due successioni (ε ' j α j ) e ( h j –1 + k j –1 $\sqrt n$ ) soddisfano quindi la stessa relazione di ricorrenza di ordine 2. Poiché coincidono per j = 0 e per j = 1, sono uguali .

Metodo di calcolo

L'approccio della frazione continua offre un arricchimento del precedente metodo algoritmico per l'equazione di Pell-Fermat o la determinazione della frazione continua. Illustriamo questi metodi usando l'esempio n = 313 e mostriamo come Brouncker potrebbe effettivamente risolvere questa sfida in un'ora o due. Per definizione, m –1 = 0 e N (α 0 ) = 1 quindi, per ogni indice j ≥ 0:

m j è congruente a - m j –1 modulo N (α j ) e il suo quadrato è il più vicino possibile a 313;
N (β j ) = m j 2 - 313;
N (α j +1 ) = N (β j ) / N (α j ).

Troviamo quindi m 0 = 18, N (β 0 ) = 11, N (α 1 ) = 11, m 1 = 15, N (β 1 ) = –88, N (α 2 ) = –8, ecc.

Deduciamo f j dalla formula del paragrafo precedente: f 0 = m 0 = 18, f 1 = - (18 + 15) / 11 = –3, ecc.

Questo approccio evita i numeri grandi, ad eccezione di h j –1 e k j –1 , dove a j e b j sono i valori assoluti. Sono calcolati per j ≥ 1 dalla formula di induzione da f j .

Inoltre, se le norme di due α consecutivi sono uguali o opposte, risulta immediatamente dall'algoritmo che la β e le norme di α formano un palindromo. Più precisamente: se N (α r +1 ) = ε N (α r ) con ε = ± 1 allora, per induzione su k , β r + k = β r - k e N (α r + k +1 ) = ε N (α r - k ). Di conseguenza, α 2 r +1 è quindi invertibile (di norma ε) e - secondo l'espressione della successione di α in funzione di quella di β - uguale a ε r α r +1 / φ (α r ) = ε r α r α r +1 / N (α r ).

Costruiamo così la seguente tabella, dove vediamo che la situazione citata si verifica per r = 6 e ε = –1:

j	m j	N (β j ) = m j 2 - 313	N (α j ) = N (β j - 1 ) / N (α j - 1 )	f j = (–1) j (m j + m j - 1 ) / N (α j )	h j - 1 = f j - 1 h j - 2 + h j - 3	k j - 1 = f j - 1 k j - 2 + k j - 3
0	18	11	1	18	1	0
1	15	–88	11	–3	18	1
2	17	–24	–8	–4	–53	–3
3	19	48	3	–12	230	13
4	13	–144	16	2	–2 813	–159
5	14	–117	–9	3	–5.396	–305
6	12	–169	13	2	–19.001	–1074
7	14	–117	–13	2	–43.398	–2 453

La sequenza delle norme di α è quindi 1, 11, –8, 3, 16, –9, 13, –13, 9, –16, –3, 8, –11, –1, che fornisce un elemento di norma - 1:

\ alpha _ {{13}} = {\ frac {\ alpha _ {6} \ alpha _ {7}} {13}} = (19 \, 001 + 1 \, 074 {\ sqrt {313}}) ( 43 \, 398 + 2 \, 453 {\ sqrt {313}}) = 126 \, 862 \, 368 + 7 \; 170 \; 685 {\ sqrt {313}}.

(Questo numero è uguale anche come α 3 2 α 5 A / 9.) Ora resta che quadratura per ottenere la soluzione desiderata:

\ alpha _ {{26}} = \ alpha _ {{13}} ^ {2} = (126 \, 862 \, 368 + 7 \; 170 \; 685 {\ sqrt {313}}) ^ {2} = 32 \; 188 \; 120 \; 829 \; 134 \; 849 + 1 \; 819 \; 380 \; 158 \; 564 \; 160 {\ sqrt {313}}.

Il metodo chakravala permette quindi di risolvere manualmente questo tipo di calcolo. Lo stesso approccio, senza il calcolo delle colonne h j –1 e k j –1 , inutili per questo obiettivo, permette di determinare una frazione continua di √ 313 . Trovare la soluzione tale che la successione ( f k ) contenga solo valori positivi suppone di restringere la scelta a m k minore o uguale a 17. Troveremmo quindi la frazione continua di questo irrazionale quadratico : [17, 1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34 ].

Note e riferimenti

(EN) Clas-Olof Selenius , “ Motivazioni del processo chakravāla di Jayadeva e Bhaskara ” , Historia Mathematica , vol. 2,1975, p. 167-184 ( leggi in linea ).
(a) Victor J. Katz e Karen Parshall , Taming the Unknown , PUP ,2014, 504 p. ( ISBN 978-1-4008-5052-5 , leggi online ) , p. 122-123.
Georges Ifrah , Storia universale delle cifre: l'intelligenza degli uomini raccontata da numeri e calcoli , Robert Laffont, 1994 ( ISBN 978-2-70284212-6 ) .
Un'analisi precisa del suo lavoro matematico è disponibile nella tesi di dottorato di A. Keller commento Un indiano sul VII ° secolo - Bhaskara e Ganita-pada di Aryabhatiya [ leggere online ] .
(in) John Stillwell , Mathematics and Its History [ edizioni al dettaglio ], 2010, pag. 75-80 .
(in) BL van der Waerden , l'equazione di Pell in greco e matematica indù , Russ. Math Surveys 31 (5), 1976, pag. 210-225
(en) John J. O'Connor e Edmund F. Robertson , “equazione di Pell” , in mactutor , Università di St Andrews ( letto on-line ).
Vedi la pagina Pierre Fermat sul sito del comune di Beaumont-de-Lomagne .
Opere di Fermat , p. 334 .
Queste informazioni sono tratte dalla corrispondenza tra i diversi attori, pubblicata in (la) John Wallis, Commercium epistolicum de quæstionibus quibusdam matematicis nuper habitum Oxonii: Excudebat A. Lichfield, Impensis Tho. Robinson , 1658
Joseph-Alfred Serret , Opere di Lagrange , vol. Io, p. 671-731 : "Soluzione di un problema aritmetico".
(in) AA Krishnaswami Ayyangar , " Nuova luce sul metodo ciclico d'oro Chakravala di Bhaskara per risolvere equazioni indeterminate di secondo grado in due variabili " , J. Indian Math. Soc. , vol. 18, 1929-30, pagg. 225-248 ( leggi in linea ).
Questo caso applicato ad α = (10 + √ 92 ) 2 /4 = 48 + 5 √ 92 a 8 Standard 2 /4 2 = 4, permette Brahmagupta risolvere il suo primo esempio : Stillwell , p. 77 .
(in) Harold Edwards , L'ultimo teorema di Fermat: un'introduzione genetica alla teoria dei numeri algebrici , Springer al. " GTM " ( n o 50)2000, 3 e ed. , 407 p. ( ISBN 978-0-387-95002-0 , letto online ) , cap. I, § 9 ("Equazione di Pell") , p. 25-36.
Selenio 1975 aggiunge questo valore assoluto al denominatore, specificando due volte che Bhāskara non lo ha fatto. Edwards 2000 incorpora questo valore assoluto nella sua formulazione, senza nemmeno questa precisione.
(en) Stillwell , p. 79 .
Il metodo chakravala è, anche in questo, superiore a quelli di Eulero e Brouncker: oltre a ottenere il risultato in meno passaggi, prevede calcoli su numeri minori ( Selenius 1975 ).
Edwards 2000 , p. 35.
Suite A040295 di OEIS .

Vedi anche

Link esterno

(it) John J. O'Connor e Edmund F. Robertson , “Indian Mathematics: Redressing the balance, 8 VI. Pell's equation " , in MacTutor History of Mathematics archive , University of St Andrews ( leggi online ).

Bibliografia

(en) Leonard Eugene Dickson , History of the Theory of Numbers (en) [ dettaglio delle edizioni ], vol. II, Analisi diofantina
Jean Trignan, Introduzione ai problemi di approssimazione: frazioni continue, differenze finite , Éditions du Choix, 1994 ( ISBN 978-2-909028-16-3 )