Equazioni Diofantee
Un’equazione Diofantea è un’equazione numerica qualunque della quale si richiedono le soluzioni intere, affiancata eventualmente da condizioni aggiuntive sulle variabili: per esempio, che una certa variabile p sia un numero primo. Di solito un’equazione Diofantea ha un certo numero di soluzioni semplici che possono essere trovate per tentativi; una volta trovate
queste normalmente occorre dimostrare che non ce ne sono altre. Altre volte può capitare che un’equazione Diofantea abbia come soluzioni un’intera classe di numeri.
Equazioni diofantee di primo grado in due variabili
Un’equazione Diofantea di primo grado in due variabili è un’espressione di questo tipo:
a x +by = c
dove a,b, c sono dati e x,y sono le incognite. Se MCD(a,b) non è divisore di c , l’equazione non ha soluzioni. In caso contrario, ne ha infinite. Per ottenerle, è possibile utilizzare il metodo delle divisioni iterate di Euclide, basato sull’algoritmo di Euclide per l’MCD.
ESEMPIO:
Trovare le soluzioni intere per l’equazione:
86x + 25y = 1
Siccome a = 86 = 2* 43; b = 25 = 5*2 si ha che MCD(86, 25) = 1, che è un divisore di c = 1. Quindi ci sono infinite soluzioni. Si usano le divisioni con resto iterate:
Nel primo passaggio, il dividendo è a e il divisore è b.
In ciascuno dei passaggi successivi, come nuovo dividendo si prende il divisore della riga precedente, e come nuovo divisore si prende il resto della riga precedente. Ci si ferma quando l’ultimo resto ottenuto è MCD(a,b). Si possono ora trovare x e y , riscrivendo l’ultima divisione e compiendo i seguenti passaggi, in cui si sostituiscono i resti ottenuti sopra, in ordine inverso:
I resti ottenuti sopra in ordine inverso sono 1, 2, 3, 11. In ogni nuova riga, il passaggio consiste nel sostituire il resto, indicato in neretto, con l’espressione in parentesi, che si ricava dalle quattro divisioni di prima.
Ad esempio, nella terza riga, 3 viene sostituito con (25 − 2 · 11), ottenuto dalla seconda divisione: 25 = 2 · 11 + 3. Poi la parentesi viene sciolta e si continua con la riga seguente, sostituendo il prossimo resto. Alla fine, si ottiene
1 = −9 · 86 + 31 · 25, e quindi x = −9 e y = 31. Da questa soluzione, si trovano facilmente tutte le altre, che sono
x = −9 + 25k e y = 31 − 86k, dove k è un qualsiasi intero.
Il metodo usato è applicabile in tutti i casi in cui esistono soluzioni. Se a,b, c all’inizio non sono coprimi, naturalmente si riduce l’equazione: ad esempio 258x + 75y = 3 si trasforma in 86x + 25y = 1 dividendo ogni termine per 3; se c ≠ 1, come nel caso 86x + 25y = 7, si adatta la soluzione di 86x + 25y = 1 moltiplicandola per 7: x = −63 e y = 217. Invece, nel caso di
42x + 30y = 16, dopo averla ridotta in 21x + 15y = 8 dividendo ogni termine per 2, si nota che MCD(21, 15) = 3 non divide 8 e quindi l’equazione non ha nessuna soluzione.
ESERCIZIO
Cinque uomini fanno naufragio su un’isola; non c’è nulla da mangiare tranne noci di cocco. Essi vanno a dormire ripromettendosi di dividersele la mattina seguente. Nel mezzo della notte, uno dei naufraghi sente improvvisamente fame e decide di prendersi subito la sua parte di noci di cocco. Nel farlo, scopre che se ne toglie una sono esattamente divisibili per cinque. Decide pertanto di dare una noce di cocco ad una scimmia che si trova nei paraggi e di prendersi la sua parte. Durante la notte, ognuno degli altri marinai fa la stessa cosa all’ insaputa dell’altro, e ognuno trova un numero di noci di cocco che diventa divisibile per cinque una volta donata una noce di cocco alla scimmia. Al mattino, decidono come d’accordo di dividere il mucchio delle noci in parti uguali, e ne trovano ancora una di resto da lasciare alla scimmia. Quante erano all’ inizio, come minimo, le noci di cocco?
SOLUZIONE
Il problema si può formulare in termini di equazioni diofantee: infatti, sia x il numero iniziale di noci di cocco. Dopo che il primo marinaio si appropria (indebitamente) di alcune di esse, in totale ne rimangono
{4/5*(x −1)}
Si noti che per i dati che abbiamo, tale quantità è un numero intero.
Dopo le attività notturne del secondo marinaio le noci di cocco si riducono a
{4/5 (4/5 *(x − 1) − 1) − 1}
Ripetendo questo ragionamento, si ha che al mattino restano
noci di cocco. Togliendone una per la scimmia abbiamo che
è un numero intero divisibile per 5: se lo chiamiamo 5y trovato che il minimo x intero che soddisfa l’equazione diofantea:
è la soluzione al problema. Facendo i calcoli mediante l’algoritmo di Euclide troviamo che è 15621.
(301)