Calcolatrice di equazioni diofantee lineari ax + by = c (con i passaggi dell’algoritmo di Euclide)

Scrivi i coefficienti dell’equazione diofantea lineare ax + by = c. La formula qui sotto è collegata ai campi, quindi puoi anche modificare i numeri direttamente al suo interno. Cambiando «Soluzioni da cercare» puoi tenere solo le soluzioni intere positive.

Coefficiente a di x

Coefficiente b di y

Termine noto c a destra

Soluzioni da cercare

Scrivi solo numeri interi (niente decimali né frazioni). Vanno bene anche i numeri negativi. Se manca il termine in x o in y, scrivi 0 come suo coefficiente.

Risultato e grafico

Scrivi i coefficienti a, b e c nei campi a sinistra e fai clic su «Calcola». Le soluzioni intere e il grafico compariranno qui.

Indice

[ Chiudi X ]

Cosa puoi fare in questa pagina
A cosa serve questo calcolo?
Come si usa
Formule e grafici
Simboli e termini
- Simboli
- Termini
Cosa conviene sapere prima
Come calcolarlo con Excel
Come calcolarlo con Fogli Google
Come calcolarlo con Python
La formula in LaTeX e in altre notazioni matematiche (da copiare)
Come chiedere a ChatGPT di fare il calcolo
I punti di forza di DataChef
Funzioni correlate
Tutte le calcolatrici di NumberChef

Cosa puoi fare in questa pagina

Scrivi i coefficienti interi \(a,\ b,\ c\) e ottieni le coppie di numeri interi \(x,\ y\) che soddisfano \(ax + by = c\) (le soluzioni intere)
Se \(c\) non è un multiplo del massimo comun divisore di \(a\) e \(b\), non esistono soluzioni intere. La pagina fa questo controllo e mostra anche perché
Puoi seguire riga per riga la tabella delle divisioni dell’algoritmo di Euclide e la tabella che risale all’indietro tra i resti per costruire una soluzione particolare
La risposta non è una sola coppia: ottieni la soluzione generale \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (con \(t\) numero intero qualsiasi) e una tabella delle soluzioni per diversi valori di \(t\)
Puoi tenere solo le soluzioni positive oppure solo quelle non negative. Così risolvi direttamente problemi come «quanti biglietti da 50 € e da 80 € fanno esattamente 1000 €?»

Come coefficienti puoi usare solo numeri interi (niente decimali né frazioni). Ogni coefficiente può avere fino a 15 cifre, e \(a\) e \(b\) non possono essere entrambi 0.

A cosa serve questo calcolo?

Trovare le combinazioni che danno un importo o un numero esatto

Comprare solo biglietti da 50 € e da 80 € per spendere esattamente 1000 €, pesare un oggetto con due soli tipi di pesi, o ottenere una lunghezza precisa con pezzi di lunghezza fissa: problemi come questi, «combinare cose di misura fissa per arrivare esattamente a un obiettivo», sono proprio il problema di trovare le soluzioni intere di \(ax + by = c\).
Non si può comprare un numero negativo di biglietti, quindi nella pratica la risposta si ottiene solo dopo aver ristretto la ricerca alle soluzioni intere positive.

Capire quali ordini si possono confezionare esattamente

Se hai solo scatole da 6 e scatole da 10, poter confezionare un ordine di esattamente \(c\) pezzi dipende dal fatto che \(6x + 10y = c\) abbia una soluzione con numeri interi maggiori o uguali a 0. Il MCD di 6 e 10 è 2, quindi un ordine con un numero dispari di pezzi non si può mai confezionare esattamente, comunque si combinino le scatole.
Quando si confezionano alimenti o componenti, sapere quali quantità si possono ottenere dice quali ordini puoi accettare e quali formati di scatola tenere in magazzino.

Misurare una quantità esatta con recipienti senza tacche

Il famoso rompicapo di misurare esattamente 4 litri con una sola brocca da 5 litri e una da 3 litri corrisponde alle soluzioni intere di \(5x + 3y = 4\) (\(x\) e \(y\) contano, con il segno, quante volte si riempie o si svuota ciascuna brocca). Poiché \(\mathrm{MCD}(5,\ 3) = 1\), l’equazione dice in anticipo che con queste due brocche si può misurare qualsiasi numero intero di litri.
È la stessa matematica che usi in laboratorio o in cucina quando ti chiedi: «Posso misurare la quantità che mi serve solo con gli strumenti che ho?»

Costruire le chiavi della crittografia RSA su internet

La crittografia RSA, che protegge l’home banking e gli acquisti online, ricava il valore della chiave privata \(d\) da quello della chiave pubblica \(e\) risolvendo l’equazione diofantea lineare \(e d + \varphi k = 1\) (\(\varphi\) è un numero intero che dipende dalla chiave). Lo strumento usato è lo stesso algoritmo di Euclide esteso di questa pagina.
Questa procedura la risolve all’istante anche per numeri di centinaia di cifre, ed è una delle cose che rendono praticabile la crittografia.

Una pianificazione della produzione che usa tutto il materiale

Supponi che il prodotto A usi \(a\) kg di materiale per pezzo e il prodotto B ne usi \(b\), e di voler usare esattamente i \(c\) kg che hai. Questo piano è il problema di trovare le soluzioni di \(ax + by = c\) in numeri interi maggiori o uguali a 0. Non si può fare mezzo prodotto, quindi la risposta deve essere un numero intero.
Il campo che tratta i problemi di pianificazione le cui risposte devono essere numeri interi si chiama programmazione lineare intera. Si usa per la pianificazione della produzione e dei turni di lavoro, per la pianificazione delle consegne e altro.

Formule e grafici

Quando esistono soluzioni intere

Grafico

Notazione matematica (la notazione abituale)

\(c\) \(=\) \(\mathrm{MCD}(a,\ b)\) \(\times\) \(m\)

A parole (i simboli sostituiti da parole)

③ \(c\): termine noto a destra \(=\) ① \(g\): MCD di \(a\) e \(b\) \(\times\) ② \(m\): un numero intero

La formula a parole

① Moltiplica il \(g\): MCD di \(a\) e \(b\)

② per \(m\): un numero intero

③ Se questo prodotto può essere esattamente uguale al \(c\): termine noto a destra (cioè se \(c\) è un multiplo di \(g\)), esistono soluzioni intere. Altrimenti non ce ne sono

Un esempio semplice

L’equazione \(2x + 4y = 6\) ha soluzioni intere, mentre \(2x + 4y = 5\) non ne ha nessuna (in entrambe \(\mathrm{MCD}(2,\ 4) = 2\))

termine noto a destra (6) \(=\) MCD (2) \(\times\) numero intero (3)

\(\mathrm{MCD}(2,\ 4) = 2\)

\(6 = 2 \times 3 \quad \Rightarrow \quad 2 \times 1 + 4 \times 1 = 6\)

\(5 = 2 \times 2 + 1 \quad \Rightarrow \quad 2x + 4y \neq 5\)

L’idea chiave

Perché \(c\) deve essere un multiplo di \(g\)? Sia \(a\) sia \(b\) sono multipli di \(g\), quindi si può scrivere \(a = g a'\) e \(b = g b'\). Allora il membro di sinistra diventa \(ax + by = g(a'x + b'y)\) Finché \(x\) e \(y\) sono numeri interi, il membro di sinistra è sempre un multiplo di \(g\) e nient’altro. Quindi, se il termine noto \(c\) non è un multiplo di \(g\), nessuna coppia di numeri interi può rendere uguali i due membri. Al contrario, se \(c\) è un multiplo di \(g\), una soluzione esiste sempre (lo garantisce l’identità di Bézout, la formula successiva). Sul grafico la differenza sta nel fatto che la retta \(ax + by = c\) passi per dei punti a coordinate intere (punti in cui \(x\) e \(y\) sono entrambi numeri interi) oppure scivoli tra l’uno e l’altro.

Identità di Bézout (una coppia di numeri interi data dall’algoritmo di Euclide)

Notazione matematica (la notazione abituale)

\(a x_1\) \(+\) \(b y_1\) \(=\) \(\mathrm{MCD}(a,\ b)\)

A parole (i simboli sostituiti da parole)

① \(a x_1\): \(a\) per il numero intero \(x_1\) dato dall’algoritmo di Euclide \(+\) ② \(b y_1\): \(b\) per il numero intero \(y_1\) dato dall’algoritmo di Euclide \(=\) ③ \(g\): MCD di \(a\) e \(b\)

La formula a parole

① Somma il termine \(a x_1\): \(a\) per il numero intero \(x_1\) dato dall’algoritmo di Euclide

② e il termine \(b y_1\): \(b\) per il numero intero \(y_1\) dato dall’algoritmo di Euclide

③ e la somma può essere resa uguale al \(g\): MCD di \(a\) e \(b\) . Due numeri interi \(x_1,\ y_1\) di questo tipo esistono sempre, e si trovano ripercorrendo all’indietro l’algoritmo di Euclide

Un esempio semplice

Applica l’algoritmo di Euclide a \(7\) e \(5\) e risali all’indietro tra i resti (\(\mathrm{MCD}(7,\ 5) = 1\))

\(7\) per il numero intero \(-2\) \(+\) \(5\) per il numero intero \(3\) \(=\) MCD (1)

\(7 = 5 \times 1 + 2, \quad 5 = 2 \times 2 + 1\)

\(1 = 5 - 2 \times 2 = 5 - (7 - 5) \times 2 = 3 \times 5 - 2 \times 7\)

\(7 \times (-2) + 5 \times 3 = -14 + 15 = 1\)

L’idea chiave

Ogni resto dell’algoritmo di Euclide si può scrivere come somma di multipli interi dei due numeri di partenza. Infatti \(2 = 7 - 5\) e, se lo sostituisci al \(2\) del passaggio successivo, \(1 = 5 - 2 \times 2\), allora \(1\) diventa una somma di multipli interi di \(7\) e \(5\). L’algoritmo di Euclide esteso fa questo passo dopo passo per qualsiasi coppia di numeri. La coppia \(x_1,\ y_1\) che trovi dà il MCD \(g\), non \(c\), quindi non è ancora una soluzione della tua equazione. Moltiplica entrambi i membri per \(\dfrac{c}{g}\) e ottieni una soluzione dell’equazione che ti interessa. \(x_0 = \dfrac{c}{g} x_1, \quad y_0 = \dfrac{c}{g} y_1\) Per esempio, per \(7x + 5y = 3\), moltiplicando l’uguaglianza precedente per 3 si ottiene \(7 \times (-6) + 5 \times 9 = 3\), quindi \((x_0\,;\,y_0) = (-6\,;\,9)\) è una soluzione. Questa calcolatrice sposta la soluzione trovata verso numeri più piccoli e più facili da leggere prima di mostrarla (da qualunque coppia si parta, la soluzione generale qui sotto dà lo stesso insieme di soluzioni).

Tutte le soluzioni intere (soluzione generale)

Grafico

Notazione matematica (la notazione abituale)

\(x\) \(=\) \(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\)

\(y\) \(=\) \(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\)

A parole (i simboli sostituiti da parole)

\(x\): soluzione intera \(=\) ① \(x_0\): soluzione particolare \(+\) ② \(\dfrac{b}{g}\): passo di \(x\) ③ \(t\): un numero intero qualsiasi

\(y\): soluzione intera \(=\) ④ \(y_0\): soluzione particolare \(-\) ⑤ \(\dfrac{a}{g}\): passo di \(y\) \(t\): un numero intero qualsiasi

La formula a parole

① Parti dalla \(x_0\): soluzione particolare

② e aggiungi il \(\dfrac{b}{g}\): passo di \(x\)

③ moltiplicato per \(t\): un numero intero qualsiasi . Ottieni la soluzione intera \(x\)

④ Allo stesso tempo, parti dalla \(y_0\): soluzione particolare

⑤ e sottrai il \(\dfrac{a}{g}\): passo di \(y\) moltiplicato per lo stesso \(t\). Ottieni la soluzione intera \(y\). Ogni numero intero che metti al posto di \(t\) dà un’altra soluzione, e insieme sono tutte le soluzioni intere

Un esempio semplice

Per \(3x + 4y = 10\) una soluzione è \((x_0\,;\,y_0) = (2\,;\,1)\) e \(\mathrm{MCD}(3,\ 4) = 1\), quindi

\(x\): soluzione intera \(=\) soluzione particolare (2) \(+\) passo (4) numero intero \(t\)

\(y\): soluzione intera \(=\) soluzione particolare (1) \(-\) passo (3) numero intero \(t\)

\(3 \times 2 + 4 \times 1 = 10\)

\(x = 2 + 4t, \quad y = 1 - 3t\)

\(t = 1 \ \Rightarrow \ (x\,;\,y) = (6\,;\,-2), \quad 3 \times 6 + 4 \times (-2) = 10\)

\(t = -1 \ \Rightarrow \ (x\,;\,y) = (-2\,;\,4), \quad 3 \times (-2) + 4 \times 4 = 10\)

L’idea chiave

Perché \(x\) si sposta solo a passi di \(\dfrac{b}{g}\) e \(y\) solo a passi di \(\dfrac{a}{g}\)? Se \((x\,;\,y)\) e \((x_0\,;\,y_0)\) sono entrambe soluzioni, sottraendo un’equazione dall’altra si ottiene \(a(x - x_0) = -b(y - y_0)\) Dividi entrambi i membri per \(g\) e ottieni \(\dfrac{a}{g}(x - x_0) = -\dfrac{b}{g}(y - y_0)\). Qui \(\dfrac{a}{g}\) e \(\dfrac{b}{g}\) sono primi tra loro (il loro unico divisore comune è 1). Quindi il membro di sinistra deve essere un multiplo di \(\dfrac{b}{g}\). Poiché \(\dfrac{a}{g}\) non ha divisori in comune con esso, è \(x - x_0\) stesso a dover essere un multiplo di \(\dfrac{b}{g}\). Cioè \(x - x_0 = \dfrac{b}{g}t\), e da qui segue la formula per \(y\). Sul grafico, i punti a coordinate intere sulla retta \(ax + by = c\) sono allineati a distanza regolare: \(\dfrac{b}{g}\) in orizzontale e \(\dfrac{a}{g}\) in verticale (in su o in giù).

Come restringersi alle soluzioni intere positive

Grafico

Notazione matematica (la notazione abituale)

\(x_0\) \(+\) \(\dfrac{b}{g}\) \(t\) \(\geq 1\)

\(y_0\) \(-\) \(\dfrac{a}{g}\) \(t\) \(\geq 1\)

A parole (i simboli sostituiti da parole)

① \(x_0\): soluzione particolare \(+\) ② \(\dfrac{b}{g}\): passo di \(x\) ③ \(t\): un numero intero qualsiasi \(\geq 1\)

④ \(y_0\): soluzione particolare \(-\) ⑤ \(\dfrac{a}{g}\): passo di \(y\) \(t\): un numero intero qualsiasi \(\geq 1\)

La formula a parole

① La \(x_0\): soluzione particolare

② più il \(\dfrac{b}{g}\): passo di \(x\)

③ per \(t\): un numero intero qualsiasi (cioè la soluzione intera \(x\)) deve essere almeno 1, e

④ la \(y_0\): soluzione particolare

⑤ meno il \(\dfrac{a}{g}\): passo di \(y\) per lo stesso \(t\) (cioè la soluzione intera \(y\)) deve essere anch’essa almeno 1. Trova l’intervallo di \(t\) che va bene per entrambe e hai tutte le soluzioni intere positive

Un esempio semplice

Per avere esattamente 47 pezzi usando solo confezioni da 3 e da 5 (\(3x + 5y = 47\), \((x_0\,;\,y_0) = (4\,;\,7)\)):

soluzione particolare (4) \(+\) passo (5) numero intero \(t\) \(\geq 1\)

soluzione particolare (7) \(-\) passo (3) numero intero \(t\) \(\geq 1\)

\(3 \times 4 + 5 \times 7 = 47\)

\(4 + 5t \geq 1 \ \Leftrightarrow \ t \geq -\dfrac{3}{5} \ \Leftrightarrow \ t \geq 0\)

\(7 - 3t \geq 1 \ \Leftrightarrow \ t \leq 2\)

\(0 \leq t \leq 2 \ \Rightarrow \ (x\,;\,y) = (4\,;\,7),\ (9\,;\,4),\ (14\,;\,1)\)

L’idea chiave

Nei problemi in cui si contano biglietti, oggetti o persone, la risposta deve essere un numero intero positivo (o un numero intero maggiore o uguale a 0). Se inserisci la soluzione generale in delle disequazioni e trovi l’intervallo di \(t\), tieni solo le soluzioni adatte. Poiché \(t\) è un numero intero, anche quando un estremo è una frazione, come in \(t \geq -\dfrac{3}{5}\), puoi stringerlo al numero intero più vicino all’interno (qui \(t \geq 0\)). È il passaggio chiave. Se \(a\) e \(b\) hanno lo stesso segno (per esempio sono entrambi positivi), una disequazione dà un limite inferiore e l’altra un limite superiore, quindi le soluzioni sono sempre in numero finito. Se i segni sono diversi (per esempio \(3x - 5y = 1\)), i due limiti vanno nello stesso verso e le soluzioni intere positive sono infinite. Se un coefficiente è 0 (per esempio \(0x + 5y = 10\)), l’altra variabile ha un solo valore possibile e la variabile con coefficiente 0 può essere qualsiasi. Se quel valore rispetta la condizione, le soluzioni sono infinite; altrimenti non ce ne sono. Può anche succedere che nessun \(t\) rispetti la condizione. In quel caso la risposta è «non c’è nessuna combinazione che vada bene».

L’equazione diofantea lineare \(ax + by = c\) ha soluzioni intere solo quando \(c\) è un multiplo di \(g\), il massimo comun divisore di \(a\) e \(b\). In quel caso, risali all’indietro l’algoritmo di Euclide per costruire una soluzione particolare \((x_0\,;\,y_0)\). Tutte le altre soluzioni sono allora \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (con \(t\) numero intero qualsiasi).

Simboli e termini

Simboli

\(a,\ b\)	a, b	I coefficienti che moltiplicano \(x\) e \(y\). Per i numeri fissi si usano per tradizione le lettere dell’inizio dell’alfabeto, \(a,\ b,\ c\). In questa pagina sono entrambi numeri interi.
\(c\)	c	Il termine noto a destra dell’equazione. È il totale che vuoi ottenere, e il fatto che sia un multiplo del MCD decide se esistono soluzioni.
\(x,\ y\)	x, y	Le incognite che cerchi. Usare le lettere della fine dell’alfabeto per le incognite è un’abitudine che si dice sia stata diffusa da Cartesio. In questa pagina valgono come risposta solo i valori interi.
\(\mathrm{MCD}(a,\ b)\)	MCD di a e b	Il massimo comun divisore di \(a\) e \(b\), abbreviato MCD. Nei testi di teoria dei numeri compare anche come gcd (dall’inglese «greatest common divisor») o, più in breve, come \((a,\ b)\).
\(g\)	g	Un nome breve per il massimo comun divisore \(\mathrm{MCD}(a,\ b)\). Serve a tenere corte le formule, come \(\dfrac{b}{g}\) e \(\dfrac{a}{g}\) nella soluzione generale.
\(x_0,\ y_0\)	x zero, y zero	La soluzione particolare, cioè la prima soluzione intera che trovi. Lo 0 piccolo indica che è il punto di partenza, la «soluzione numero 0». Tutte le soluzioni intere si scrivono a partire da qui.
\(x_1,\ y_1\)	x uno, y uno	La coppia di numeri interi che trovi ripercorrendo all’indietro l’algoritmo di Euclide. Soddisfa \(a x_1 + b y_1 = g\). Moltiplicala per \(\dfrac{c}{g}\) per ottenere la soluzione particolare \((x_0\,;\,y_0)\).
\(t\)	t	Una variabile che può essere un numero intero qualsiasi (un parametro). Permette a una sola formula di descrivere tutte le soluzioni intere insieme. Ogni numero intero che metti al posto di \(t\) dà un’altra soluzione intera.
\(m\)	m	Il numero intero che dice quante volte \(g\) sta in \(c\). Per i numeri interi si usano spesso lettere come \(m\), \(n\) e \(k\), e si dice che \(m\) venga da «multiplo». Esistono soluzioni intere se si può scrivere \(c = g \times m\), e solo in quel caso.
\(q\)	q	Il quoziente di una divisione, dall’iniziale di «quoziente». Nella tabella dell’algoritmo di Euclide è il \(2\) di \(13 = 5 \times 2 + 3\).
\(r\)	r	Il resto di una divisione, dall’iniziale di «resto». Nella tabella dell’algoritmo di Euclide è il \(3\) di \(13 = 5 \times 2 + 3\). L’algoritmo si ferma quando questo resto arriva a 0.
\(\geq\)	maggiore o uguale a	Il segno di disuguaglianza che significa «il membro di sinistra è maggiore o uguale a quello di destra». \(x \geq 1\) dice che \(x\) vale 1 o più. Il suo compagno \(\leq\) significa «minore o uguale a».

Termini

equazione diofantea lineare	Il tipo più semplice di equazione diofantea: un’equazione lineare con due incognite ma una sola equazione, come \(ax + by = c\). Sui numeri reali ogni punto della retta è una soluzione, quindi la soluzione non è unica. Anche tenendo solo le soluzioni intere, di solito sono infinite.
equazione diofantea	Il nome delle equazioni le cui soluzioni devono essere numeri interi. Viene da Diofanto, un matematico della Grecia antica. L’equazione diofantea lineare di questa pagina è il tipo più semplice.
soluzione intera	Una soluzione dell’equazione in cui sia \(x\) sia \(y\) sono numeri interi. Nei problemi su quantità che non si possono dividere, come il numero di biglietti, oggetti o persone, hanno senso solo le soluzioni intere.
soluzione particolare	La prima coppia che trovi tra le infinite soluzioni intere. Va bene una qualsiasi. A partire da essa, la soluzione generale descrive tutte le soluzioni.
soluzione generale	Tutte le soluzioni intere scritte in un’unica formula con un numero intero \(t\). Ogni numero intero che metti al posto di \(t\) dà un’altra soluzione.
massimo comun divisore (MCD)	Il più grande numero intero positivo che divide ciascuno di due o più numeri interi. In un’equazione diofantea lineare questo valore decide sia se esistono soluzioni sia a che distanza stanno l’una dall’altra.
algoritmo di Euclide	Un modo per trovare il massimo comun divisore dividendo il numero più grande per il più piccolo e sostituendo la coppia con il divisore e il resto, più volte. Il divisore del passaggio in cui il resto arriva a 0 è il MCD. Compare negli «Elementi» di Euclide, intorno al III secolo a.C., ed è spesso detto il più antico algoritmo del mondo. Si chiama anche algoritmo delle divisioni successive.
algoritmo di Euclide esteso	Un modo per scrivere il massimo comun divisore nella forma \(a x_1 + b y_1\), sostituendo dal basso verso l’alto le uguaglianze delle divisioni dell’algoritmo di Euclide. Serve a costruire una soluzione particolare di un’equazione diofantea lineare.
identità di Bézout	Il teorema secondo cui esistono sempre due numeri interi \(x_1,\ y_1\) con \(a x_1 + b y_1 = \mathrm{MCD}(a,\ b)\). Prende il nome dal matematico francese Bézout. È il motivo per cui un’equazione diofantea lineare si può risolvere.
primi tra loro	Due numeri interi sono primi tra loro (o coprimi) quando il loro massimo comun divisore è 1. Per esempio, 3 e 4 sono primi tra loro. \(\dfrac{a}{g}\) e \(\dfrac{b}{g}\) sono sempre primi tra loro, ed è per questo che le soluzioni sono equidistanti.
multiplo	Un numero che si ottiene moltiplicando un numero intero per un altro numero intero. I multipli di \(10\) sono \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\). Anche lo zero e i numeri negativi contano come multipli.
resto	Ciò che avanza quando una divisione tra numeri interi non è esatta. \(13 \div 5\) ha quoziente \(2\) e resto \(3\). L’algoritmo di Euclide lavora solo con questi resti.
quoziente	Nella divisione tra numeri interi, il numero intero di volte che il divisore ci sta. In \(13 = 5 \times 2 + 3\) il quoziente è \(2\).
punto a coordinate intere	Un punto del piano cartesiano le cui coordinate \(x\) e \(y\) sono entrambe numeri interi, come gli angoli dei quadretti su un foglio a quadretti (si dice anche punto reticolare). Le soluzioni intere di un’equazione diofantea lineare sono esattamente i punti a coordinate intere sulla retta \(ax + by = c\).
parametro	Una variabile che puoi far variare liberamente, usata per scrivere un intero insieme di soluzioni con un’unica formula. In questa pagina il parametro è \(t\).
coefficiente	Il numero davanti a una lettera. In \(3x\) il coefficiente è \(3\). Quando non c’è nessun numero, come in \(x\), il coefficiente è 1.
disequazione	Una relazione che confronta la grandezza di due valori, come \(t \geq 0\). Si usa per restringersi alle soluzioni intere positive. Il segno usato si chiama segno di disuguaglianza.

Cosa conviene sapere prima

Ecco cosa ti aiuta a usare il calcolo di questa pagina capendo davvero che cosa stai facendo, e non solo premendo il pulsante.
Se ti blocchi, ripassare questi argomenti è la via più rapida.

Divisione con resto (classi 3ª–5ª della primaria, 8-11 anni)	Sapere che \(13 \div 5\) dà «quoziente \(2\), resto \(3\)» e saperlo riscrivere in un’unica uguaglianza, \(13 = 5 \times 2 + 3\) Sapere che il resto è sempre minore del divisore (almeno \(0\) e minore del divisore)
Divisori, multipli e MCD (classe 5ª della primaria – classe 1ª della secondaria di primo grado, 10-12 anni)	Saper passare da «\(6\) è un multiplo di \(3\)» a «\(3\) è un divisore di \(6\)» e viceversa Saper trovare che il massimo comun divisore di \(12\) e \(18\) è \(6\) (va bene anche con la scomposizione in fattori primi) Sapere che due numeri il cui MCD è \(1\) si dicono «primi tra loro»
Espressioni letterali ed equazioni di primo grado (classi 2ª–3ª della secondaria di primo grado, 12-14 anni)	Sapere che in un’espressione come \(ax + by\), \(a\) e \(b\) sono coefficienti e \(x\) e \(y\) sono incognite Saper risolvere rispetto a \(y\) un’equazione come \(3 \times 2 + 5y = 1\) Saper raccogliere un fattore comune, come in \(4x + 6y = 2(2x + 3y)\)
Equazioni lineari in due incognite e loro grafico (biennio della secondaria di secondo grado, 14-16 anni)	Sapere che \(ax + by = c\) è una retta nel piano cartesiano Sapere che con due incognite e una sola equazione non c’è una sola risposta, e ogni punto della retta è una soluzione
Disequazioni (biennio della secondaria di secondo grado, 14-16 anni)	Saper riscrivere \(5t \geq 1\) nella forma \(t \geq \dfrac{1}{5}\) Sapere che dividendo entrambi i membri per un numero negativo il verso della disequazione si inverte Sapere che se \(t \leq \dfrac{5}{3}\) e \(t\) è un numero intero, si può stringere fino a \(t \leq 1\)
Calcolo con le frazioni (classe 5ª della primaria – classe 1ª della secondaria di primo grado, 10-12 anni)	Saper semplificare una frazione come \(\dfrac{80}{10} = 8\) Saper confrontare sulla retta dei numeri frazioni negative come \(-\dfrac{3}{8}\)

Come calcolarlo con Excel

Copia tutta la tabella qui sotto e incollala nella cella A1 di Excel. Funziona così com’è.

Tabella per verificare se esistono soluzioni intere

Coefficiente a di x	50
Coefficiente b di y	80
Termine noto c a destra	1000
MCD g	=MCD(B1;B2)
Resto di c ÷ g	=RESTO(B3;B4)
Ci sono soluzioni intere?	=SE(B5=0;"Ci sono soluzioni";"Nessuna soluzione")

Tabella per verificare l’identità di Bézout

Coefficiente a di x	50
Coefficiente b di y	80
x1 dall’algoritmo di Euclide	-3
y1 dall’algoritmo di Euclide	2
a×x1 + b×y1	=B1B3+B2B4
MCD g	=MCD(B1;B2)

Tabella per ricavare le soluzioni dalla soluzione generale

Coefficiente a di x	50
Coefficiente b di y	80
Termine noto c a destra	1000
MCD g	=MCD(B1;B2)
Soluzione particolare x0	4
Soluzione particolare y0	10
Numero intero t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Verifica a×x + b×y	=B1B8+B2B9

Tabella per restringersi alle soluzioni intere positive

Coefficiente a di x	50
Coefficiente b di y	80
MCD g	=MCD(B1;B2)
Soluzione particolare x0	4
Soluzione particolare y0	10
Limite inferiore di t (da x ≥ 1)	=-INT((B4-1)/(B2/B3))
Limite superiore di t (da y ≥ 1)	=INT((B5-1)/(B1/B3))
Numero di soluzioni intere positive	=MAX(0;B7-B6+1)

Dopo averla incollata, le righe in alto (i coefficienti e la soluzione particolare) sono i dati da inserire e quelle in basso si calcolano da sole. MCD dà il massimo comun divisore, RESTO dà il resto di una divisione e INT scarta la parte decimale (arrotonda per difetto).
La prima tabella usa l’esempio 50x + 80y = 1000. Il MCD è 10 e 1000 ÷ 10 ha resto 0, quindi mostra «Ci sono soluzioni». Cambia 1000 in 1001 e diventa «Nessuna soluzione».
La seconda tabella controlla che x1 = −3 e y1 = 2, trovati ripercorrendo all’indietro l’algoritmo di Euclide, soddisfino davvero l’identità di Bézout. 50×(−3) + 80×2 = 10, che coincide con il MCD.
La terza tabella ricava una soluzione dalla soluzione generale. Scrivi 1 per t e ottieni x = 12 e y = 5, e la riga di verifica torna a 1000. Prova altri numeri interi per t.
La quarta tabella si restringe alle soluzioni intere positive. Il limite inferiore di t è 0 e quello superiore è 1, quindi ci sono 2 soluzioni intere positive (t = 0 e t = 1). Queste due formule valgono nel caso in cui a e b siano entrambi positivi. Con un coefficiente negativo il verso della disequazione si inverte, quindi fai attenzione.

Come calcolarlo con Fogli Google

Copia tutta la tabella qui sotto e incollala nella cella A1 di Fogli Google. Funziona così com’è.

Tabella per verificare se esistono soluzioni intere

Coefficiente a di x	50
Coefficiente b di y	80
Termine noto c a destra	1000
MCD g	=MCD(B1;B2)
Resto di c ÷ g	=RESTO(B3;B4)
Ci sono soluzioni intere?	=SE(B5=0;"Ci sono soluzioni";"Nessuna soluzione")

Tabella per verificare l’identità di Bézout

Coefficiente a di x	50
Coefficiente b di y	80
x1 dall’algoritmo di Euclide	-3
y1 dall’algoritmo di Euclide	2
a×x1 + b×y1	=B1B3+B2B4
MCD g	=MCD(B1;B2)

Tabella per ricavare le soluzioni dalla soluzione generale

Coefficiente a di x	50
Coefficiente b di y	80
Termine noto c a destra	1000
MCD g	=MCD(B1;B2)
Soluzione particolare x0	4
Soluzione particolare y0	10
Numero intero t	1
x = x0 + (b/g)×t	=B5+(B2/B4)*B7
y = y0 − (a/g)×t	=B6-(B1/B4)*B7
Verifica a×x + b×y	=B1B8+B2B9

Tabella per restringersi alle soluzioni intere positive

Coefficiente a di x	50
Coefficiente b di y	80
MCD g	=MCD(B1;B2)
Soluzione particolare x0	4
Soluzione particolare y0	10
Limite inferiore di t (da x ≥ 1)	=-INT((B4-1)/(B2/B3))
Limite superiore di t (da y ≥ 1)	=INT((B5-1)/(B1/B3))
Numero di soluzioni intere positive	=MAX(0;B7-B6+1)

Le stesse formule di Excel funzionano così come sono (MCD, RESTO, INT, MAX e SE hanno in Fogli Google gli stessi nomi e la stessa funzione). Copia tutta la tabella, incollala nella cella A1 e sostituisci i coefficienti con i tuoi numeri.

Come calcolarlo con Python

from math import gcd

# coefficienti di ax + by = c (numeri interi)
a, b, c = 50, 80, 1000

def extended_gcd(x, y):
    # algoritmo di Euclide esteso: restituisce il MCD e s, t con x*s + y*t = MCD
    if y == 0:
        return x, 1, 0
    g, s, t = extended_gcd(y, x % y)
    return g, t, s - (x // y) * t

g = gcd(a, b)
if c % g != 0:
    print(f"{c} non è un multiplo di {g}, quindi non ci sono soluzioni intere")
else:
    _, s, t = extended_gcd(a, b)
    x0, y0 = s * (c // g), t * (c // g)   # soluzione particolare (una soluzione intera)
    step_x, step_y = b // g, a // g       # passo di x e passo di y
    # sposta la soluzione finché x è il più piccolo valore maggiore o uguale a 0, per averne una più facile da leggere
    n = x0 // step_x
    x0, y0 = x0 - n * step_x, y0 + n * step_y
    print(f"Soluzione particolare: (x, y) = ({x0}, {y0})")
    print(f"Soluzione generale: x = {x0} + {step_x}t, y = {y0} - {step_y}t (t è un numero intero qualsiasi)")
    for k in range(-2, 3):
        print(f"  t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
    # tieni solo le soluzioni intere positive (x >= 1 e y >= 1)
    t_low = -((1 - x0) // -step_x)
    t_high = (y0 - 1) // step_y
    print("Soluzioni intere positive:", [(x0 + step_x * k, y0 - step_y * k)
                                         for k in range(t_low, t_high + 1)])

Bastano math.gcd della libreria standard e un algoritmo di Euclide esteso scritto in modo ricorsivo. Questo esempio è 50x + 80y = 1000. Eseguendolo stampa la soluzione particolare (4, 10), la soluzione generale x = 4 + 8t, y = 10 − 5t e le soluzioni intere positive [(4, 10), (12, 5)]. Cambia i coefficienti e provalo (l’ultima parte, per le soluzioni intere positive, è scritta per il caso in cui a e b siano entrambi positivi).

La formula in LaTeX e in altre notazioni matematiche (da copiare)

Quando esistono soluzioni intere

c = gcd(a, b) × m

c = \gcd(a, b) \times m

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>c</mi>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>m</mi>
  </mrow>
</math>

c = gcd(a, b) * m

Mod[c, GCD[a, b]] == 0

irem(c, igcd(a, b)) = 0;

mod(c, gcd(a, b)) == 0

c = gcd(a,b) × m

Identità di Bézout (una coppia di numeri interi data dall’algoritmo di Euclide)

a·x₁ + b·y₁ = gcd(a, b)

a x_1 + b y_1 = \gcd(a, b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
    <mo>+</mo>
    <mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
    <mo>=</mo>
    <mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
  </mrow>
</math>

a*x_1 + b*y_1 = gcd(a, b)

ExtendedGCD[a, b]

igcdex(a, b, x1, y1);

[g, x1, y1] = gcd(a, b);

a x_1 + b y_1 = gcd(a,b)

Tutte le soluzioni intere (soluzione generale)

x = x₀ + (b/g)t, y = y₀ − (a/g)t

x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>,</mo><mspace width="1em"/>
    <mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
  </mrow>
</math>

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Solve[a x + b y == c, {x, y}, Integers]

isolve(a*x + b*y = c);

S = solve(a*x + b*y == c, [x y], 'Integer', true);

x = x_0 + (b/g)t, y = y_0 - (a/g)t

Come restringersi alle soluzioni intere positive

x₀ + (b/g)t ≥ 1 e y₀ − (a/g)t ≥ 1

x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <msub><mi>x</mi><mn>0</mn></msub>
    <mo>+</mo>
    <mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
    <mo>,</mo><mspace width="1em"/>
    <msub><mi>y</mi><mn>0</mn></msub>
    <mo>&#x2212;</mo>
    <mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
    <mo>&#x2265;</mo><mn>1</mn>
  </mrow>
</math>

x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1

Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]

isolve({a*x + b*y = c, x >= 1, y >= 1});

S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);

x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1

Come chiedere a ChatGPT di fare il calcolo

Sei un assistente per il calcolo di matematica (proprietà dei numeri interi). Esegui il calcolo seguente eseguendo davvero del codice Python e basa la risposta solo sui numeri ottenuti dall’esecuzione (non rispondere a mente né a stima).

Trova le soluzioni intere dell’equazione diofantea lineare 50x + 80y = 1000.
Mostra ciascuna delle cose seguenti:
1. Il massimo comun divisore di 50 e 80, e se 1000 ne è un multiplo
2. I passaggi di divisione dell’algoritmo di Euclide (fino a quando il resto è 0) e gli x1, y1 con 50×x1 + 80×y1 = MCD trovati ripercorrendoli all’indietro
3. Una soluzione particolare (x0, y0) e la soluzione generale x = x0 + (b/g)t, y = y0 − (a/g)t
4. Tutte le soluzioni intere in cui x e y sono entrambi maggiori o uguali a 1

In Python usa math.gcd e l’algoritmo di Euclide esteso per calcolare in modo esatto, e mostra le formule usate e i numeri ottenuti dall’esecuzione.

Come si usa

1

Inserisci i numeri

Scrivi nei campi i numeri con cui vuoi fare il calcolo
2

Calcola

Fai clic sul pulsante «Calcola»
3

Guarda il risultato

Il risultato compare subito. Nella stessa pagina trovi anche lo svolgimento del calcolo e la spiegazione della formula