dei 100 polli dei 100 polli

Esercitazione N Esercitazione N .4 .4

‹ ‹ Equazioni diofantee Equazioni diofantee lineari lineari

applicazioni elementari pratiche:il problema cinese applicazioni elementari pratiche:il problema cinese

dei 100 polli dei 100 polli

‹ ‹ Relazioni d Relazioni d ’equivalenza ’ equivalenza

‹ ‹ Domande interessanti poste dagli studenti in aula Domande interessanti poste dagli studenti in aula

14 novembre 2006

14 novembre 2006

E

QUAZIONI

D

IOFANTEE LINEARI (= equazioni di I° grado a coefficienti

in Z che vengono risolte in Z)

1 I

NCOGNITA

Esempi 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

NCOGNITE

Esempi 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 DIOFANTEA

ax+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

₀

,y

₀

) è una sua soluzione allora anche (tx

₀

,ty

₀

) al va- riare di t in Z è soluzione ? Sì ! Ma …

D

OMANDA

E’ 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=

₂¹

∉ 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

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^*

P^ROBLEMA 1.Stabilire se e quando ax+by=c ha soluzioni in Z.

R

ISPOSTA

L'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

₀

+by

₀

=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

₀

,y

₀

∈Z tali che d= ax

₀

+by

₀

. 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

₀

, y=my

₀

(o meglio la coppia (mx

₀

,my

₀

)).

Abbiamo risposto anche ad un secondo problema

P

ROBLEMA

2. 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

SEMPI

1) 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

ROBLEMA

3. 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ì f¹(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

SERCIZIO

3.

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.