Come Risolvere un’Equazione Diofantea Lineare

Info sull'Autore

Un’equazione diofantea (o diofantina) è un’equazione algebrica di cui si ricercano le soluzioni per le quali le variabili assumono valori interi. In generale, le equazioni diofantee sono piuttosto difficili da risolvere e ci sono diversi approcci (l’ultimo teorema di Fermat è una famosa equazione diofantea che resta irrisolta da oltre 350 anni).

Tuttavia, le equazioni diofantee lineari del tipo ax + by = c possono essere risolte facilmente utilizzando l’algoritmo descritto qui sotto. Usando questo metodo, troviamo (4,7) come uniche soluzioni intere positive dell’equazione 31x + 8y = 180. Le divisioni in aritmetica modulare possono anche essere espresse come equazioni diofantee lineari. Per esempio, 12/7 (mod 18) richiede la soluzione 7x = 12 (mod 18) e può essere riscritta come 7x = 12 + 18y o 7x - 18y = 12. Anche se molte equazioni diofantee sono difficili da risolvere, puoi comunque fare un tentativo.

Passaggi

1
Se già non lo è, scrivi l’equazione nella forma ax + by = c.
2
Applica l’algoritmo di Euclide ai coefficienti a e b. Questo serve per due motivi. Primo, vogliamo scoprire se a e b hanno un divisore comune. Se stiamo cercando di risolvere 4x + 10y = 3, possiamo subito affermare che, poiché la parte sinistra è sempre pari e la parte destra sempre dispari, non esistono soluzioni intere per l’equazione. Allo stesso modo, se abbiamo 4x + 10y = 2, possiamo semplificare a 2x + 5y = 1. La seconda ragione sta nel fatto che, dimostrato che esiste una soluzione, possiamo costruirne una dalla sequenza di quozienti ottenuti tramite l’algoritmo di Euclide.
3
Se a, b e c hanno un divisore comune, semplifica l’equazione dividendo la parte destra e la parte sinistra per il divisore. Se a e b hanno tra loro un divisore comune ma questo non è divisore anche di c, allora fermati. Non ci sono soluzioni intere.
4
Costruisci una tabella a tre righe come vedi nella foto qui sopra.
5
Scrivi nella prima riga della tabella i quozienti ottenuti con l’algoritmo di Euclide. L’immagine qui sopra mostra quello che otterresti risolvendo l’equazione 87x - 64y = 3.
6
Riempi le ultime due righe da sinistra a destra seguendo questa procedura: per ogni cella, calcola il prodotto tra la prima cella in alto di quella colonna e la cella immediatamente alla sinistra della cella vuota. Scrivi nella cella vuota questo prodotto più il valore di due celle a sinistra.
7
Guarda le ultime due colonne della tabella completata. L’ultima colonna dovrebbe contenere a e b, i coefficienti dell’equazione del passaggio 3 (se non è così, ricontrolla i tuoi calcoli). La penultima colonna conterrà altri due numeri. Nell’esempio con a = 87 e b = 64, la penultima colonna contiene 34 e 25.
8
Nota che (87*25) - (64*34) = -1. Il determinante della matrice 2x2 in basso a destra sarà sempre o +1 o -1. Se è negativo, moltiplica entrambi i lati dell’uguaglianza per -1 per ottenere -(87*25) + (64*34) = 1. Questa osservazione è il punto di partenza da cui costruire una soluzione.
9
Ritorna all’equazione originale. Riscrivi l’uguaglianza del passaggio precedente o nella forma 87*(-25) + 64*(34) = 1 o come 87*(-25) - 64*(-34) = 1, a seconda di quale somiglia di più all’equazione originale. Nell’esempio, la seconda scelta è preferibile perché soddisfa il termine -64y dell’equazione originale quando y = -34.
10
Solo ora dobbiamo considerare il termine c nella parte destra dell’equazione. Dato che la precedente equazione dimostra una soluzione per ax + by = 1, moltiplica entrambe le parti per c ottenendo a(cx) + b(cy) = c. Se (-25, -34) è una soluzione di 87x - 64y = 1, allora (-75, -102) è una soluzione di 87x-64y = 3.
11
Se un’equazione diofantea lineare ha una soluzione, allora ha infinite soluzioni. Questo perché ax + by = a(x+b) + b(y-a) = a(x+2b) + b(y-2a), e in generale ax + by = a(x+kb) + b(y-ka) per ogni k intero. Perciò, dato che (-75,-102) è una soluzione di 87x-64y = 3, altre soluzioni sono (-11,-15), (53,72), (117,159) ecc. La soluzione generale può essere scritta come (53+64k, 72+87k) dove k è qualunque numero intero.

Pubblicità

Consigli

Dovresti essere in grado di farlo anche con carta e penna, ma quando lavori con numeri grandi, una calcolatrice, o meglio ancora, un foglio di calcolo può essere molto utile.
Controlla i tuoi risultati. L'uguaglianza del passaggio 8 dovrebbe aiutarti a individuare eventuali errori commessi usando l’algoritmo di Euclide o nella compilazione della tabella. Verificare il risultato finale con l'equazione originale dovrebbe evidenziare eventuali altri errori.