Cap. 1. – EQUAZIONI E SISTEMI DIOFANTEI - …verardi/T d N Verardi cap I.pdfPiù in dettaglio,...

Teoria dei numeri I 2013-14, modulo prof. Verardi – Cap. I: equazioni e sistemi lineari diofantei

17

Cap. 1. – EQUAZIONI E SISTEMI DIOFANTEI

I sistemi di equazioni che hanno i coefficienti ed i termini noti interi, e di cui si

cercano le soluzioni intere li chiamerò per semplicità diofantei.

Ovviamente, i meno difficili sono i sistemi lineari. In questo caso, possiamo

considerarli casi particolari di sistemi lineari nel campo razionale, quindi applicare

algoritmi e teoremi di Algebra lineare ben noti e validi in tutti i campi, quali Gauss-Jordan e

Rouché-Capelli. In particolare, per un sistema lineare di m equazioni ed n incognite, dette A

la matrice incompleta, B la colonna dei termini noti,

!

C = A B[ ] la matrice completa e X la

colonna delle incognite, avremo la consueta condizione necessaria per l’esistenza di

soluzioni del sistema

!

A " X = B: i due ranghi di A e C devono essere uguali: r(A) = r(C).

Questo però non garantisce che le soluzioni siano intere.

Per esempio, per un sistema “di Cramer”, nel quale si ha m = n e r(A) = r(C) = n, nel campo

razionale la matrice A è invertibile e si ha

!

X = A"1 # B . Tuttavia, occorre ricordare che il

calcolo di

!

A"1 richiede di dividere per det(A): se non è ±1, si potrebbero trovare radici non

intere. Più in dettaglio, ricordando la formula di Cramer, detta

!

A j la matrice ottenuta

sostituendo alla j-esima colonna di A la colonna B dei termini noti, l’incognita

!

xj è uguale a

!

det A j( )det A( )

. Se det(A) divide tutti quei determinanti al numeratore, la soluzione è intera.

Per esempio, l’equazione

!

ai " xii=1

n# = 0 nello spazio n-dimensionale razionale rappresenta un

iperpiano, e possiede una base

!

B1,K, Bn"1{ } a coordinate razionali. Per ogni j,

!

1 " j " n #1

sia

!

m j il minimo comune denominatore delle n coordinate di

!

Bj. A quest’ultimo

sostituiamo

!

m jBj ed otterremo una nuova base a coordinate intere. Non solo, ma, volendo,

possiamo dividere ogni vettore per il MCD delle sue coordinate, ottenendo una base intera

ad elementi primitivi

!

E1,K, En"1{ } . Allora ogni

!

X = k j "E jj=1

n#1$ , k j % Z è soluzione intera

dell’equazione

!

ai " xii=1

n# = 0. Tuttavia, non vale il viceversa, ossia non ogni base intera dà


18

tutte le soluzioni intere. Per esempio, una base intera per l’equazione

!

5x "3y " z = 0 è

!

217

"

#

$ $ $

%

&

' ' ' ,

231

"

#

$ $ $

%

&

' ' '

(

) *

+ *

,

- *

. * , ma la soluzione

!

112

"

#

$ $ $

%

&

' ' ' non è combinazione lineare a coefficienti interi di quella base.

Invece, ponendo

!

x = c1y = c2z = 5c1 "3c2

#

$ %

& %

, otteniamo la base

!

105

"

#

$ $ $

%

&

' ' ' ,

01(3

"

#

$ $ $

%

&

' ' '

)

* +

, +

-

. +

/ + , che ci dà tutte le soluzioni

intere.

Passiamo quindi ad esaminare la teoria dei sistemi lineari diofantei, incominciando dal caso

di una sola equazione.

§ 1.1. Equazioni diofantee lineari in Z.

Dai corsi di Algebra I e II è noto che l’anello Z degli interi relativi ha gli ideali

principali. La dimostrazione è semplice: l’ideale nullo è generato da 0. Un ideale non nullo I

è un sottogruppo additivo, quindi se contiene un elemento x, contiene anche l’opposto –x,

quindi contiene almeno un numero positivo. Per il principio del minimo, l’insieme dei

numeri positivi di I ha il minimo m. Se dividiamo ogni x∈I per m, otteniamo

!

x = m "q + r ,

con

!

0 " r < m . Allora,

!

r = x "m #q $ I , quindi essendo minore di m, non può essere positivo.

Dunque, r = 0 e x è multiplo di m.

Ciò posto, siano a,b∈Z, non nulli. L’insieme

!

I = c " Z c = a # x + b # y, x, y " Z{ } delle

combinazioni lineari di a e b a coefficienti interi è un ideale di Z (dimostrazione per

esercizio) e quindi esiste d∈Z che lo genera. Poiché anche –d è un suo generatore, possiamo

supporre d > 0. Dunque, ogni c∈I è un multiplo di d. D’altra parte, anche a e b

appartengono ad I, quindi sono multipli di d. Allora d è un divisore comune di a e b. Poiché

d∈I, esistono u,v∈Z tali che

!

d = a "u + b " v. Allora ogni altro divisore comune k di a e b è

divisore di d: infatti da

!

a = k " # a b = k " # b

$ % &

, segue

!

d = a "u + b " v = k " # a "u + # b " v( ) . Ne segue:

d = MCD(a,b). Ricordiamo infine che tra numeri positivi si ha: se x divide y allora x ≤ y.

Abbiamo allora dimostrato il

TEOREMA 1.1.1. (Bézout). Sono equivalenti:

a) d = MCD(a,b) (positivo)

b) d è il minimo intero positivo tale che esistono u,v∈Z tali che

!

d = a "u + b " v.


19

COROLLARIO 1.1.2. I numeri a e b sono coprimi se e solo se esistono u,v∈Z tali che

!

1 = a "u + b " v.

NOTA. Come trovare i due interi u e v del teorema è mostrato negli esempi che vedremo: si usa il

procedimento euclideo delle divisioni successive ed uno schema facilmente eseguibile anche con

Excel, perché basato sul calcolo ricorsivo dei coefficienti

!

um, vm tali che

!

rm = a "um + b " vm ,

dove

!

rm è l’m−esimo resto nel citato procedimento.

A questo punto occupiamoci dapprima delle equazioni diofantee lineari in due

incognite. Nell’introduzione abbiamo visto un esempio in N, ma qui lavoriamo in Z,

l’ambiente più adatto. Una tale equazione si presenta nella forma

!

a " x + b " y = c , con a, b, c

interi. Il caso in cui a = 0 oppure b = 0 è lasciato per esercizio.

Siano quindi a, b non nulli. Come sempre, occorre esaminare i tre aspetti del

problema: esistenza di soluzioni, numero delle soluzioni, algoritmi risolutivi.

Siano nel seguito: d = MCD(a, b), a = da’, b = db’.

LEMMA 1.1.3. Esistenza. Esiste una soluzione dell’equazione diofantea

a

!

a " x + b " y = c se e solo se d = MCD(a,b) divide c.

Dimostrazione. Segue subito dal fatto che c appartiene all’ideale

!

I = a, b{ }( ), di cui d è

un generatore.

Volendo provarlo esplicitamente, siano x, y interi tali che

!

a " x + b " y = c . Allora:

c = ax + by = da’x + db’y = d(a’x + b’y)

quindi d divide c. D’altra parte, se d divide c, posto c = dc’, esistono u, v interi tali che

!

d = a "u + b " v, quindi:

a(c’u) + b(c’v) = c’d = c

e una soluzione (x, y) = (c’u, c’v) esiste.

LEMMA 1.1.4. Numero soluzioni. Se esiste una soluzione dell’equazione

diofantea

!

ax + by = c allora ce ne sono infinite.

Dimostrazione. Sia (u,v) una soluzione dell’equazione

!

ax + by = c . Consideriamo

l’equazione omogenea associata

!

ax + by = 0 . Dividiamo per d ed otteniamo

!

" a x + " b y = 0 ,

ossia a’x = −b’y. Poiché MCD(a’,b’) = 1, allora, per il lemma di Euclide, a’ divide y, ossia


20

esiste k intero tale che y = ka’. Ma allora x = -kb’. Inversamente, per ogni k intero, la coppia

(-kb’, ka’) è soluzione dell’equazione omogenea associata.

Pertanto, per ogni k intero si ha

a(u-kb’) + b(v+ka’) = au + bv +a(-kb’)+b(ka’) = c+0 = c,

ossia la coppia

!

u " k # $ b , v + k # $ a ( ) è soluzione dell’equazione data per ogni k intero.

Inversamente, per ogni altra soluzione (u’,v’) dell’equazione data, la differenza

!

" u #u, " v # v( )

è soluzione dell’equazione omogenea associata. Allora esiste k intero tale che

!

" u #u = #k $b" v # v = k $a

% & '

,

ossia

!

" u = u # k $b" v = v + k $a

% & '

. Abbiamo così un insieme numerabile di soluzioni, una per ogni k intero.

ALGORITMI RISOLUTIVI. Un algoritmo per risolvere l’equazione diofantea lineare

!

a " x + b " y = c , in cui d = MCD(a, b) e c = dc’, è già stato indicato:

• con l’algoritmo euclideo si determinano u, v tali che au + bv = d

• si trova la soluzione particolare

!

x0, y0( ) = u " # c , v " # c ( )

• si aggiungono le soluzioni dell’equazione omogenea associata:

-

!

x, y( ) = x0 " k # $ b , y0 + k # $ a ( ) , k∈Z.

Tuttavia, la soluzione particolare potrebbe essere migliorata, nel senso che potrebbe essere

utile “minimizzarla”, ossia trovare soluzioni con

!

x0 < " b o

!

y0 < " a . Vediamo come, con un

esempio.

ESEMPIO 1.1.5. Vediamo l’equazione diofantea 120x + 85y = 50.

Si ha MCD(120, 85) = 5, che divide 50. Allora risolviamo dapprima l’equazione

!

120u + 85v = 5 (o equivalentemente 24u + 17v =1).

resti 120 85 35 15 5 0

!

un 1 0 1 -2 5 -17

!

vn 0 1 -1 3 -7 24 quozienti 1 2 2 3

NOTA. I calcoli qui ed altrove sono svolti con Excel: si inseriscono i due numeri in A1 e B1, poi 1 e 0 in A2 e

B2, 0 ed 1 in A3 e B3. In B4 si colloca il quoziente tra A1 e B1 (=int(A1/B1)) mentre C1 = A1-B1*B4 è il resto.

Si ha poi C2=A2-B4*B2, C3=A3-B3*B4.


21

Per calcolare C4 si prolunga B4 col riempimento

automatico, poi le colonne successive sono ottenute

dalla C col riempimento automatico. Ci si ferma

quando il resto è zero.

Le soluzioni sono dunque: u = 5, v = -7. Poiché c’ = 50/5 = 10, si ha così:

!

x0, y0( ) = u " # c , v " # c ( ) = 50,$70( )

Si ha poi a’ = 120/5 = 24, b’ = 85/5 = 17. Pertanto, la soluzione generale è:

!

x, y( ) = x0 " k # $ b , y0 + k # $ a ( ) = 50 "17k,"70 + 24k( ) , k∈Z.

Per migliorare la forma delle soluzioni, dividiamo 50 per 17, ottenendo quoziente 2 e resto

16, oppure quoziente 3 e resto -1.

Nel primo caso si ha 50 – 17k = 16 – 17k’, dove k’ = k-2, e si ha anche

-70+24k = -70+24(k’+2) = -22+24k’.

Perciò (x, y) = (16-17k’, -22+24k’), k’∈Z.

Nel secondo caso, posto k” = k+3, si ha

!

x = "1+17 # # k y = 2+ 24 # # k

$ % &

, k” ∈Z. Quest’ultima forma delle

soluzioni è assai più semplice delle precedenti.

NOTA. Sia

!

x, y( ) = 50 "17k,"70 + 24k( ) la soluzione trovata con l’algoritmo. Facciamo variare per il

momento k in R e cerchiamo la soluzione di norma minima. Minimizziamo cioè

!

x2 + y2 al variare di

k. Ossia, minimizziamo la funzione

!

f k( ) = 865k2 "5060k + 7400 . Annullando la derivata di f,

(oppure, per chi non sa le derivate, prendendo l’ascissa k del vertice della parabola grafico di

questa funzione), troviamo

!

k =506173

" 2,92. Gli interi più prossimi sono

!

k = 2 e

!

k = 3, ma 3 è più

vicino al valore trovato. Per questi due valori interi di k si trovano le due soluzioni particolari

(16,−22) e (-1, 2) già note, e la seconda è migliore dell’altra.

Nel caso generale di ax + by = c si trova

!

k =" # a $ y0 " # b $ x0( )

# a 2 + # b 2.

ESERCIZIO 1.1.6. Risolvere l’equazione diofantea 12856⋅x+3347⋅y = 329

Troviamo dapprima d = MCD(12856, 3347) ed i due numeri u, v.

12856 3347 2815 532 155 67 21 4 1 0 1 0 1 -1 6 -19 44 -151 799 -3347 0 1 -3 4 -23 73 -169 580 -3069 12856

3 1 5 3 2 3 5 4 #


22

Allora 12856⋅799+ 3347⋅(-3069) = 1, quindi i due numeri sono coprimi ed il problema ha

soluzione.

Una soluzione particolare è allora (799⋅329, -3069⋅329) = (262871, -1009701)

Poiché i due coefficienti sono coprimi, segue che la soluzione generale è data da:

!

x = 262871"3347 #ky = "1009701+12856 #k

$ % &

.

Per trovare soluzioni con numeri più vicini a zero, usiamo la formula sopra trovata:

!

k =" # a $ y0 " # b $ x0( )

# a 2 + # b 2= 78,539...

I due interi più prossimi a questo valore sono 78 e 79. Abbiamo allora le due forme:

!

x = 1805"3347 #ky = "6933+12856 #k

$ % &

oppure

!

x = "1542"3347 #ky = 5923+12856 #k

$ % &

Esistono altri metodi per trovare queste soluzioni, di cui uno dovuto ad Eulero, ma sono più

lenti e complessi dei due indicati.

Il caso più generale di equazione lineare in n ≥ 3 incognite presenta risultati simili

per quanto riguarda l’esistenza ed il numero delle soluzioni:

PROPOSIZIONE 1.1.7. Sia data l’equazione

!

ai " xii=1

n# = c, con

!

0 " ai∈Z ∀i e c∈Z.

a) Essa ha soluzioni intere se e solo se il massimo comune divisore dei coefficienti

!

ai

divide il termine noto c.

b) Se ha una soluzione

!

x 1,K, x n( ) " Zn , allora ogni altra soluzione si trova sommando

ad essa le soluzioni intere dell’equazione omogenea associata

!

ai " xii=1

n# = 0.

Dimostrazione. a) La necessità è immediata. Per la sufficienza, dividiamo coefficienti e

termine noto per il loro MCD. Ossia, supponiamo che il MCD dei coefficienti sia 1.

Procediamo per induzione rispetto ad n ≥ 2. Il caso n = 2 sappiamo che ha soluzioni.

Sia n > 2. Se ci sono due coefficienti, per esempio

!

an"1 ed

!

an , coprimi o tali che il loro

MCD divida c, allora basta porre

!

xi = 0 "i # n $2 ed il problema si riconduce al caso delle

due incognite. Avremo allora una soluzione

!

0,K, 0n"2

1 2 4 3 4 , x n"1, x n#

$

% %

&

'

( ( ) Zn del sistema.


23

Altrimenti, se MCD(

!

an"1,

!

an ) = d, introduciamo un’incognita ausiliaria y e risolviamo il

sistema

!

an"1 # xn"1 + an # xn = d # y

ai # xii=1

n"2$ + d # y = c

%

& ' '

( ' '

. La prima equazione ha soluzioni per ogni y, la seconda

ha n-1 incognite ed i coefficienti coprimi, quindi per l’ipotesi induttiva ha una soluzione

!

x 1,K, x n"2, y ( ) # Zn"1. Sostituiamo

!

y alla y nella prima equazione e risolviamo

!

an"1 # xn"1 + an # xn = d # y . Avremo allora anche gli interi

!

x n"1, x n , quindi avremo una

soluzione

!

x 1,K, x n"2, x n"1, x n( ) # Zn del sistema dato.

b) Si dimostra come nel caso n = 2.

ESERCIZIO 1.1.8. Risolvere l’equazione diofantea 21x+35y+15z = 8.

Svolgimento: dato che MCD(21,35) = 7, introduciamo l’ulteriore incognita t tale che:

!

21x + 35y = 7t7t +15z = 8

" # $

.

La seconda equazione ha soluzione (-1,1). Allora, sostituendo t = -1 nella prima, si ottiene

21x+35y = -7, ossia 3x+5y = -1. Una soluzione è (3,-2), quindi (3,-2,1) è una soluzione

dell’equazione data: 21⋅3+35⋅(-2)+15⋅1 = 8.

Ce ne sono altre? L’equazione omogenea associata è 21x+35y+15z = 0.

Poiché MCD(21,35) = 7, allora 7 divide 15z, ossia z = 7z’. Abbiamo allora 3x+5y+15z’ = 0.

Analogamente, 5 = MCD(5,15) divide 3x, quindi x = 5h. Ne segue 3h+y+3z’ = 0.

Infine, 3 = MCD(3,3) divide y, quindi y = 3k, e resta: h+k+z’= 0.

Ricaviamo di qui z’ = -h-k, quindi z = -7h-7k, dunque (5h, 3k, -7h-7k) è la soluzione

generale dell’equazione omogenea associata.

Allora, le soluzioni dell’equazione 21x+35y+15z = 8 sono (3+5h, -2+3k, 1-7h-7k), con h, k

interi qualsiasi.

In questo caso particolare, le stesse soluzioni le possiamo trovare anche così: risolviamo

l’equazione 21x+35y+15z = 0 rispetto a z:

!

z = "75

x " 73

y e poniamo x = 5h, y = 3k e allora la

base è

!

50"7

#

$

% % %

&

'

( ( ( ,

03"7

#

$

% % %

&

'

( ( (

)

* +

, +

-

. +

/ + , corrispondente a z = -7h-7k trovata sopra.


24

§ 1.2. Sistemi diofantei lineari in Z.

Osserviamo prima di tutto che una matrice quadrata ad elementi interi ha il

determinante intero, perché ottenuto solo con somme, differenze e prodotti.

Sia M una matrice di tipo mxn e supponiamo m ≤ n. Chiamiamo divisore d di M il

massimo comune divisore dei determinanti dei suoi minori(1) di ordine massimo, ossia di

quelli di ordine m.

Se M è quadrata, allora d = det(M). Se r(M) < m, tutti i minori d’ordine massimo sono

nulli, quindi d = 0. Vale allora il seguente teorema:

TEOREMA 1.2.1. Un sistema lineare diofanteo di m equazioni ed n incognite, con

!

m " n ed r(A) = m, ha soluzioni intere se e solo se la matrice incompleta A e la completa C

hanno lo stesso divisore.

Traccia della dimostrazione. Vediamo prima due casi particolari:

a) Nel caso di una sola equazione, la matrice incompleta A è di tipo 1xn, ed il suo

divisore è il MCD dei coefficienti: per avere soluzioni intere, dunque, esso deve dividere

anche il termine noto, come già sappiamo.

b) Nel caso m = n, i minori d’ordine massimo di C sono la matrice A e le matrici

ottenute dalle matrici

!

A j, quelle che compaiono nei numeratori delle formule di Cramer,

riportando la colonna B all’ultimo posto, il che al massimo cambia il segno del loro

determinante. Poiché il divisore di A è d = det(A), ecco che A e C hanno lo stesso divisore se

e solo se d divide ciascuno dei minori

!

det A j( ) ; come già rilevato all’inizio del capitolo, in

questo caso le soluzioni sono intere.

Un metodo per dimostrare il teorema e trovare le soluzioni del sistema è quello di

“completare” il sistema stesso aggiungendovi equazioni fino a portarlo ad un sistema di

Cramer con le stesse soluzioni e gli stessi divisori.

Chiamiamo primitivo un vettore-colonna (o vettore-riga) a coefficienti interi coprimi.

Denotiamo poi con

!

Mt la trasposta di una matrice M.

(1) In molti testi un minore di una matrice è una sottomatrice quadrata, mentre in altri è il suo determinante. Qui intenderemo la sottomatrice quadrata.


25

LEMMA 1.2.2. Data una matrice

!

Am di tipo mxn, con m < n e rango m, esistono

infiniti modi per ampliarla ad una matrice quadrata

!

An il cui determinante sia, in valore

assoluto, uguale al divisore di

!

Am.

L’algoritmo è il seguente:

1. Si sceglie un vettore primitivo

!

X1 soluzione del sistema omogeneo

!

Am " X = 0

2. Si sceglie un vettore intero primitivo

!

R1 soluzione dell’equazione

!

X1( )t " X = 1.

3. Si aggiunge la riga

!

R1( )t come ultima riga alla matrice

!

Am, ottenendo una

matrice

!

Am+1. Si dimostra che

!

Am ed

!

Am+1 hanno lo stesso divisore.

4. Se m+1 < n, si ripete il procedimento a partire da

!

Am+1.

Osserviamo che il procedimento non è proprio agevolissimo, ma non richiede il

calcolo preventivo del divisore d, che si può trovare solo alla fine come

!

det An( ). Ciò posto:

TEOREMA 1.2.3. Sia dato il sistema lineare diofanteo A×X = B, con m equazioni ed

!

n " m incognite, tale che r(A) = m e che le matrici A e

!

C = A B[ ] abbiano lo stesso divisore

d. Le soluzioni intere del sistema sono tutte e sole quelle che si ottengono risolvendo il

sistema di Cramer A’×X = B’, dove A’ è un ampliamento di A ottenuto come nel lemma

precedente, e i termini noti delle ultime n-m equazioni sono parametri interi arbitrari.

Dimostrazione. Mediante l’algoritmo sopra descritto, possiamo trasformare il vettore

primitivo

!

X1 soluzione del sistema omogeneo

!

A " X = 0 aggiungendovi uno zero come n+1-

esima coordinata, in modo che sia soluzione del sistema omogeneo

!

C " # X = 0. Se ora

aggiungiamo come n+1-esima coordinata ad

!

R1 il parametro intero

!

t1, abbiamo la

possibilità di ingrandire anche C senza cambiarne il divisore. Iteriamo il procedimento fino

a ottenere la matrice A’, e contestualmente anche C’: le due matrici hanno gli stessi divisori

di A e C, e se e solo se d(A) = d(C) si ha d(A’) = d(C’), qualunque sia il valore intero

attribuito agli n-m parametri. Pertanto, al variare di questi ultimi abbiamo tutte soluzioni

intere del sistema dato.

Viceversa, presa una soluzione intera

!

X del sistema A×X = B, se si esegue il prodotto

!

" A # X si trova un vettore

!

" B le cui prime m coordinate sono quelle di B e le altre sono valori

interi, che si possono attribuire ai parametri

!

t1,K, tn"m.


26

ESEMPIO 1.2.4. a) Si abbia il sistema lineare diofanteo

!

5x1 + 4x2 + 7x3 = 26x1 + 5x2 + 4x3 = 7

" # $

. In questo caso,

poiché

!

5 46 5

= 1, basta risolvere, per esempio con la regola di Cramer, il sistema

!

5x1 + 4x2 = "7x3 + 26x1 + 5x2 = "4x3 + 7

# $ %

, ottenendo:

!

x1 =2"7t 47" 4t 5

x2 =5 2"7t6 7" 4t

x3 = t

#

$

% % % %

&

% % % %

'

x1 = "19t "18x2 = 22t + 23x3 = t

#

$ %

& %

, t∈Z.

b) Si abbia il sistema lineare diofanteo

!

3x1 + 4x2 + 5x3 + 7x4 = 92x1 + 5x2 " 4x3 + 3x4 = 14

# $ %

.

Qui è agevole calcolare i divisori delle due matrici A e C:

!

3 42 5

= 7,

!

3 52 "4

= "22 sono coprimi, quindi certamente d = 1 senza ulteriori calcoli sia per A

sia per C. Allora ci sono soluzioni intere. Però nessuno dei

!

42

"

# $ $ %

& ' ' = 6 minori d’ordine 2 di A ha

determinante uguale ad 1 o a -1, quindi il metodo precedente non funziona.

Proviamo ad ampliare la matrice A dei coefficienti risolvendo il sistema omogeneo

associato:

!

3x1 + 4x2 + 5x3 + 7x4 = 02x1 + 5x2 " 4x3 + 3x4 = 0

# $ %

. Per questo prendiamo

!

x4 = 0 e risolviamo

!

3x1 + 4x2 = "5x32x1 + 5x2 = 4x3

# $ %

. Si ha

subito

!

x1 =

"5x3 44x3 5

7="39x3

7,

!

x2 =

3 "5x32 4x3

7=

22x37

. Allora, posto

!

x3 = 7, si ha la soluzione

intera

!

"39 22 7 0[ ] . Un vettore

!

R1 tale che

!

"39 22 7 0[ ] #R1 = 1 è tale che:

!

"39y1 + 22y2 + 7y3 = 1. Posto

!

y1 = 0, si trova subito

!

y2 = 1 ed

!

y3 = "3. Allora, per esempio

prendiamo

!

R1t

= 0 1 "3 0[ ] e lo aggiungiamo come ultima riga ad A:

!

A1 =

3 4 5 72 5 "4 30 1 "3 0

#

$

% % %

&

'

( ( ( .

A questo punto, o calcoliamo i quattro minori d’ordine 3 cercandone uno che sia ±1,

oppure aggiungiamo la quarta riga.


27

Il primo minore fa al caso nostro:

!

3 4 52 5 "40 1 "3

= 1, allora possiamo risolvere il sistema

!

3x1 + 4x2 + 5x3 = "7x4 + 92x1 + 5x2 " 4x3 = "3x4 +14

x2 "3x3 = t1

#

$ %

& %

ottenendo:

!

x1 = "41t1 + 26t2 +139x2 = 22t1 "15t2 "72x3 = 7t1 "5t2 "24x4 = t2

#

$

% %

&

% %

,

!

t1, t2( ) " Z .

In alternativa, possiamo cercare la quarta riga di A, risolvendo dapprima il sistema

omogeneo

!

3x1 + 4x2 + 5x3 + 7x4 = 02x1 + 5x2 " 4x3 + 3x4 = 0

x2 "3x3 = 0

#

$ %

& %

. Una soluzione non nulla è

!

26 "15 "5 1[ ] ed un

vettore

!

R2 tale che

!

26 "15 "5 1[ ] #R2 = 1 è tale che:

!

26y1 "15y2 "5y3 + y4 = 1. Una

soluzione è per esempio la riga

!

1 0 5 0[ ] , e la collochiamo come quarta riga di A:

!

A2 =

3 4 5 72 5 "4 30 1 "3 01 0 5 0

#

$

% % % %

&

'

( ( ( (

. Si noti che

!

det A2( ) = 1 = divisore di A. Il sistema finale è allora:

!

3x1 + 4x2 + 5x3 + 7x4 = 92x1 + 5x2 " 4x3 + 3x4 = 14

x2 "3x3 = t1x1 + 5x4 = t2

#

$

% %

&

% %

e le soluzioni sono:

!

x1 = 115t1 + 26t2 "355x2 = "68t1 "15t2 + 213x3 = "23t1 "5t2 + 71x4 = 6t1 + t2 "19

#

$

% %

&

% %

,

!

t1, t2( ) " Z .

Come verificare che le soluzioni sono le stesse? Posto

!

t1t2

"

# $

%

& ' =

10

"

# $ %

& ' nell’ultima formula, si

ottiene la quaterna

!

"240 145 48 "13[ ] , che con la formula precedente si ottiene per

!

t1t2

"

# $

%

& ' =

1(13

"

# $

%

& ' . Analogamente, posto

!

t1t2

"

# $

%

& ' =

01

"

# $ %

& ' nell’ultima formula, si ottiene la quaterna

!

"329 198 66 "18[ ] , ottenibile con la prima formula con

!

t1t2

"

# $

%

& ' =

0(18

"

# $

%

& ' .

Allora, una trasformazione di parametri unifica le due formule: la stessa soluzione che con

la seconda formula si trova con

!

t1t2

"

# $

%

& ' =

hk

"

# $ %

& ' si trova dalla prima formula con

!

t1t2

"

# $

%

& ' =

h6h + k (19

"

# $

%

& ' .

Un caso particolare di sistemi diofantei è il seguente: n-1 equazioni in n incognite

!

ai " x + mi " ti = ci, 2 # i # n $1,

!

ai " 0 " mi


28

Affinché ogni equazione abbia soluzioni per ogni scelta dei termini noti, supponiamo

!

MCD ai,mi( ) = 1. Allora esistono

!

ui, vi tali che

!

ai "ui + mi " vi = 1. Possiamo allora ottenere

!

x = ci "ui #mi "qiti = ci " vi + ai "qi

$ % &

, dove i

!

qi sono parametri.

Poniamo

!

bi = ci "ui . Allora il sistema diventa:

!

x + mi "qi = bi, 2 # i # n $1, e risolvere questo

sistema porta a risolvere quello di partenza. Per farlo, serve un lemma.

LEMMA 1.2.5. Siano dati h numeri interi

!

mi a due a due coprimi. Allora gli h+1

numeri

!

m = mii=1

h" ,

!

mmi

, 1 " i " h , sono coprimi, ossia il loro MCD è 1.

Dimostrazione. Sia

!

d = MCD m, mm1

,K, mmh

"

# $ $

%

& ' ' .

Poiché

!

MCD m, mm1

"

# $ $

%

& ' ' =

mm1

, allora

!

d = MCD mm1

, mm2

,K, mmh

"

# $ $

%

& ' ' .

Analogamente, dato che gli

!

mi sono a due a due coprimi, segue

!

MCD mm1

, mm2

"

# $ $

%

& ' ' =

mm1 (m2

,

che implica

!

d = MCD mm1 "m2

, mm3

K, mmh

#

$ % %

&

' ( ( . Così seguitando, si trova

!

d =m

m1 "m2Lmh= 1.

Siamo in grado ora di dare una dimostrazione di un teorema antico e famoso, del

quale esistono altre numerose formulazioni, dimostrazioni e generalizzazioni:

TEOREMA 1.2.6. (Teorema cinese del resto). Sia dato il sistema lineare diofanteo

!

x + mi " yi = bi, 1 # i # n $1, con gli

!

mi positivi. Se questi sono a due a due coprimi, allora il

sistema ha soluzioni intere. Inoltre, c’è un’unica soluzione intera in cui

!

0 " x < m = mii=1

n#1$ .

Dimostrazione. Consideriamo la matrice incompleta A del sistema: è di tipo (n-1)xn

!

A =

1 m1 0 K 01 0 m2 K 0K K K K K

1 0 0 K mn"1

#

$

% % % %

&

'

( ( ( (

. I minori

!

A j di ordine massimo si ottengono sopprimendo a

turno una delle colonne. Si ha

!

A1 = m ,

!

A j = "1( ) j mm j"1

per j > 1, e questi numeri sono

coprimi, per il lemma. Allora possiamo procedere come al solito, ossia cercare un vettore


29

primitivo X tale che

!

A " X = 0. Una soluzione è

!

X =

"mm m1m m2

K

m mn"1

#

$

% % % % % %

&

'

( ( ( ( ( (

. Poi cerchiamo un vettore R

tale che

!

Xt "R = 1. Posta = 0 la prima coordinata di R, resta l’equazione

!

mm jj=1

n"1# xj = 1, che ha

soluzione perché i coefficienti sono coprimi. Aggiungiamo allora la riga trovata ed abbiamo

la matrice A’ il cui determinante è = 1. Completata anche la colonna B dei termini noti con

l’aggiunta del termine t, si ricava con la formula di Cramer:

!

x =

b1 m1 0 K 0b2 0 m2 K 0K K K K K

bn"1 0 0 K mn"1t u1 u2 K un"1

= "1( ) j+1#bj #u j #

mmj

j=1

n"1$ + "1( )n+1

#m # t.

Posto

!

k = "1( )i+1#bi #ci #

mmii=1

n"1$ , ed inglobato il segno di m in t, si ha quindi

!

x = k + m " t.

Se

!

0 " k < m , allora la soluzione

!

x tale che

!

0 " x < m si ottiene per t = 0. Se no, dividiamo k

per m,

!

k = m "q + r , con 0 ≤ r < m. Basta porre allora t = -q e si ottiene

!

0 " x = r < m . Gli altri

valori di t danno soluzioni negative o maggiori di m, quindi c’è una sola soluzione

!

x tale

che

!

0 " x < m .

ESEMPIO 1.2.7. Risolviamo

!

x + 3y1 = "8x + 4y2 = 11x + 5y3 = "6

#

$ %

& %

. I coefficienti 3, 4, 5 sono a due a due coprimi. A

differenza di come fatto nel teorema, seguiamo un altro procedimento: aggiungiamo una

riga incognita ad A e imponiamo che il determinante della matrice ottenuta sia 1.

L’equazione

!

1 3 0 01 0 4 01 0 0 5

u0 u1 u2 u3

= 1, ossia

!

60u0 "20u1 "15u2 "12u3 = "1 ha per esempio la

soluzione

!

0 "1 "1 3[ ] .


30

Allora consideriamo il sistema

!

x + 3y1 = "8x + 4y2 = 11x + 5y3 = "6

"y1 " y2 + 3y3 = t

#

$

% %

&

% %

. Si ricava

!

x =

"8 3 0 011 0 4 0"6 0 0 5t "1 "1 3

= "60t "221,

da cui segue x =

!

x = "60t " 60 #4 +19 = "60 # t + 4( ) +19 = 19 " 60$ , dove

!

t = " # 4

Allora, la soluzione principale, minore di

!

60 = 3 "4 "5, è 19, ottenuta per t = -4.

A questo punto, volendo, si ricavano direttamente le altre tre incognite:

!

"60t "221+ 3y1 = "8"60t "221+ 4y2 = 11"60t "221+ 5y3 = "6

#

$ %

& %

'

y1 = 20t + 71y2 = 15t + 58y3 = 12t + 43

#

$ %

& %

, o anche

!

y1 = 20" # 9y2 = 15" #2y3 = 12" #5

$

% &

' &

.

NOTA. Questo teorema ha formulazioni assai diverse, una delle quali in termini di ideali. In un

dominio D ad ideali principali (PID) come Z, dati gli ideali

!

I = a( ) ,

!

J = b( ) , si ha, come noto:

!

I + J = a, b{ }( ) = MCD a, b( )( ),

!

I " J = mcm a, b( )( ) . Se a e b sono coprimi, allora

!

I + J = 1D( ) = D ,

!

I " J = a #b( ) = I # J .

Inoltre, è noto che se A e B sono anelli, ogni ideale del prodotto diretto A×B è prodotto diretto I×J,

con I ideale di A e J ideale di B, e inoltre

!

A " BI " J

#AI"

BJ

.

Pertanto, in un PID D, dati gli ideali

!

I = a( ) ,

!

J = b( ) , se a e b sono coprimi si ha:

!

DI " J

#DI$

DJ

, dove

l’isomorfismo è,

!

"x # D, x + I $ J a x + I, x + J( ) .

Se si esplicita questo risultato, segue l’esistenza della soluzione x del sistema:

!

x + a "q1 = c1x + b "q2 = c2

# $ %

,

perché alla coppia

!

c1 + a( ), c2 + b( )( ) = x + a( ), x + b( )( ) " DI#

DJ

corrisponde biunivocamente

l’elemento

!

c = x + a "b( ) # DI $ J

.


31

§ 1.3. Equazioni diofantee lineari in N.

In vari problemi interessano le soluzioni in N, ossia le soluzioni non negative

dell’equazione

!

a " x + b " y = c , con a e b positivi e c multiplo di MCD(a,b). Per trovarle,

usando i simboli della sezione precedente, basta porre

!

x0 " k # $ b % 0y0 + k # $ a % 0

& ' (

e trovare le soluzioni

intere, se ce ne sono. Vediamo alcuni esempi

ESEMPIO 1.2.1. L’equazione 120x + 85y = n.

a) 120x + 85y = 50 non ha soluzioni in N, in quanto 50 è minore dei due coefficienti.

b) 120x + 85y = 85 ha la soluzione (0,1)

c) 120x + 85y = 120 ha la soluzione (1,0)

Basta tentativi, ora procediamo come nel quesito della Susy.

Sappiamo che

!

120 " 5n( ) + 85 " #7n( ) = 5n per ogni n. Sappiamo anche che

!

120 " #17k( ) + 85 " 24k( ) = 0 per ogni k, quindi

!

120 " 5n #17k( ) + 85 " #7n + 24k( ) = 5n per ogni k.

Poniamo allora

!

5n "17k # 0"7n + 24k # 0

$ % &

, da cui segue

!

7n24

" k "5n17

o anche, riducendo allo stesso

denominatore,

!

119n408

" k "120n408

. Certamente ci sono soluzioni intere non negative se

!

n " 408, perché la differenza delle frazioni è ≥ 1, quindi ce ne sono se il termine noto è

!

" 408 #5 = 2040 . Tuttavia, ci sono soluzioni anche per numeri minori di questo: i multipli di

uno dei due coefficienti e le loro combinazioni lineari minori di 2040.

Quante sono? Sono tante quante le coppie (h, k) tali che 17x+24y ≤ 408, ossia 225, come

mostra la tabella seguente, calcolata con Excel, ed in cui sono rese illeggibili le

combinazioni lineari maggiori di 408.

In questa tabella, trasformata in una riga e riordinata, si osserva che solo il 408 è ripetuto

due volte. Dal 368 in poi, sono presenti tutti i numeri fino al 408, senza lacune. Quindi

l’ultimo numero senza soluzioni è n = 367, ossia, nel problema iniziale, il massimo termine

noto non ammesso è 367⋅5 = 1835.

Si noti che

!

367 = 17 "24 # 17+ 24( ) . Sarà un caso?

Inoltre, i termini noti c’ senza soluzioni nel problema ausiliario 17x+24y = c’, ossia quelli

che mancano nella tabella sono 184. Si può determinare questo numero con qualche

formula?


32

x\y 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 0 24 48 72 96 120 144 168 192 216 240 264 288 312 336 360 384 408 1 17 41 65 89 113 137 161 185 209 233 257 281 305 329 353 377 401 425 2 34 58 82 106 130 154 178 202 226 250 274 298 322 346 370 394 418 442 3 51 75 99 123 147 171 195 219 243 267 291 315 339 363 387 411 435 459 4 68 92 116 140 164 188 212 236 260 284 308 332 356 380 404 428 452 476 5 85 109 133 157 181 205 229 253 277 301 325 349 373 397 421 445 469 493 6 102 126 150 174 198 222 246 270 294 318 342 366 390 414 438 462 486 510 7 119 143 167 191 215 239 263 287 311 335 359 383 407 431 455 479 503 527 8 136 160 184 208 232 256 280 304 328 352 376 400 424 448 472 496 520 544 9 153 177 201 225 249 273 297 321 345 369 393 417 441 465 489 513 537 561

10 170 194 218 242 266 290 314 338 362 386 410 434 458 482 506 530 554 578 11 187 211 235 259 283 307 331 355 379 403 427 451 475 499 523 547 571 595 12 204 228 252 276 300 324 348 372 396 420 444 468 492 516 540 564 588 612 13 221 245 269 293 317 341 365 389 413 437 461 485 509 533 557 581 605 629 14 238 262 286 310 334 358 382 406 430 454 478 502 526 550 574 598 622 646 15 255 279 303 327 351 375 399 423 447 471 495 519 543 567 591 615 639 663 16 272 296 320 344 368 392 416 440 464 488 512 536 560 584 608 632 656 680 17 289 313 337 361 385 409 433 457 481 505 529 553 577 601 625 649 673 697 18 306 330 354 378 402 426 450 474 498 522 546 570 594 618 642 666 690 714 19 323 347 371 395 419 443 467 491 515 539 563 587 611 635 659 683 707 731 20 340 364 388 412 436 460 484 508 532 556 580 604 628 652 676 700 724 748 21 357 381 405 429 453 477 501 525 549 573 597 621 645 669 693 717 741 765 22 374 398 422 446 470 494 518 542 566 590 614 638 662 686 710 734 758 782 23 391 415 439 463 487 511 535 559 583 607 631 655 679 703 727 751 775 799 24 408 432 456 480 504 528 552 576 600 624 648 672 696 720 744 768 792 816

Occupiamoci del problema, limitandoci al caso di due incognite, anche se pure il

caso di tre incognite è stato risolto.

Nel seguito supporremo a,b > 0, c ≥ 0, MCD(a,b) = 1. Per l’equazione

!

a " x + b " y = c si

presentano tre problemi:

a) Trovare la configurazione dei valori di c per i quali non ci sono soluzioni in N o in

!

N+ = N \ 0{ } .

b) (Problema lineare di Frobenius) Trovare il massimo c per il quali non ci sono

soluzioni in N o in

!

N+.

c) Trovare il numero di soluzioni dell’equazione

!

a " x + b " y = c in in N o in

!

N+.

Siano F il massimo valore di c per il quale non ci sono soluzioni positive e

!

F0 il massimo

valore di c per il quale non ci sono soluzioni in N.


33

TEOREMA 1.3.2. Sia data l’equazione

!

a " x + b " y = c , a,b > 0, c ≥ 0, MCD(a,b)=1.

Allora F = a⋅b ed

!

F0 = F " (a + b) = a #b " (a + b)

Dimostrazione. Consideriamo l’equazione

!

a " x + b " y = a "b. Poiché a e b sono coprimi, allora

a deve dividere y e b deve dividere x. Ossia

!

x = b " # x y = a " # y

$ % &

, con x’ ed y’ positivi. Si ottiene

!

a "b = a "b " # x + # y ( ) $ 2a "b , assurdo. Ora proviamo che per ogni c > a⋅b le soluzioni positive ci

sono. Poniamo c = a⋅b+q, q > 0.

Troviamo dapprima le soluzioni in Z, poi le trattiamo col procedimento visto:

!

x = x0 " kby = y0 + ka

# $ %

. Imposto che x ed y siano entrambi positivi, si ottiene:

!

"y0a

< k <x0b

#"b $ y0a $b

< k <a $ x0a $b

Ora,

!

a " x0a "b

##b " y0a "b

=a " x0 + b " y0

a "b=

ca "b

= 1+q

a "b> 1, perciò almeno un valore intero di k

nell’intervallo

!

"y0a

, x0b

#

$ %

&

' ( esiste. Allora effettivamente F = a⋅b.

Verifichiamo ora che

!

F0 = F " (a + b) = a #b " (a + b).

L’equazione

!

a " x + b " y = a "b # a # b si riconduce a

!

a " x +1( ) + b " y +1( ) = a "b, che non ha

soluzioni positive, quindi i numeri positivi x+1 ed y+1 non esistono. D’altra parte, posto

c = a⋅b+q-a-b, si ha l’equazione

!

a " x +1( ) + b " y +1( ) = a "b+q, che le soluzioni positive le ha.

Dette x’, y’ tali soluzioni, si ha ovviamente

!

x = " x #1 $ 0y = " y #1 $ 0

% & '

, e si ha una soluzione non

negativa. Il problema lineare di Frobenius in due incognite è così risolto.

Completiamo le informazioni su queste equazioni. Una soluzione

!

x , y ( ) si dice

minimale se si ha

!

x " b #1,

!

y " a #1. Negli esempi precedenti ne abbiamo trovate con due

approcci diversi. Tuttavia non sempre esistono.

ESEMPIO 1.3.3. Risolviamo l’equazione 3x+5y = 26. Una soluzione particolare è

!

2,4( ) , che

non è minimale, perché 4 non è ≤ 2 = 3-1. La soluzione generale è

!

x = 2"5ky = 4 + 3k

# $ %

, con k∈Z.

k -5 -4 -3 -2 -1 0 1 2 3 4 5 x 27 22 17 12 7 2 -3 -8 -13 -18 -23 y -11 -8 -5 -2 1 4 7 10 13 16 19


34

Come si vede dalla tabella, niente da fare. Però, se come termine noto prendiamo 22,

otteniamo la soluzione particolare

!

4,2( ) , che è minimale. Se prendiamo c = 7, troviamo

!

"1,2( ) e

!

4,"1( ) . Qual è la soglia?

PROPOSIZIONE 1.3.4. Siano dati a,b > 0, c ≥ 0, MCD(a,b)=1.

a) Se l’equazione ha soluzioni minimali, allora

!

c " 2a #b $ a $ b

b) Se

!

c < a "b allora ci sono due soluzioni minimali, che coincidono se e solo se sono

non negative.

c) Se

!

a "b # c # 2a "b allora esiste al massimo una soluzione minimale, ed è positiva.

Dimostrazione. a) I valori massimi di

!

x , y ( ) sono

!

b "1,a "1( ) : sostituendoli nell’equazione

si ottiene

!

a " b #1( ) + b " a #1( ) = 2a "b # a # b .

b) Abbiamo già visto nell’esempio 1.1.5 che una soluzione particolare

!

x1, y1( ) con

!

0 " x1 " b #1 si trova sempre con una semplice divisione, ed è anche unica : trovata una

soluzione particolare

!

x0, y0( ) si divide infatti

!

x0 per b e si prende il resto positivo. Le altre

soluzioni hanno valori di x negativi o maggiori di b.

Allora la soluzione generale è

!

x = x1 + k "by = y1 # k "a

$ % &

, k∈Z.

Ora, se

!

y1 = a + h, h " 0 , allora

!

a "b > c = a " x1 + b " a + h( ) = a "b + a " x1 + h( ) # a "b, assurdo.

Pertanto, se

!

y1 " 0,

!

x1, y1( ) è minimale ed è l’unica, come si vede dando a k valori negativi

o positivi. Potrebbe essere però

!

y1 < 0. In tal caso, deve risultare

!

y1 " a #1. In caso

contrario, se cioè fosse

!

y1 = "a "h, h # 0 , allora

!

0 " c = a # x1 + b # $a $h( ) " a # b $1( ) + b # $a $h( ) = $a $ b #h < 0 ,

assurdo. Dunque,

!

x1, y1( ) è minimale. Naturalmente è possibile scambiare i ruoli delle due

incognite, scegliendo una soluzione particolare

!

x2, y2( ) con

!

0 " y2 " a #1. In tal caso, se

anche

!

x2 " 0 si ritrova la stessa soluzione di prima,

!

x1, y1( ) . Altrimenti, la soluzione è

minimale, ma diversa da

!

x1, y1( ) . c) Se una soluzione minimale

!

x1, y1( ) esiste, e se una delle due componenti della coppia è

negativa o nulla, il termine noto c non può essere maggiore di ab-1. Allora sono entrambe

positive, ed in tal caso ce n’è solo una.


35

PROPOSIZIONE 1.3.5 Siano dati a,b > 0, c ≥ 0, MCD(a,b)=1. Se c < a⋅b e non è

multiplo né di a né di b, allora una ed una sola delle due equazioni

!

a " x + b " y = c oppure

!

a " x + b " y = ab # c ha una soluzione non negativa. Inoltre, tale soluzione è positiva.

Dimostrazione. Ovviamente, se

!

c = a "h , con necessariamente

!

h " b #1 allora una

soluzione di

!

a " x + b " y = c è

!

h,0( ) . L’altra equazione

!

a " x + b " y = ab # c ha soluzione

!

b "h,0( ) . Stesso discorso se c è multiplo di b.

Vediamo ora il caso di c < a⋅b, non multiplo né di a né di b. Allora tale è anche

!

a "b # c .

Perciò le due equazioni non hanno soluzioni con un’incognita nulla. Ciò posto:

Esistenza. Supponiamo che

!

a " x + b " y = c non abbia soluzioni positive. Ha comunque una

soluzione minimale

!

x1, y1( ) con

!

0 < x1 " b #1 e

!

"a +1 # y < 0. Allora,

!

b " x1,"y1( ) è una

soluzione positiva di

!

a " x + b " y = ab # c .

Unicità. Sia

!

x1, y1( ) una soluzione positiva di

!

a " x + b " y = c , che se esiste è unica per 1.3.4.

Se anche

!

a " x + b " y = ab # c avesse una soluzione positiva

!

x2, y2( ) , allora

!

x1 + x2, y1 + y2( )

sarebbe una soluzione positiva di

!

a " x + b " y = ab, contro il teorema 1.3.2. Dunque, una sola

delle due ha soluzioni positive.

NOTA. Il caso delle tre incognite è stato studiato e risolto in varie epoche con approcci a

volte diversi, ma tutti riconducibili alle soluzioni minimali di tre casi in due incognite

ricavati dall’equazione data. Ricordo solo il contributo del mio collega e predecessore in

questo insegnamento di Teoria dei Numeri, Calogero Tinaglia, il quale ha tra l’altro

perfezionato e spiegato numeri ausiliari proposti da altri autori, Johnson in particolare. Chi

è interessato al problema può consultare i suoi lavori e la bibliografia che essi riportano.

I casi di n ≥ 4 incognite sono tuttora aperti. Ossia, non si conosce un modo generale per

determinare il massimo numero naturale m per il quale l’equazione

!

ak " xk = mk=1

n# a

coefficienti interi positivi coprimi non ha soluzioni naturali o soluzioni intere positive.

Ora cambiamo il punto di vista: per cominciare, dato che i coefficienti dell’equazione

!

ak " xk = mk=1

n# sono positivi, si possono interpretare come le frequenze delle rispettive

incognite, quindi, posto

!

r = akk=1

n" , l’equazione data si può interpretare come un caso


36

particolare dell’equazione

!

xj = mj=1

r" , della quale si cercano le soluzioni con

!

ak coordinate

consecutive uguali ad

!

xk. Per esempio,

!

2x + 3y = 8 si può riscrivere

!

x + x + y + y + y = 8.

Allora si pone un altro problema: quante equazioni della forma

!

xk = mk=1

n" hanno

soluzioni positive e quante ne hanno? Ossia, in quanti modi si può scrivere m come somma

di numeri interi positivi? Ovviamente, deve essere

!

1 " n " m , perché ci siano soluzioni.

Se imponiamo

!

x1 " x2 " K " xn , le soluzioni sono dette partizioni di m in n addendi. Per

avere poi le soluzioni senza questa restrizione, basta contare per ogni partizione il numero

di suoi “anagrammi” e sommare.

ESEMPIO 1.3.6. Vediamo il caso di m = 8.

n° incognite equazione partizioni: n° soluzioni parz. 1

!

x1 = 8 8 1 1 2

!

x1 + x2 = 8 7+1 2 6+2 2 5+3 2 4+4 1 7 3

!

x1 + x2 + x3 = 8 6+1+1 3 5+2+1 6 4+3+1 6 4+2+2 3 3+3+2 3 21 4

!

x1 + x2 + x3 + x4 = 8 5+1+1+1 4 4+2+1+1 12 3+3+1+1 6 3+2+2+1 12 2+2+2+2 1 35 5

!

x1 + x2 + x3 + x4 + x5 = 8 4+1+1+1+1 5 3+2+1+1+1 20 2+2+2+1+1 10 35 6

!

x1 + x2 + x3 + x4 + x5 + x6 = 8 3+1+1+1+1+1 6 2+2+1+1+1+1 15 21 7

!

x1 + x2 + x3 + x4 + x5 + x6 + x7 = 8 2+1+1+1+1+1+1 7 7 8

!

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 8 1+1+1+1+1+1+1+1 1 1 totale 22 128 128

Esistono algoritmi, ma anche formule complicatissime per trovare il numero p(m) delle

partizioni di m, mentre il numero complessivo delle soluzioni, per

!

1 " n " m , è

!

2m"1.

Cap. 1. – EQUAZIONI E SISTEMI DIOFANTEI - …verardi/T d N Verardi cap I.pdfPiù in dettaglio,...

Documents

Transcript of Cap. 1. – EQUAZIONI E SISTEMI DIOFANTEI - …verardi/T d N Verardi cap I.pdfPiù in dettaglio,...