Sulla risoluzione delle equazioni di Pell

Cristiano Teodoro

cristianoteodoro@virgilio.it

Sulla risoluzione delle equazioni di Pell

( )

About the solution of Pell’s equations

− ⋅

2 2

x D y ±

= 1

Sommario: questa nota e dedicata al calcolo dei valori numerici interi di x a di y soddisfacenti le due equazioni

− ⋅

2 2 = ± 1. Queste equazioni rientrano nel vasto ed interessante campo delle equazioni denominate

x D y numeri razionali).

diofantee od anche equazioni indeterminate, che sono equazioni da risolversi in interi (o in

Cercheremo di illustrare come si possono risolvere queste due equazioni anche se i valori interi più piccoli per x e y che le soddisfano sono numeri addirittura di diverse migliaia di cifre.

Daremo preliminarmente delle informazioni essenziali sulla Frazioni Continue; continueremo quindi con alcune principali osservazioni sullo sviluppo di un irrazionale quadratico, illustrando il metodo per il calcolo dei quozienti

a p q

parziali e per quello dei numeratori e dei denominatori delle ridotte della frazione continua, sviluppo

i i i

D D

dell’ irrazionale , essendo un non quadrato perfetto.

− ⋅

2 2

Passeremo quindi a considerare l’equazione = +1, nota sotto il nome di equazione di Pell,

x D y

dando l’algoritmo per il calcolo dei più piccoli valori interi per x e y che soddisfano l’equazione.

− ⋅

2 2 = che presenta per la sua risoluzione lo

Prenderemo in considerazione anche l’equazione x D y -1

stesso tipo di algoritmo, ma che a differenza della prima equazione non risulta sempre risolvibile. Per questa equazione daremo anche alcuni tipi di valori di D per i quali non si hanno soluzioni.

Per ottenere dei risultati concreti per le due equazioni viene riportato in questa nota il breve listato in linguaggio Qbasic di un unico programma limitato alla loro risoluzione per valori di x e di y costituiti da non più di 15 cifre; soluzioni che si possono ricavare non andando oltre l’implicazione dell’aritmetica a doppia precisione.

In allegato daremo invece il listato di un programma più complesso, suddiviso in due principali parti, la prima

15

10 , la seconda, implicante una aritmetica a

per soluzioni dell’equazione aventi valori per x e y minori di

7

10

precisione multipla in Base , per soluzioni con valori di x e y anche molto grandi (aventi centinaia o addirittura migliaia di cifre) e dipendenti in modo non prevedibile dal valore di D. Riporteremo in allegato anche alcuni esempi di risultati ottenibili con il suddetto programma, mettendo in evidenza i valori numerici di x e di y, quali valori interi minimi soddisfacenti i due tipi di equazione ed i relativi tempi di calcolo.

Abstract

Abstract: the aim of this paper is to illustrate the integers x and y, wich satisfactory values of the two Equations

− ⋅ = ±

2 2

x D y 1 . These equations belong to the set of diophantine or indeterminate equations. In this paper we explain their solutions even if their satisfactory x and y values are large numbers.

First we give some basic informations concerning the Continued Fractions, then we continue with some main

by explaining the method of his partial

remarks pertinent the development of quadratic irrational number D

quotients computation and also the computation of numerators and denominators of his convergents.

− ⋅ =

2 2

x D y 1 and we give the algorithm for the computation of the least

Then we consider the Pell equation

x and y solutions. − ⋅ = −

2 2 , wich has the same algorithm, but that can’t always have any

We also consider the equation x D y 1

solutions. For this equation we give also some kinds of the D values that have no solution.

In this paper we show one algorithm for both equations, limited to solutions of x and y values consisting of numbers

15

10 , fullfilled by one short program in Qbasic language. This restriction is due only at the use of

smaller than

double precision arithmetic.

At the end we enclose also the list pertinent a more complex program, still in Qbasic language, divided into two

15

10 , the

main parts, the first regarding solutions of equations wich have satisfactory x and y values smaller than

7

10

second using an original Radix multiple-precision arithmetic for equations with large x and y solutions, namely satisfactory values with several tens of digits or some hundreds and even thousands of digits.

We report also, as enclosures, some results by using this program, highligthing the least x and y values, such as solutions of the tested equations, and their computation time.

1

Con il nome di equazione di Pell (o più appropriatamente di Pell - Fermat ) è nota l’equazione

− ⋅ =

2 2 − ⋅

2 2

1 . Prenderemo in considerazione anche l’equazione = 1, che per

x D y x D y -

la sua risoluzione presenta lo stesso tipo di algoritmo. ,

Sui loro sviluppi storici e in generale per loro notizie si rimanda a [Bei], [Dav], [Old].

Queste equazioni rientrano nel vasto ed interessante campo delle equazioni denominate diofantee o indeterminate, che sono equazioni da risolversi in interi (o in numeri razionali).

V’è subito qui da specificare che mentre l’equazione col termine noto positivo risulta sempre

non sempre lo è.

risolubile, l’altra equazione col termine noto -1

(

1

)

In effetti è facile dimostrare che non esistono valori interi di e di soddisfacenti la

x y

( 2 ) :

suddetta equazione per i seguenti tipi di valori di D

• D ≡ 0 (mod 4) vale a dire per D = 4 k
• D ≡ 3 (mod 4) vale a dire per D = + 3
• D ≡ 6 (mod 8) vale a dire per D = 8 k 6

Dove = 1, 2, 3, 4,……….

k − ⋅ = −

2 2 risulta sempre risolvibile se

Inversamente, si dimostra [Nag] che l’equazione 1

x D y

è un numero primo ≡ 1 (mod 4); ciò risulta senz’altro utile se già è noto che D è

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

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