Lezione 17: Equazioni diofantee e congruenze lineari in Algebra 1

Equazioni diofantee lineari

Un'equazione diofantea è un'equazione in una o più incognite a coefficienti interi, di cui si ricercano le soluzioni intere. Un'equazione diofantea a due incognite si dice lineare se è della forma ax + by = c con a, b, c E Z. Una sua soluzione è una coppia (m, n) E Z x Z tale che am+ bn = c. Risolvere un'equazione significa trovarne tutte le soluzioni. Due equazioni diofantee si dicono equivalenti se hanno le stesse soluzioni.

Lemma

Dati a, b E Z, con b = 0, sia d = MCD(a, b). Allora ald e b/d sono coprimi.

Dimostrazione del Lemma

Poniamo a/d = a' e b/d = b', così che a = da' e b = db'. Se k E Z è un divisore comune ad a' e b', allora Ja" , b" E Z, a' = ka", b' = kb". Ora a' = ka", b' = kb" = a = da' = dka", b = db' = dkb", quindi dk è un divisore comune ad a e b, quindi dk | d, da cui k = ±1. Cigoli - Alg 1 - Lez 17 1 / 18

Criterio di risolubilità

Proposizione (criterio di risolubilità)

Siano a, b, c E Z e sia d = MCD(a, b). L'equazione diofantea ax + by = c (1) ha soluzioni MCD(a, b) | c. Se d # 0 ed | c, l'equazione (1) è equivalente all'equazione a'x + b'y = c', (2) dove a' = ald, b' = b/d, c' = c/d. Quest'ultima è detta equazione ridotta e i suoi coefficienti a' e b' sono coprimi.

Dimostrazione del criterio di risolubilità

Come nell'enunciato, poniamo d = MCD(a, b). (=>) Sia (m, n) € Z x Z tale che am+ bn = c. Allora d | am+ bn = c. (=) Supponiamo che d | c. Se d = 0, allora a = b = c = 0 ed ogni coppia (m, n) € Z x Z è soluzione. Cigoli - Alg 1 - Lez 17 2 / 18Sia ora d # 0 e sia (m, n) € Z x Z. Grazie alla legge di cancellazione (valida in Z), si ha che am+ bn = c > a'm+b'n=c', cioè le equazioni (1) e (2) sono equivalenti. Grazie al Lemma precedente, MCD(a', b') = 1. Quindi per l'identità di Bezout esistono m, n E Z tali che a'm+b'n=1. Moltiplicando per c' otteniamo a'mc' + b' nc' = c'. Cioè (mc', nc') è una soluzione dell'equazione (2) e quindi anche dell'equazione (1). In realtà, quando è risolubile, un'equazione diofantea ammette infinite soluzioni, descritte dal teorema seguente.

Teorema sulle soluzioni infinite

Siano a, b, c E Z, con MCD(a, b) = 1. Allora l'equazione diofantea ax + by = c ammette infinite soluzioni, ovvero le coppie (×0 + kb, yo - ka), KEZ, dove (xo, Yo) è una qualunque soluzione dell'equazione. Cigoli - Alg 1 - Lez 17 3 / 18

Dimostrazione del teorema sulle soluzioni infinite

Poiché MCD(a, b) = 1 | c, dalla Proposizione precedente sappiamo che l'equazione ammette almeno una soluzione (x), yo), ricavabile a partire dall'identità di Bézout per a e b. Vk E Z, sostituendo (x, y) = (x0 + kb, yo - ka) nell'equazione vediamo che a(x0 + kb) + b(yo -ka) = ax0 + akb+ byo -bka = axo + byo = c, quindi la coppia (x0 + kb, yo - ka) è soluzione. Viceversa, se (x1, y1) è una soluzione, allora ax1 + by1 = c = ax0 + byo, da cui a(×1-X0)= b(yo-y1). Poiché a | b(yo - y1) e MCD(a, b) = 1, per il Lemma di Euclide a | (yo - y1). Ovvero Ek E Z tale che yo - y1 = ka, da cui y1 = yo - ka . Sostituendo al posto di y1 otteniamo a(x1 - X0) = bka. Se a # 0, semplificando abbiamo ×1 - X0 = bk, ovvero x1 = X0 + kb . Se a = 0, allora b = 0 e il risultato si ottiene in modo analogo. Cigoli - Alg 1 - Lez 17 4 / 18

Esercizi sulle equazioni diofantee

Esercizio: Risolvere 12x + 39y = 15

Se possibile, risolvere l'equazione diofantea 12x +39y = 15.

Soluzione dell'esercizio 12x + 39y = 15

MCD(12,39) = 3 | 15, quindi per il criterio di risolubilità l'equazione ammette soluzioni. Dividiamo per 3 in modo da ottenere l'equazione ridotta: 4x+ 13y = 5. Poiché MCD(4, 13) = 1, quest'ultima equazione è risolubile e le sue soluzioni sono descritte dal Teorema precedente. Ricaviamo l'identità di Bezout attraverso l'algoritmo. In realtà è sufficiente svolgere la prima divisione: 13 = 3 . 4+ 1, da cui 4 . (-3) + 13 . 1 = 1. Moltiplicando per 5 otteniamo 4 . (-15) + 13 .5 = 5. Quindi la coppia (x0, yo) = (-15,5) è una soluzione particolare dell'equazione 4x+ 13y = 5. Tutte le soluzioni sono date da X = X0 + kb = - 15+13k, y = yo -ka=5-4k, KEZ. Queste sono anche tutte le possibili soluzioni dell'equazione 12x +39y = 15, essendo le due equazioni equivalenti. Cigoli - Alg 1 - Lez 17 5 / 18

Esercizio: Indovinello delle taniche di Die Hard

Avendo a disposizione una tanica da 5 galloni, una da 3 ed una fontana, è possibile riempire la prima tanica esattamente con 4 galloni d'acqua?

Soluzione dell'indovinello delle taniche

Indichiamo con x il numero di riempimenti della tanica da 5 galloni e con y il numero di riempimenti della tanica da 3 galloni. Il problema si riduce a trovare una soluzione dell'equazione 5x+3y = 4. Per quanto visto finora, tale equazione è risolubile, dato che MCD(5,3) = 1. L'identità di Bezout si vede a occhio: 5 . (-1) +3 .2 = 1. Moltiplicando per 4 otteniamo 5 . (-4) +3 . 8 = 4, da cui si deduce che la coppia (x0, yo) = (-4,8) è una soluzione particolare dell'equazione. Quindi Vk E Z, anche (-4+3k, 8-5k) è una soluzione. La soluzione proposta nel film è: riempire la tanica da 5, versare 3 galloni in quella da 3, gettare i 3 galloni e versare i restanti 2 nella tanica da 3, riempire la tanica da 5 e usarla per riempire totalmente quella da 3. Nella tanica da 5 rimarranno 4 galloni. In termini algebrici: 4=5-1 = 5- (3-2) =5-(3-(5-3)) =5.2+3.(-2), corrispondente alla soluzione (x, y) = (2, -2), che si ottiene per k = 2. Cigoli - Alg 1 - Lez 17 6 / 18

Esercizio: Banconote da 20 e 50 euro

In quanti modi un cassiere può dare 300 € ad un cliente usando solo banconote da 20 e 50 €? Qual è il numero minimo di banconote che deve usare?

Soluzione dell'esercizio sulle banconote

Siano x ed y i numeri delle banconote da 20 e 50 € usate, rispettivamente. II problema si riduce alla soluzione dell'equazione 20x +50y = 300. Poiché MCD(20,50) = 10 | 300, l'equazione ha soluzioni in Z x Z ed è equivalente all'equazione ridotta 2x +5y = 30. Scriviamo l'identità di Bezout: 2 . (-2) +5 . 1 = 1. Moltiplicando per 30 otteniamo la soluzione particolare (xo, yo) = (-60,30). Tutte le soluzioni sono date da (x, y) =(-60+5k,30-2k), con k E Z. Essendo però x ed y numeri di banconote, abbiamo i vincoli x _ 0, y ≥ 0, da cui segue che 60 < k ≤ 30. Quindi i valori possibili sono k = 12, 13, 14, 15, che corrispondono alle soluzioni (0, 6), (5,4), (10,2), (15,0). Il cassiere ha 4 modi di servire il cliente. Il numero minimo di banconote da usare è 6. Cigoli - Alg 1 - Lez 17 7 / 18

Esercizi aggiuntivi

Se possibile, risolvere in Z x Z le equazioni

1. 15x+20y = 35;
2. 15x +21y = 35.

Esercizio: Sacchetto di biglie

In quanti modi è possibile ottenere un sacchetto del peso di 117 grammi usando biglie da 27 e 21 grammi? Qual è il minimo ed il massimo numero di biglie utilizzabili? Cigoli - Alg 1 - Lez 17 8 / 18

Congruenze lineari

Una congruenza lineare è un'espressione della forma ax =c mod n con a, c E Z, ne N \ {0}. Una sua soluzione è un numero z E Z tale che az = c mod n. Risolvere una congruenza lineare significa trovarne tutte le soluzioni. Due congruenze si dicono equivalenti quando hanno le stesse soluzioni. Spesso le soluzioni si indicano nella forma X=Z mod n, che equivale a dire che x = z + kn per k E Z. Così un solo rappresentante descrive tutte le soluzioni ad esso congruenti modulo n. Notiamo che ax = c mod n > By Ez, c-ax = ny y E Z, ax + ny = C. Quindi la congruenza a sinistra ha soluzioni se e solo se ha soluzioni l'equazione diofantea a destra. Come sappiamo, ciò succede se e solo se d = MCD(a, n) | c. Cigoli - Alg 1 - Lez 17 9 / 18In tal caso, possiamo dividere per d e passare all'equazione ridotta ax + ay = c. A sua volta, quest'ultima e equivalente alla congruenza a d x d c d mod ~ Quindi la congruenza appena scritta è equivalente a quella di partenza.

Osservazione sulle congruenze

Abbiamo definito nella scorsa lezione Z> = {k E Zn | Ba E Zn, k · a = 1}. Perciò k E Z, se e solo se la congruenza kx = 1 mod n ha soluzioni. Ma abbiamo visto che ciò accade se e solo se MCD(k, n) = 1, in accordo con la caratterizzazione data nella scorsa lezione.

Esercizio: Risolvere 5x = 3 mod 10

Risolvere la congruenza 5x = 3 mod 10.

Soluzione dell'esercizio 5x = 3 mod 10

Poiché MCD(5, 10) = 5}3, la congruenza non ha soluzioni. Equivalentemente, l'equazione diofantea associata 5x + 10y = 3 non ha soluzioni. Cigoli - Alg 1 - Lez 17 10 / 18

Esercizio: Risolvere 12x = 15 mod 21

Risolvere la congruenza lineare 12x = 15 mod 21.

Soluzione dell'esercizio 12x = 15 mod 21

MCD(12,21) = 3 | 15, quindi la congruenza ha soluzioni. Innanzitutto semplifichiamo per 3 per ottenere la conrguenza 4x = 5 mod 7. Quest'ultima equivale all'equazione 4 . X = 5 in Z7. Poiché MCD(4,7) = 1, la classe 4 è invertibile in Z7. La sua inversa si trova tramite l'identità di Bezout: 4 . 2+7 . (-1) = 1, da cui 4 = 2 in Z -. Moltiplicando per 2 nell'equazione si ottiene 2 .4 . x = 2.5, cioè x = 3 in Z7, ovvero x = 3 mod 7. Pertanto le soluzioni di 12x = 15 mod 21 sono della forma x = 3+7k con kez. Per scriverle modulo 21, dividiamo k per 3: k = 3q + r con 0 < r < 3. Sosituendo: 3+7k = 3+7(3q+r) =3+21q+7r=21 3+7r. Quindi X =21 3+7r con 0 <r <3. Sostituendo i valori possibili (0, 1,2) di r otteniamo tutte le soluzioni della congruenza di partenza: x =3 mod 21 , x =10 mod 21, X =17 mod 21 . Cigoli - Alg 1 - Lez 17 11 / 18

Sistemi di congruenze lineari

Talvolta può essere richiesto che più congruenze lineari siano verificate contemporaneamente. Consideriamo ad esempio il sistema { ax =b mod n1 a2X = b2 mod n2 Risolverlo significa trovare le soluzioni comuni alle due congruenze. Affinché tali soluzioni esistano, occorre che ogni congruenza sia risolubile, cioè MCD(a1 , n1) | b1 e MCD(a2, n2) | b2. In tal caso, possiamo ridurre il sistema a un sistema del tipo { X= C X = C2 mod n4 mod n'2 per opportuni c1, C2, dove n'; = n¡/MCD(aj, ni). Dalle due equazioni ricaviamo X = C1 + an, ed x = C2 + bn2, da cui c1 + an' = c2 + bn2, ovvero an' - bn2 = C2 - C1. Quest'ultima è un'equazione diofantea nelle incognite a e b, che ha soluzioni se e solo se MCD(n', nh) | (c2 - C1). Risolvendola, se possibile, otteniamo di conseguenza le soluzioni del sistema. Vediamo questo procedimento in un esempio. Cigoli - Alg 1 - Lez 17 12 / 18

Esercizio: Risolvere un sistema di congruenze

Risolvere, se possibile, il sistema di congruenze { 8x = 10 mod 14 15x = 9 mod 24

Soluzione del sistema di congruenze

Semplifichiamo le congruenze dividendo per i rispettivi MCD: mod 7 { 4x =5 5x =3 mod 8 Poiché 4 = 2 € Z- e 5 = 5 € Z8, moltiplicando la prima equazione per 2 e la seconda per 5 si ha { 2 .4x = 2.5 mod 7 5.5x =5.3 mod 8 ovvero X=3 mod 7 X=7 mod 8 Quindi x = 3+7a ed x = 7+8b, da cui 3+7a = 7+8b, cioè 7a- 8b = 4. Non ci resta che cercare le soluzioni di quest'ultima, che esistono perché MCD(7,8) = 1. Identità di Bezout: 7 . (-1) - 8 . (-1) = 1. Moltiplicando per 4 otteniamo la soluzione particolare (ao, bo) = (-4, -4). Tutte le soluzioni sono date da (a, b) = (-4-8k,-4-7k) con kez. Sostituendo, x = 3+7a= 3+7(-4-8k) =3-28-56k =31-56(k+1), cioè x = 31 mod 56 . Cigoli - Alg 1 - Lez 17 13 / 18