Un’equazione diofantea lineare chiede di trovare numeri interi, non semplicemente numeri reali. Confrontiamo la teoria con l’esempio 18x + 12y = 72, dall’algoritmo di Euclide fino a tutte le soluzioni. Non cerchiamo una coppia fortunata per tentativi: costruiamo un procedimento completo e poi imponiamo gli eventuali vincoli del problema.
Apri il laboratorio: inserisci a, b e c e segui tutti i passaggi
1. Equazione di partenza
| Parte teorica | Esempio pratico |
|---|---|
La forma è ax + by = c, con a, b, c ∈ ℤ. Cerchiamo x, y ∈ ℤ. | 18x + 12y = 72 |
Per il procedimento principale supponiamo a, b ≠ 0. I coefficienti nulli sono trattati alla fine. | a = 18, b = 12, c = 72 |
2. Calcolo del massimo comune divisore
Applichiamo l’algoritmo di Euclide: ogni divisione produce un resto più piccolo del divisore.
| Parte teorica | Esempio pratico |
|---|---|
Calcoliamo d = MCD(|a|,|b|) mediante divisioni successive. | 18 = 12×1 + 6 |
| Dividiamo il divisore precedente per il resto, fino a ottenere resto zero. | 12 = 6×2 + 0 |
| L’ultimo resto non nullo è il MCD, preso positivo. | d = 6 |
3. Verifica dell’esistenza
| Parte teorica | Esempio pratico |
|---|---|
Esistono soluzioni intere se e solo se d ∣ c: il MCD divide il termine noto. | 6 ∣ 72 |
Se il MCD non divide c, non esiste nessuna coppia intera. Se lo divide, proseguiamo. | 72/6 = 12 |
Perché è necessario? Ogni ax + by è un multiplo del MCD. Perché è sufficiente? L’identità di Bézout, costruita al prossimo passo, produce una soluzione ogni volta che c/d è intero.
4. Euclide esteso e identità di Bézout
Risalire dalle divisioni significa riscrivere i resti come combinazioni dei coefficienti iniziali.
| Parte teorica | Esempio pratico |
|---|---|
| Isoliamo l’ultimo resto non nullo e sostituiamo all’indietro gli eventuali resti precedenti. | 6 = 18 - 12 |
Otteniamo due interi u, v tali che au + bv = d: è l’identità di Bézout. | 18(1) + 12(-1) = 6 |
I coefficienti della combinazione ottenuta sono u e v. | u = 1, v = -1 |
5. Calcolo di una soluzione particolare
Trasformiamo l’identità di Bézout nell’equazione originale moltiplicando per lo stesso numero.
| Parte teorica | Esempio pratico |
|---|---|
Partiamo da au + bv = d. | 18(1) + 12(-1) = 6 |
Il moltiplicatore è m = c/d. | 72/6 = 12 |
Moltiplichiamo tutta l’identità: a(um) + b(vm) = c. | 18(12) + 12(-12) = 72 |
Quindi x₀ = u(c/d) e y₀ = v(c/d). | x₀ = 12, y₀ = -12 |
La coppia (12,-12) è corretta anche se una coordinata è negativa: per ora cerchiamo soluzioni in ℤ. La non negatività sarà una richiesta ulteriore.
6. Dimostrazione della formula generale
| Parte teorica | Esempio pratico |
|---|---|
| Scriviamo l’equazione originale. | 18x + 12y = 72 |
| Scriviamo l’equazione soddisfatta dalla soluzione particolare. | 18(12) + 12(-12) = 72 |
| Sottraiamo membro a membro. | 18(x - 12) + 12(y + 12) = 0 |
| Portiamo il secondo termine a destra. | 18(x - 12) = -12(y + 12) |
Dividiamo entrambi i membri per d. | 3(x - 12) = -2(y + 12) |
Poniamo a′ = a/d e b′ = b/d. I due numeri sono coprimi. Da a′(x - x₀) = -b′(y - y₀), per il lemma di Euclide, segue b′ ∣ (x - x₀).
Esiste quindi un intero k con x - x₀ = b′k. Sostituendo e semplificando ricaviamo y - y₀ = -a′k.
x = x₀ + (b/d)ky = y₀ - (a/d)kk ∈ ℤ
Abbiamo dimostrato che ogni soluzione ha questa forma. Viceversa, sostituendo le formule nell’equazione, i termini con k si cancellano: ogni intero k dà una soluzione. Non ne manca nessuna.
7. Applicazione della formula generale
| Parte teorica | Esempio pratico |
|---|---|
Prima coordinata: x = x₀ + (b/d)k. | x = 12 + (12/6)k |
Seconda coordinata: y = y₀ - (a/d)k. | y = -12 - (18/6)k |
Semplifichiamo e ricordiamo che k può essere qualsiasi intero. | x = 12 + 2k; y = -12 - 3k; k ∈ ℤ |
Le formule descrivono infinite soluzioni intere, comprese quelle con coordinate negative. Una soluzione particolare diversa può dare formule dall’aspetto diverso, ma rappresenta la stessa famiglia dopo uno spostamento del parametro.
8. Ricerca delle soluzioni non negative
Se il problema richiede quantità non negative, imponiamo entrambe le condizioni, non soltanto una.
| Parte teorica | Esempio pratico |
|---|---|
Imponiamo x₀ + (b/d)k ≥ 0. | 12 + 2k ≥ 0 ⇒ k ≥ -6 |
Imponiamo y₀ - (a/d)k ≥ 0. | -12 - 3k ≥ 0 ⇒ k ≤ -4 |
Intersechiamo gli intervalli e prendiamo soltanto i valori interi di k. | -6 ≤ k ≤ -4 |
In generale un vincolo ha la forma q + tk ≥ m, con m = 0 per quantità non negative e m = 1 per quantità intere strettamente positive.
- Se
t > 0:k ≥ ⌈(m - q)/t⌉. - Se
t < 0:k ≤ ⌊(m - q)/t⌋; il verso cambia dividendo per un numero negativo. - Se
t = 0, controlliamo direttamente seq ≥ m.
⌈ ⌉ e ⌊ ⌋ indicano rispettivamente arrotondamento per eccesso e per difetto. Un intervallo vuoto significa nessuna soluzione ammissibile; con coefficienti di segno opposto l’intervallo può essere illimitato.
9. Calcolo delle soluzioni
Nell’esempio k ∈ {-6,-5,-4}. Sostituiamo ciascun valore nelle due formule.
| k | x = 12 + 2k | y = -12 - 3k |
|---|---|---|
| -6 | 0 | 6 |
| -5 | 2 | 3 |
| -4 | 4 | 0 |
Le tre soluzioni non negative sono (0,6), (2,3), (4,0). Verifica: 18×0 + 12×6 = 72, 18×2 + 12×3 = 72, 18×4 + 12×0 = 72.
Se chiediamo invece x ≥ 1 e y ≥ 1, rimane soltanto (2,3). «Intere», «non negative» e «strettamente positive» sono tre richieste diverse.
10. Schema riassuntivo del metodo
| Fase | Parte teorica | Esempio pratico |
|---|---|---|
| Equazione | ax + by = c | 18x + 12y = 72 |
| MCD | d = MCD(|a|,|b|) | d = 6 |
| Esistenza | d ∣ c | 6 ∣ 72 |
| Bézout | au + bv = d | 18 - 12 = 6 |
| Moltiplicatore | m = c/d | m = 12 |
| Soluzione particolare | x₀ = um, y₀ = vm | (12,-12) |
| Formula generale: x | x = x₀ + (b/d)k | x = 12 + 2k |
| Formula generale: y | y = y₀ - (a/d)k | y = -12 - 3k |
| Condizioni | x, y ≥ 0 | -6 ≤ k ≤ -4 |
| Soluzioni | k ∈ ℤ | (0,6), (2,3), (4,0) |
11. Due compiti distinti, anche con numeri più grandi
- Euclide esteso trova una soluzione particolare senza tentativi.
- La formula generale produce tutte le altre soluzioni variando il parametro intero
k.
Per 252x + 198y = 900 le divisioni sono 252 = 198×1 + 54, 198 = 54×3 + 36, 54 = 36×1 + 18, 36 = 18×2 + 0. Il MCD è 18.
Risalendo otteniamo 18 = 4×252 - 5×198. Moltiplichiamo per 900/18 = 50: una soluzione particolare è (200,-250). La famiglia è x = 200 + 11k, y = -250 - 14k.
La non negatività impone k ≥ -18 e k ≤ -18. Quindi k = -18 e l’unica coppia non negativa è (2,2). Nel laboratorio puoi caricare questo esempio e vedere ogni sostituzione all’indietro.
12. Casi impossibili, segni e coefficienti nulli
Nessuna soluzione intera: 18x + 12y = 73 è impossibile perché 6 non divide 73. Nessuna soluzione non negativa: 6x + 10y = 2 ha la famiglia x = 2 + 5k, y = -1 - 3k, ma richiede contemporaneamente k ≥ 0 e k ≤ -1.
Coefficienti negativi: Euclide si applica ai valori assoluti. Se |a|u′ + |b|v′ = d, basta ripristinare i segni nei coefficienti di Bézout per ottenere au + bv = d. La formula generale e i vincoli restano validi.
- Se
a = 0eb ≠ 0, serve chebdividac:y = c/bè fissato exè libero. - Se
b = 0ea ≠ 0, analogamentex = c/aè fissato eyè libero. - Se
a = b = 0ec ≠ 0, non esistono soluzioni. Se anchec = 0, ogni coppia intera è una soluzione:x = s,y = t, con due parametri indipendenti.
Il laboratorio usa calcoli interi esatti, senza arrotondare i coefficienti. Accetta fino a 80 cifre per ciascuno dei tre parametri e distingue le formule complete dalla tabella, che mostra al massimo 25 soluzioni per pagina.
Apri il laboratorio: inserisci a, b e c e segui tutti i passaggi