Le Equazioni Diofantee

Se non ci sono limitazioni sui valori delle incognite, possiamo dare a x e ad y valori arbitrari, per esempio x = 1/2, per cui si ottiene y = 77/5. In questo senso l'equazione (1) è una equazione indeterminata, vale a dire che per ogni x possiamo trovare un valore di y corrispondente.
Se invece ci limitiamo a valori interi per le incognite x e y, come in effetti è naturale nel problema proposto (è improbabile che un fattore voglia acquistare mezza mucca), il problema cambia radicalmente.
Le equazioni indeterminate di cui si cercano le soluzioni intere si dicono Equazioni Diofantee (dal nome del matematico greco Diofanto che scrisse un trattato su questo tipo di equazioni).
Il nostro problema ha poi un' ulteriore restrizione per le incognite, dato che queste devono essere anche positive. L'equazione (1) ha 2 soluzioni:

Questa soluzione può essere trovata anche per semplici tentativi dando alla x valori interi successivi e accettando quelli per cui 81 - 8x è multiplo di 5.
Ci sono ovviamente altri modi di risolvere questo tipo di equazioni. Il primo di questi fu usato spesso da Eulero nel suo libro "Algebra", pubblicato nel 1770. Il secondo invece è un esempio di una applicazione delle frazioni continue.

2. Il metodo di Eulero

Consideriamo l'equazione

Poiché il coefficiente della y è il piu piccolo, risolviamo l'equazione rispetto a y ottenendo

y = (81 - 8x)/5. (2)

Sia 81 che 8 contengono dei multipli di 5, nel senso che 81 = 16*5 + 1 e 8 = 1 · 5 + 3. Quindi, sostituendo nella (2) si ottiene:

y = ((5 · 16 + 1) - (5 · 1 + 3)x)/5 = (16 - x) + (1 - 3x)/5 = (16 - x) + t(3)

dove

La (3) si può anche scrivere come

3x + 5t = 1. (4)

Poiché x ed y devono essere interi, dalla (3) segue che anche t deve esserlo. Quindi il nostro obiettivo è diventato ora cercare soluzioni intere della (4). L'idea essenziale del metodo di Eulero è di ricondurre la risoluzione di una certa equazione diofantea a quella di un'altra equazione con coefficienti più piccoli.
Il procedimento usato per passare dalla (2) alla (4) può essere ripetuto: risolvendo la (4) rispetto a x si ottiene:

Poiché x e t devono essere interi, anche u deve esserlo. Ci siamo ricondotti a cercare le soluzioni intere dell'equazione

t = 3u - 1. (5)

Queste però si ricavano banalmente: poiché il coefficiente di t è 1, basta dare ad u un valore intero qualsiasi per ottenere in corrispondenza un valore intero per la t, cioè per ottenere una soluzione intera della (5). A questo punto basta sostituire all'indietro i valori trovati, fino ad arrivare alle soluzioni della (1):

Quindi la soluzione generale della (1) è data da

(6) y = 13 + 8u

dove u è un qualunque intero, positivo, negativo o zero.
Nel problema del fattore era necessario inoltre che x ed y fossero positivi. Tenendo conto di questo, dalla (6) si ottiene:

-13/8 < u < 2/5

ovvero, dato che u deve essere intera, gli unici valori accettabili sono u = -1 e u = 0, da cui si ottengono le due soluzioni trovate in precedenza per via empirica: (2,13) e (7,5).

---

3. L'equazione indeterminata ax - by = ± 1.

Mostreremo come possono essere usate le frazioni continue per risolvere le equazioni indeterminate del tipo ax + by = c dove a, b, c sono interi assegnati e x, y sono delle incoglite intere.

Comincieremo col risolvere

ax - by = ± 1(7)

con a,b interi positivi primi fra loro.
In queste ipotesi l'equazione (1) ha infinite soluzioni intere, cosa che non è piu vera se rinunciamo all'ipotesi che a,b siano primi tra loro.
L'equazione 2x - 4y = 1 ad esempio, non può avere soluzioni intere dato che il primo membro è necessariamente pari mentre il secondo è dispari.
Il teorema che ora proponiamo, oltre a dimostrare l'esistenza di soluzioni intere per l'equazione ax - by = ±1, suggerisce anche un metodo per determinare la soluzione generale di tale equazione.

Teorema: L'equazione ax - by = ± 1, dove a e b sono interi positivi primi tra loro, ha infinite soluzioni intere.

Dimostrazione: per prima cosa sviluppiamo a/b in frazione continua. Sia

a/b=[a₁, a₂, ..., a_n-1, a_n].

Siano poi c₁, c₂, ..., c_n i convergenti della frazione continua. Gli ultimi due convergenti, c_n-1=p_n-1/q_n-1 e c_n=p_n/q_n=a/b, saranno la chiave della dimostrazione. Infatti, dal teorema dei convergenti si ha che

p_nq_n-1-q_np_n-1=(-1)ⁿ

Poiché a=p_n e b=q_n, segue

aq_n-1-bp_n-1=(-1)ⁿ.
Confrontando con l'equazione ax - by = (-1)ⁿ si vede che

x₀ = q_n-1, y₀ = p_n-1
è una soluzione. Se ora ci ricordiamo che ogni frazione può essere sviluppata in frazione continua sia con un numero dispari che con un numero pari di quozienti, calcolando i convergenti siamo in grado di trovare una soluzione particolare di ax - by = ± 1.

Con questo abbiamo dimostrato il teorema. Cerchiamo ora di scrivere la soluzione generale dell'equazione. Se (x, y) è una qualunque soluzione di ax - by = 1 e (x₀, y₀) è una soluzione particolare, cioè ax₀ - by₀ = 1, sottraendo membro a membro si ha che

a(x - x₀) - b(y - y₀)=0.

Dato che le quantità che compaiono nell'uguaglianza sono intere, e b divide il secondo membro, allora deve dividere anche il primo. Inoltre MCD(a,b) = 1, quindi b deve dividere x - x₀, ovvero x - x₀ = tb, con t intero.
Sostituendo nell'uguaglianza precedente si ricava a(tb) = b(y - y₀). Quindi le soluzioni dell'equazione sono tutte della forma:

x = x₀ + tb (8) y = y₀ + ta

con t intero qualsiasi. D'altra parte, se x ed y sono di questa forma, sostituendo nell'equazione si vede subito che la soddisfano, quindi le soluzioni di ax₀ - by₀ = 1 sono tutte e sole quelle della forma (8).

A prima vista può sembrare che sia stato fatto lavoro doppio, cioè che dopo aver ricavato le soluzioni si sia verificato che lo sono per davvero. In realtà non è così: prima abbiamo stabilito che affinché una coppia di numeri (x, y) sia soluzione è necessario che verifichi le condizioni (8). Dopo abbiamo dimostrato che tutte le coppie (x, y) di quella forma sono effettivamente soluzioni, cioè che è sufficiente soddisfare la (8) per essere soluzione. Questo modo di procedere si incontra frequentemente nelle dimostrazioni matematiche.

In maniera analoga (sviluppando a/b in frazione continua con un numero dispari di divisori) si ottiene la soluzione generale di ax - by = -1.

Esempio: Trovare la soluzione generale di 205x - 93y = 1.

Sviluppiamo 205/93 in frazione continua: 205/93 = [2, 4, 1, 8, 2]. Poiché il numero di divisiori ottenuti è dispari, sostituiamo lo sviluppo con

205/93 = [2, 4, 1, 8, 1, 1].

I convergenti della frazione sono:

c₁=2/1, c₂=9/4, c₃=11/5, c₄=97/44, c₅=108/49, c₆=205/93.

Quindi una soluzione particolare è

x₀=49 y₀=108

La soluzione generale invece è:

x = x₀ + tb = 49 + 93t y = y₀ + ta = 108 + 205t

---

4. Alcune generalizzazioni

ax - by = c, MCD(a,b) = 1.
Basta osservare che se (x₀, y₀) è soluzione di ax - by = 1 allora, moltiplicando membro a membro per c segue:

a(cx₀) - b(cy₀) = c

e quindi (cx₀, cy₀) è una soluzione particolare di ax - by = c. Per trovare la soluzione generale si procede esattamente come nel caso precedente ricavando:

x = cx₀ + tb y = cy₀ + ta.

ax + by = c, MCD(a,b) = 1.
Si determina prima la soluzione generale di ax + by = 1: ci si può ricondurre ai casi precedenti scrivendo l'equazione come ax - b(-y) = 1 e risolvendola rispetto alle incognite x e -y). Poi, moltiplicando l'equazione membro a membro per c, si trova la soluzione:

x = cq_n-1 - tb y = -cp_n-1 + ta

dove (q_n-1, p_n-1) è, come abbiamo visto nel paragrafo 2, la soluzione di ax - b = 1.

---

Bibliografia

• C. D. Olds, Frazioni Continue, Zanichelli, 1972

---