Sulla risoluzione delle equazioni di Pell

D

effettivamente primo.

Ci si propone qui di esporre e sviluppare alcuni argomenti dedicati alla loro risoluzione, e quindi

e che le soddisfano, con l’impiego dello sviluppo

calcolare i valori interi minimi per x y

in frazione continua.

dell’irrazionale D

Nei riguardi delle frazioni continue, per le notazioni ed i simboli matematici delle varie

grandezze in gioco e per le giustificazioni teoriche relative alle formule matematiche che

vengono impiegate qui di seguito, si rimanda a [Old] e [Dav] .

viene indicata come segue [Old]:

La frazione continua sviluppo di un generico irrazionale D

= [ , , , … , 2 , , , … , 2 , , , … , 2 , , ..……] (1a)

a a a a a a a a

a a a a a a a

D 1 2 1 2 1 2 1 2

n n n

3 3 3 3

 

con = e dove uguali simboli per gli altri indicano uno stesso valore numerico.

a

D

a i

1  

Con il simbolo generico si definisce l’intero più grande inferiore a

x x.

Tutti i vari a partire da prendono il nome di dello sviluppo di .

a quozienti parziali

a D

i 1

I quozienti parziali , , …… , 2 che si ripetono indefinitamente, formano il

a a periodo

a a

n

2 3 1

dello sviluppo . E’ consuetudine indicare il suddetto sviluppo come segue:

a

= [ , , , ,.........

..... , 2 ], dove l’insieme dei simboli sopralineati formano il

a a a a a

D 1 n

2 3 4 1

.

periodo può comprendere un numero pari o dispari di valori e può essere formato da pochi

Il periodo come da molti, dipendendo il loro numero in modo non prevedibile dal

quozienti parziali .

valore stesso di D

⋅

4 k = ⋅ ⋅ 2

2 2

x 4 k y

(1) per D = si ha - 1; è evidente che x e quindi anche x devono risultare di valore dispari;

⋅ + ⋅ +

8 m 1 8 m 1

poiché poi il quadrato di un numero dispari può sempre porsi sotto la forma si ha =

⋅ ⋅ −

2

4 k y 1 ⋅ = ⋅ ⋅ −

2

⋅ 4 m 2 k y 1

= , uguaglianza palesemente

e infine

da cui ⋅ ⋅ −

2

8 m 4 k y 2

. Analoghe considerazioni si possono fare per gli altri tipi di valori di D.

impossibile − ⋅

2 2

x D y

(2) Considerando i tre tipi di valori di D elencati, l’equazione = – 1 non risulta risolubile per almeno

il 62,5 % dei valori di D. 2

Diamo qualche esempio.

D = 28 il è formato da 4 si ha 28 = [ 5,

Per 3,2,3,10 ] come

periodo quozienti parziali:

sarà mostrato più avanti ;

= 37 il è formato da un solo : si ha 37 = [a,2a] = [ 6,12 ]

per periodo quoziente parziale

D = 309 il è formato da 26

per periodo quozienti parziali

D

per = 408 il è formato da un

periodo quoziente parziale

D = 409 il è formato da 21

per periodo quozienti parziali

D

per = 410 il è formato da un

periodo quoziente parziale

D

per = 30001 il è formato da 284

periodo quozienti parziali;

D = 123456811 il è formato addirittura da 20006 .

per periodo quozienti parziali

D

Poiché la conoscenza del valore numerico di tutti i formanti il è

quozienti parziali periodo

indispensabile per la risoluzione dell’equazione di Pell, occorre trovare un algoritmo efficiente e

veloce per il loro calcolo esatto

.

Un semplice metodo di calcolo derivato da quanto accennato in [Chr], [Dav], [Old] può indicare

la strada per sviluppare un algoritmo di tipo iterativo illustrato più sotto.

Prima però vediamo di esporre quanto segue.

= in frazione continua;

Sia da sviluppare l’irrazionale x D

1

  come già detto indica l’intero più grande inferiore a .

Il simbolo generico x x

i i

1  

= = +

Si ponga = x

con

D x a a

1 1

1 1 x 2 1

Risolvendo l’equazione in si ottiene =

x x

2 2 −

x a

1 1

1 1

 

con

si ponga ora = + = x : si ottiene x =

x a a

2 2 2 2 3 −

x x a

3 2 2

1 1

 

con

x = a + a = x : si ottiene =

proseguendo: x

3 3 3 3 4 −

x x a

4 3 3

= ………………………………………………………………

x 4

x = ………………………………………………………………

5

.……………………………………………………………………

1

1  

con

x = a + a = x : si ottiene x =

− − − −

1 1 1 1

i i i

i i −

x x a

− −

1 1

i i i

1  

con

x …= a + a = x ……………………………….

i i

i i x +

i 1

……………………………………………………………………. ⋅

Ci si ferma nel procedimento quando si ottiene un valore di x per cui a = 2 in quanto

a

i i 1

si dimostra [Old] che nello sviluppo di un irrazionale del tipo suddetto gli ulteriori quozienti

parziali si ripetono come mostrato in (1a). 3 x e quindi i

Ma come si deve procedere per trovare nella maniera più opportuna i vari i

a ? Vediamo con un esempio numerico concreto di chiarire il procedimento.

corrispondenti i

Siano da calcolare i quozienti parziali della frazione continua relativa a 28 .

1 1  

= 5 + dove

Posto = 28 si considera = + = = 5 è il più grande

x x a a 28

1 1 1 1

x x

2 2

intero inferiore a , cioè alla radice quadrata di 28 .

x

1 1

1

Risolvendo la suddetta equazione in si ottiene: = =

x x

2 2 − −

x a 28 5

1 1

Risulta opportuno (vedi Nota) non calcolare subito il valore numerico di e da questo ricavare

x 2

+ +

28 5 28 5

, ma razionalizzare il suo denominatore ottenendo così = = da cui si

a x

2 2 − 2 3

28 5

a = = 3 . Ripetendo per x lo stesso tipo di procedimento fatto sopra si pone

trae:  

x

2 3

2 +

1 1

28 5 1 3

a . Si ha allora : da cui

= + = 3 + x = =

x 2

2 3 + −

x x

3 28 5 28 4

−

3 3 3

3

Razionalizzando di nuovo il denominatore si ottiene dopo qualche passaggio:

+

28 4 .

 

= =

a x

x = 2 Continuando questo tipo di procedimento

da cui si trae 3 3

3 4 +

28 4   =

a x

x da cui si ricava

si ottiene: = = 3

per i successivi x 4 4

i 4 3  

a x

+

x = 28 5 da cui finalmente = = 10

Proseguendo si trova 5 5

5

a a

Avendo ottenuto per un valore uguale a 2 ci si ferma in quanto gli ulteriori si ripetono

a

5 1 i

come risulta da (1a). Si indicherà pertanto 28 = [ 5, 3,2,3,10 ] . a

nel calcolo dei vari si arriva

In effetti la teoria ci assicura che per un irrazionale D i

 

⋅ , che i valori numerici dei quozienti parziali sono tutti

sempre ad un valore pari a 2 N

numeri interi e che essi si ripetono, escludendo , in ogni periodo.

a

1

28 si può poi osservare che per il generico valore

Da quanto mostrato con l’esempio relativo a  

+ +

D c D c

 

i i

x x = a x

di vale la seguente formula: da cui = =  

i i i i

b b

 

 

i i

: il vantaggio di razionalizzare ogni volta il denominatore comporta la possibilità di realizzare per il calcolo dei quozienti

Nota

parziali l’algoritmo illustrato, che presenta una maggiore precisione di calcolo. Ciò risulta evidente soprattutto quando il

che ha un periodo

periodo è formato da molti quozienti parziali. Prendiamo un esempio tipico: per l’irrazionale 309

costituito da 26 quozienti parziali, volendo calcolarli direttamente, senza il processo di razionalizzazione del denominatore di

x

ogni , e quindi senza il conseguente uso dell’algoritmo iterativo di seguito illustrato, tali quozienti, già dal 19° in poi

i

risulterebbero errati anche con l’uso della doppia precisione. In corrispondenza poi del 27° quoziente parziale, invece di

 

a a

⋅ 309

trovare un valore = 2 = 34, come deve essere, si otterrebbe un valore = 5 e quindi decisamente errato.

27 27

4

Non è difficile poi vedere, sempre osservando passo per passo lo sviluppo di 28 , che i valori

 

+

D c −

i 1

c b c b a dalle seguenti

di e di sono legati ai precedenti valori , e =  

− − −

1 1 1

i i i i i −

bi 1

 

   

+

− ⋅ D c

D c c

⋅ − =

i i i

c = a b c ; b = dalle quali si può ricavare a

relazioni:  

− − −

i i 1 i 1 i 1 i i b

b  

 

−

i 1 i

b occorrerà calcolare prima quello di c .

E’ evidente che per calcolare il valore di i i

Sfruttando queste relazioni si può realizzare allora un algoritmo di tipo iterativo per il calcolo

a mostrato qui di seguito:

dei quozienti parziali i ALGORITMO PER IL CALCOLO

DEI QUOZIENTI PARZIALI a di D

i

Si considerino le seguenti grandezze:  

a , b , c con i valori iniziali = ; = 1; = 0

a D b c

i i i 1 1 1

vale il seguente algoritmo iterativo:

⋅

c = a b – c (1)

− − −

i i 1 i 1 i 1

− ⋅

D c c

i i

b = (2)

i b −

i 1

 

+

D c i

a = (3)

 

i b

 

 

i

i

con = 2, 3, 4…….. c b i

e dell’iterazione possono essere calcolati

Come si vede chiaramente i valori dei parametri i i

con i valori degli stessi parametri trovati nella iterazione precedente. Può essere poi calcolato

a .

con la (3) il valore del quoziente parziale i

Si fa osservare che in ogni ciclo le tre suddette relazioni devono essere eseguite rigorosamente

nella successione indicata, vale a dire deve essere eseguita prima la (1), quindi la (2) e infine la

i

(3). Con il primo ciclo o iterazione dell’algoritmo suddetto, vale a dire per = 2, si troverà il

a

, per i = 3 il valore di e cos&igrav