Esercitazione N Esercitazione N .4 .4
Equazioni diofantee Equazioni diofantee lineari lineari
applicazioni elementari pratiche:
applicazioni elementari pratiche:
il problema cinese dei 100 polli il problema cinese dei 100 polli
Relazioni d Relazioni d ’ ’ equivalenza equivalenza
Domande interessanti poste dagli Domande interessanti poste dagli studenti in aula
studenti in aula
14 novembre 2006
14 novembre 2006
E
QUAZIONID
IOFANTEE LINEARI(= equazioni di I° grado a coefficienti in Z che vengono risolte in Z)
1 I
NCOGNITAEsempi a) 3x=4 non ha sol. in Z
b) 5x=10 ha unica sol. in Z, x= 10/5 =2
Quindi ax=b con a, b ∈ Z , a≠0 ha un’unica soluzione in Z (x= b/a) se e solo se a|b ( a divide b)
Altrimenti non ci sono soluzioni in Z
2 I
NCOGNITEEsempi a) 4x+6y=3 non ha sol. in Z:comunque si sostituiscano x e y con due interi il I° membro è pari, il secondo è dispari.
Si noti che in R l’equazione ha infinite soluzioni, basta assegnare ad x un generico valore reale t e ricavare il corrispondente
y= 6 4t 3 −
, con t∈R .
b) 3x+6y=18 ha soluzioni intere,ad esempio (4,1), (-6,6),(10,-2).
L’
EQUAZIONE DIOFANTEAax+by=0
Affrontiamo ora lo studio dell’equazione ax+by=0, detta equazione omogenea associata all’equazione ax+by=c (c=0) .
L’equazione ax+by=0 ha sempre la soluzione (0,0).
Se (x
0,y
0) è una sua soluzione allora anche (tx
0,ty
0) al va- riare di t in Z è soluzione ? Sì ! Ma …
D
OMANDAE’ vero che le soluzioni intere dell’equazione li- neare omogenea 4x-6y=0 sono tutte del tipo (6t,4t) al va- riare di t∈Z ?
x=6 y=4
soddisfa l’equazione (corrisponde a t=1)x=6⋅2 y=4⋅2
soddisfa l’equazione (corrisponde a t=2)x=6⋅3 y=4⋅3
soddisfa l’equazione (corrisponde a t=3) etc. quindi :x=6t y=4t , t∈Z
soddisfa l’equazione. Ma attenzione !¾ anche (3,2) è soluzione, ma non c’è nessun valore in-
tero di t che consenta di ottenere (3,2) = (6t,4t),
perché dovrebbe essere 3= 6t e 2 =4t , ma dalla pri-
ma segue t=
12∉ Z.
Quindi le coppie (6t,4t) al variare di t∈Z sono sì soluzione dell’equazione 4x-6y=0 ma non sono TUTTE le infinite soluzioni !
¾ Ma se l’equazione fosse stata scritta così 2x-3y=0 sarebbe stato corretto dire che tutte le soluzioni so- no x= 3t, y=2t , t∈Z ! Perché ? In virtù della
¾
Proprietà *
se a divide bc, e se a è primo con b, allora a divide c
¾ Osservo che da 2x=3y posso ricavare che:
3 divide 2⋅x , 3 è primo con 2 ( non hanno fattori co muni ) , allora 3 divide x, e quindi x=3t da cui
2(3t)=3y cioé y=2t).
Invece da 4x=6y ricavo che:
6 divide 4⋅x e stop ! 2 è fattore a comune tra 4 e 6 ! Abbiamo visto prima cosa può succedere:4⋅3 = 6⋅2
Morale …
4 non divide né 6 né 2
Tutte le soluzioni di ax+by=0, nel ns. caso 4x-6y=0 si trovano così :
• M.C.D.(4,6)=2
• dividiamo per 2 l’equazione 4x-6y=0, otteniamo l’equazione equivalente (con le stesse soluzioni) 2x-3y=0, i cui coefficienti sono primi tra loro
• la soluzione generale in Z di 2x-3y=0 è
"scambiando in croce": x=3t,y=2t al variare di t in Z,(o equivalentemente) l’insieme S={(3t,2t)| t ∈Z}.
PROSPETTO
Dobbiamo capire ancora la parte destra dello schema.
ax+by=c a, b ∈ Z
*, c∈ Z
c=0 → "omogenea" c≠0 → "non omogenea"
infinite soluzioni in Z • nessuna soluzione in Z
• infinite soluzioni in Z
EQUAZIONE LINEARE NON OMOGENEA ax+by=c, CON a,b,c∈Z*
PROBLEMA 1. Stabilire se e quando ax+by=c ha soluzioni in Z.
R
ISPOSTAL'equazione ax+by=c, con a,b,c∈Z
*ha soluzioni in Z ⇔ M.C.D. (a,b) divide c.
Dim.Se esiste la soluzione intera (x
0,y
0) allora si ha
ax
0+by
0=c. Se d è il M.C.D. (a,b) allora a=dr, b=ds, quindi sostituendo : c= (dr)x
0+(ds)y
0= d(rx
0+sy
0), che ci dice d divide c.
Viceversa supponiamo che d divida c, ossia dm=c.
Dalla proprietà del M.C.D.(a,b) si sa che esistono x
0,y
0∈Z tali che d= ax
0+by
0. Quindi si ha :
c = dm= (ax
0+by
0)m = a(mx
0)+b(my
0)
Questo ci dice che l’equazione diofantea ax+by=c ha la so- luzione x= mx
0, y=my
0(o meglio la coppia (mx
0,my
0)).
Abbiamo risposto anche ad un secondo problema
P
ROBLEMA2. Nel caso in cui ax+by=c abbia soluzioni inte- re trovare una soluzione.
R
ISPOSTA. Troviamo prima una soluzione di ax+by=d,
d= M.C.D. (a,b), (ad esempio)con l'algoritmo di Eucli-
de e poi la moltiplichiamo per c/d.
E
SEMPI1) 21x+15y=14 ha soluzioni in Z ?
M.C.D.(21,15)=3, 3 non divide 14⇒NON ci sono sol. inZ.
2) 21x+15y=6 ha soluzioni in Z ?
3 divide 6 ⇒ S
Ì, ci sono soluzioni in Z.
Troviamo una
soluzione intera di 21x+15y=6.
Prima troviamo una soluzione di 21x+15y=3 Si vede facilmente che x= -2 , y= 3 va bene.
Ora c=6,d=3 quindi c/d=2 e perciò moltiplichiamo la coppia trovata ( -2, 3) per 2 e otteniamo (-4,6) , soluzione di 21x+15y=6.
Resta l’ultimo problema :
P
ROBLEMA3. Determinare le infinite soluzioni di ax+by=c
R
ISPOSTA. Sommiamo ad una sua soluzione tutte le soluzioni dell’equazione omogenea associata.
( per la dim. Cfr. dispense G.Niesi scorso anno).
E
SEMPIO: Quali sono le infinite soluzioni di 21x+15y=6 ?
Determiniamo le infinite soluzioni dell’eq.omog.associata 21x+15y=0. Semplifichiamo per 3: 7x+5y=0. Ora i coef- ficienti sono primi fra loro e quindi le soluzioni sono (5t,-7t) al variare di t in Z.
Una soluzione particolare di 21x+15y=6 è (-4,6)
(
SI PUÒ TROVARE ANCHE CON L’
ALGORITMO EUCLIDEO)
allora la soluzione generale di 21x+15y=6 è (-4,6) + (5t,-7t)
La soluzione generale di 21x+15y=6 è (-4+5t,6-7t) al variare di t in Z
Sommiamo ordinatamente le componenti
ESERCIZIO 1.
Il problema dei 100 polli di Chang Chhiu-Chien
Se un gallo costa 5 monete, una gallina 3 monete e con una moneta si possono comprare 3 pulcini, quanti galli, galline e pulcini si possono comprare con 100 monete , vo- lendo comprare in tutto 100 polli ?
Indichiamo : x= numero dei galli y= numero delle galline z= numero dei pulcini
Il quesito si traduce nel sistema
⎪⎩
⎪ ⎨
⎧
= +
+
= + +
100 3 z
3y 1 5x
100 z
y x
⇒
⎪⎩
⎪ ⎨
⎧
= +
+
=
100 y)
- x - 100 3 (
3y 1 5x
y - x - 100 z
⇒ ⎩ ⎨ ⎧
= +
=
200 8y
14x
y - x - 100 z
.
La seconda equazione è una diofantea lineare che possia- mo semplificare in 7x+4y=100.
Una soluzione particolare si vede essere (0,25).
L’eq.omog.ass. 7x+4y=0 ha i coefficienti che sono primi fra loro, perciò le sue infinite soluzioni sono ( 4t,-7t) al variare di t∈Z, e di conseguenza la soluzione generale dell’equazione 14x+8y=200 è
(0,25)+ ( 4t,-7t) = (4t, 25-7t) al variare di t∈Z , quindi la soluzione del sistema è
x= 4t, y= 25-7t, z= 75+7t al variare di t∈Z.
Chang Chhiu-Chien,nel suo trattato di ″Matematica classi- ca″ (~250 d.C. ) dà le risposte
Infatti occorre mettere la condizione di positività ! 4t > 0; 25 - 7t > 0; 75 + 3t > 0
x=4 y=18 z=78 x=8 y=11 z=81 x=12 y=4 z=84
-25<t<3+ 4/7 t>0
Quindi t=1,2,3 : si ottengono le soluzioni di Chang !
ESERCIZIO 2.
Sulle funzioni Sia f:ZxZ→Z la funzione definita da f(x,y)=6x-15y.
a) Determinare f
-1(0) e f
-1(12).
b) Stabilire se f è iniettiva, surgettiva.
a)
f-1(0)={(x,y)∈ZxZ | f(x,y)=0}= {(x,y)∈ZxZ | 6x-15y=0}.Semplificata per 3 l'equazione si riduce a 2x-5y=0, ossia 2x=5y, i cui coefficienti sono primi fra loro.
Ora si può procedere come sempre: 2 non divide 5 , quindi 2 divide y, ossia y= 2t , da cui segue x=5t , con t∈Z.
Si ottiene f-1(0) = {(5t,2t)| t∈Z}.
f-1(12)={(x,y)∈ZxZ | f(x,y)=12}={(x,y)∈ZxZ| 6x-15y=12}.
Una soluzione particolare di 6x-15y=12 è (-3,-2).
La soluzione generale è (-3,-2)+(5t,2t)=(-3+5t,-2+2t),t∈Z Si ottiene f-1(12) ={(-3+5t,-2+2t)| t∈Z}.
b) Si può avere f-1(♣)= {(x,y)∈ZxZ | 6x-15y=♣} = ∅ ? 6x-15y=c ha soluzioni in Z ⇔ M.C.D.(6,15) divide c
M.C.D.(6,15)=3,ad es.non ci sono soluzioni se c=2.Così f1(2)=∅
ed f NON è surgettiva.
Da a) f NON è iniettiva: f-1(0) ha infiniti elementi
( (0,0)≠(5,2) ma f(0,0)=f(5,2)= 0 ).
E
SERCIZIO3.
Relazioni binarie – relazioni d’equivalenza La relazione disegnata è di equivalenza ?
R
ICORDIAMO CHE:
Una relazione binaria su un insieme A è un sottoin- sieme del prodotto cartesiano AxA. Dati x, y elementi di A diciamo che x è in relazione con y e scriviamo x∼y (opp. x R y) se (x,y)∈AxA.
A = {0,1,2}
R= { (0,0), (0,1), (1,0), (1,1), (2,2) }
• Una relazione ∼ su A è di equivalenza se è
¾
riflessiva: x ∼x , ∀ x∈A
¾
simmetrica: x ∼y ⇒ y∼x , ∀ x,y∈A
¾
transitiva: x ∼y e y∼z ⇒ x∼z , ∀ x,y,z∈A
Dal disegno si 'leggono' la riflessiva e la simmetrica.
Rispetto alla bisettrice del I° quadrante …
A = {0,1,2} , R= { (0,0), (0,1), (1,0), (1,1), (2,2) }
Transitiva: sì ! verificarlo ! 0∼0, 1∼1, 2∼2 : rifl. sì
0∼1 ⇒ 1∼0 : simm. sì
OSSERVAZIONI EDOMANDE INTERESSANTI
POSTE IN AULA DAGLI STUDENTI DURANTE L' ESERCITAZIONE
PROPRIETA’ DI PAG.3
QUALE CORRELAZIONE C’È TRA LA PROPRIETÀ DI PAG.3 E IL TEOREMA
FONDAMENTALE DELL’ARITMETICA ? PER PROVARE LA PROPRIETÀ SI UTI LIZZA IL TEOREMA O VICEVERSA ?
La proprietà * di pag.3 afferma che
In Z se a divide bc, e se a è primo con b, allora a divide c
Il teorema fondamentale dell’aritmetica afferma che:
Ogni numero intero maggiore di 1 si fattorizza in modo unico (a me- no dell’ordine) in un numero finito di primi.
La proprietà * si prova facendo uso della divisione e dell’identità di BeZout così:
Se a è primo con b, ossia se il M.C.D.(a,b) = 1, allora sappiamo che esi- stono due interi m, n tali che 1=am+bn; moltiplicando per c si ha
c= cam+cbn. Ma per ipotesi a divide bc, quindi ak=bc e sostituendo si ha c= cam+akn= a(cm+kn). Dunque a divide c, che è la tesi.
Un interessante COROLLARIO della proprietà * è il seguente :
Se in Z un numero primo divide un prodotto, allora divide almeno uno dei fattori.
Infatti se il numero primo p divide ab si ha: M.C.D.(p,a)=1 oppure M.C.D.(p,a)=p.
Nel primo caso usiamo la proprietà * e allora p divide b.Nel secondo caso p divide a, per definizione di M.C.D.
Questo COROLLARIO viene usato nel corso della dimostrazione del teorema fondamentale dell’aritmetica.
