Algebra e Matematica discreta a.a. 2015/2016 Scuola di ...parmeggi/stat3/INFL1.pdf · G....

G. Parmeggiani, 1/3/2016

Algebra e Matematica discreta a.a. 2015/2016

Scuola di Scienze - Corso di laurea: INFORMATICA

1 / 29

Docenti:parte di Algebra: Gemma Parmeggianiparte di Matematica discreta: Carla De Francesco

orario lezioni:lunedı , martedı , giovedı , venerdıdalle 9.30 alle 11.30

prof.ssa De Francesco: tutti i lunedı ed anchei seguenti 4 venerdı : 4/3, 1/4, 29/4, 20/5

io: le rimanenti lezioni

2 / 29

sospensione didattica (compitino): dal 18 al 22 aprile

date degli appelli al link:informatica.math.unipd.it/laurea/index.html

3 / 29

orario di ricevimento (mio):mercoledı dalle 11.00 alle 12.30venerdı dalle 12.00 alle 13.00

indirizzo: Dipartimento di Matematica (sesto piano)via Trieste 63indirizzo di posta elettronica: [email protected]

materiale didattico alla pagina web:(ATTENZIONE al corso !)http://www.math.unipd.it/ parmeggiesercizi per casa, ESERCIZI TIPO, programma svolto

4 / 29

libro di testo: Geometria analitica con elementi dialgebra lineareMarco Abate e Chiara de FabritiisMc Graw Hill

link alla piattaforma connect:

http://connect.mheducation.com/class/g-parmeggiani-ii-semestre-2015-2016

5 / 29

DIVISIONE NEI NUMERI NATURALI E NEI NUMERIINTERI

Siano

N = l’insieme dei numeri naturali = {0, 1, 2, 3, . . . } e

Z = l’insieme dei numeri interi = {· · · − 3,−2,−1, 0, 1, 2, 3, . . . }.

Divisione in N: Siano a, b ∈ N con b 6= 0. Allora esistono e sonounici due numeri naturali q (detto quoziente) ed r (detto resto) taliche

a = q · b + r con 0 ≤ r < b.

6 / 29

ESEMPI:

per a = 137 e b = 55 si ha q = 2 ed r = 27;

per a = 137 e b = 142 si ha q = 0 ed r = a = 137.

N.B. 1 L’esistenza di q ed r puo essere dimostrata usando il principiodi induzione.

N.B. 2 Che q ed r siano unici significa:

a = q1 · b + r1 con 0 ≤ r1 < b

a = q2 · b + r2 con 0 ≤ r2 < b

=⇒

q1 = q2

r1 = r2

7 / 29

Divisione in Z: Siano a, b ∈ Z con b 6= 0. Allora esistono e sono unicidue numeri interi q (detto quoziente) ed r (detto resto) tali che

a = q · b + r con 0 ≤ r < |b|.

ESEMPI:

per a = 137 e b = −55 si ha q = −2 ed r = 27;

per a = −137 e b = 55 si ha q = −3 ed r = 28;

per a = −137 e b = −55 si ha q = 3 ed r = 28.

N.B. 1 La dimostrazione dell’esistenza di q ed r e simile alla di-mostrazione dell’esistenza di quoziente e resto nella divisione in N.

N.B. 2 Che q ed r sono unici dal momento che si richiede che sia r ≥ 0.

N.B. 3 Se a, b ∈ Z con b 6= 0, allora |a|, |b| ∈ N con |b| 6= 0, ma ilquoziente ed il resto della divisione di a con b non sono i valori assolutidel quoziente ed il resto della divisione di |a| con |b|.

8 / 29

DIVISIBILITA’ NEI NUMERI NATURALI E NEI NUMERIINTERI

Divisibilita in N: Siano a, b ∈ N con b 6= 0. Si dice che b divide a se

a = q · b per un opportuno q ∈ N.

Se b divide a si scrive b|a. Se invece b non divide a, si scrive b 6 |a.

ESEMPI:

6 | 18 perche esiste q ∈ N tale che 18 = q · 6 (si prende q = 3);

4 6 | 18: nella divisione di 18 per 4 c’e un resto r 6= 0 (e r = 2).

9 / 29

N.B. Siano a, b ∈ N con a 6= 0 e b 6= 0. Allora

a|bb|a

}

=⇒ a = b

Divisibilita in Z: Siano a, b ∈ Z con b 6= 0. Si dice che b divide a se

a = q · b per un opportuno q ∈ Z.

b|a. Se invece b non divide a, si scrive b 6 |a.

10 / 29

ESEMPI:

(−6) | 18 perche esiste q ∈ Z tale che 18 = q · (−6) (si prende q = −3);

6 | (−18) perche esiste q ∈ Z tale che −18 = q · 6 (si prende q = −3);

4 6 | (−18): nella divisione di −18 per 4 c’e un resto r 6= 0 (nella divisionedi −18 per 4, dovendo essere r ≥ 0, e q = −5 ed r = 2).

N.B. Siano a, b ∈ Z con a 6= 0 e b 6= 0.

a|bb|a

}

=⇒ a ∈ {b,−b}

11 / 29

MASSIMO COMUN DIVISORE NEI NUMERI NATURALIE NEI NUMERI INTERI

Massimo comun divisore in N: Siano a, b ∈ N non entrambi nulli. Sidice che d ∈ N e un massimo comun divisore di a e b se

1) d |a e d |b (ossia se d e un divisore comune di a e b)

2) se z |a e z |b per qualche z ∈ N, allora z |d

(ossia d e un multiplo di tutti i divisori comuni di a e b).

12 / 29

N.B. 1 In N il massimo comun divisore e unico (ossia, se a, b ∈ N sononon entrambi nulli, e d1, d2 ∈ N sono due divisori comuni di a e b con laproprieta di essere multipli di ogni altro divisore comune di a e b, allorad1 = d2).

Se d e IL massimo comun divisore di a e b (in N) si scrive

d = MCD(a, b).

ESEMPIO: 6 = MCD(12, 18).

N.B. 2 Siano a, b ∈ N non entrambi nulli. Allora

MCD(a, b) = MCD(b, a).

13 / 29

N.B. 3 Siano a, b ∈ N con b 6= 0. Se b|a allora b = MCD(a, b).

In particolare, per ogni b 6= 0 si ha che b = MCD(0, b) = MCD(b, 0).

N.B. 4 Siano a, b ∈ N con b 6= 0. Siano q ed r il quoziente ed il restodella divisione di a per b (con eventualmente r = 0 se b|a):

a = q · b + r con 0 ≤ r < b.

AlloraMCD(a, b) = MCD(b, r).

14 / 29

Massimo comun divisore in Z: Siano a, b ∈ Z non entrambi nulli.Si dice che d ∈ Z e un massimo comun divisore di a e b se

1) d |a e d |b (ossia se d e un divisore comune di a e b)

2) se z |a e z |b per qualche z ∈ Z, allora z |d

(ossia d e un multiplo di tutti i divisori comuni di a e b).

Se d e UN massimo comun divisore di a e b (in Z) si scrive d =MCD(a, b).

ESEMPI:

6 = MCD(12, 18) ed anche −6 = MCD(12, 18) in Z;

6 = MCD(−12, 18) ed anche −6 = MCD(−12, 18) in Z.

15 / 29

N.B. 1 In Z il massimo comun divisore e individuato a meno del segno(ossia, se a, b ∈ Z sono non entrambi nulli, e d1, d2 ∈ Z sono duedivisori comuni di a e b con la proprieta di essere multipli di ogni altrodivisore comune di a e b, allora d1 = d2 oppure d1 = −d2).

N.B. 2 Siano a, b ∈ Z con b 6= 0. Siano q ed r il quoziente ed il restodella divisione di a per b (con eventualmente r = 0 se b|a):

a = q · b + r con 0 ≤ r < |b|.

AlloraMCD(a, b) = MCD(b, r).

N.B. 3 Siano a, b ∈ Z non entrambi nulli. Allora

MCD(a, b) = MCD(−a, b) = MCD(a,−b) = MCD(−a,−b).

16 / 29

CALCOLO DEL MASSIMO COMUN DIVISORE NEI NUMERINATURALI E NEI NUMERI INTERI

Calcolo del MCD in N: Dati a, b ∈ N con a 6= 0 e b 6= 0, descriviamoun algoritmo (detto algoritmo di Euclide ) che permette di calcolareMCD(a, b). Esso consiste in una sequenza di divisioni successive:

10passaggio: si divide a per b : esistono q1, r1 ∈ N tali chea = b · q1 + r1 con 0 ≤ r1 < b

MCD(a, b) = MCD(b, r1)

se r1 = 0 allora MCD(b, r1) = MCD(b, 0) = b

e l’algoritmo si ferma;

se r1 6= 0 l’algoritmo continua.

17 / 29

20passaggio: se r1 6= 0, si divide b per r1 :esistono q2, r2 ∈ N tali cheb = r1 · q2 + r2 con 0 ≤ r2 < r1

MCD(b, r1) = MCD(r1, r2)

se r2 = 0 allora MCD(r1, r2) = MCD(r1, 0) = r1e l’algoritmo si ferma;


18 / 29

30passaggio: se r2 6= 0, si divide r1 per r2 :esistono q3, r3 ∈ N tali cher1 = r2 · q3 + r3 con 0 ≤ r3 < r2

MCD(r1, r2) = MCD(r2, r3)

se r3 = 0 allora MCD(r2, r3) = MCD(r2, 0) = r2e l’algoritmo si ferma;


. . . . . . . . . . . . . . . . . . . . . . . .

19 / 29

k-esimo passaggio: se rk−1 6= 0, si divide rk−2 per rk−1 :esistono qk , rk ∈ N tali cherk−2 = rk−1 · qk + rk con 0 ≤ rk < rk−1

MCD(rk−2, rk−1) = MCD(rk−1, rk)

se rk = 0 allora MCD(rk−1, rk) = MCD(rk−1, 0) = rk−1

e l’algoritmo si ferma;

se rk 6= 0 l’algoritmo continua.

. . . . . . . . . . . . . . . . . . . . . . . .

Concludendo, il massimo comun divisore MCD(a, b) e l’ultimoresto non nullo della sequenza di divisioni successive.

20 / 29

ESEMPIO: Calcoliamo MCD(2420, 1386):

10passaggio: dividiamo a = 2420 per b = 1386 :2420 = 1386 · 1 + 1034 (q1 = 1, r1 = 1034 < 1386)

1034 6= 0 =⇒ l’algoritmo continua.

20passaggio: dividiamo b = 1386 per r1 = 1034 :1386 = 1034 · 1 + 352 (q2 = 1, r2 = 352 < 1034)


30passaggio: dividiamo r1 = 1034 per r2 = 352 :1034 = 352 · 2 + 330 (q3 = 2, r3 = 330)


21 / 29




r5 = 0 e r4 6= 0 =⇒ r4 = MCD(a, b)

e l’algoritmo si ferma: MCD(2420, 1386) = 22.

22 / 29

Calcolo del MCD in Z: Siano a, b ∈ Z non entrambi nulli. Percalcolare MCD(a, b) si puo procedere in uno dei due seguenti modi:

10 modo:

- calcolare |a|, |b| ∈ N,- calcolare MCD(|a|, |b|) = d ∈ N,- osservare che allora d e −d sono i due MCD(a, b) in Z.

20 modo:

- usare l’algoritmo di Euclide in Z: si eseguono divisioni successive in Z

(attenzione: tutti i resti devono essere non negativi !)

e l’ultimo resto non nullo nella sequenza di queste divisioni e il massimocomun divisore positivo di a e b in Z.

23 / 29

ESEMPIO: Calcoliamo MCD(−274, 110) nei due modi:

10 modo: a = −274 e b = 110 per cui |a| = 274 e |b| = 110.

274 = 110 · 2 + 54 (q1 = 2, r1 = 54)

110 = 54 · 2 + 2 (q2 = 2, r2 = 2)

54 = 2 · 27 + 0 (q3 = 27, r3 = 0)

Dunque r2 = 2 = MCD(|a|, |b|) e 2 e −2 sono i due massimi comundivisori di a = −274 e b = 110 in Z.

24 / 29

20 modo: a = −274 e b = 110 (i resti sono non negativi !)

−274 = 110 · (−3) + 56 (q1 = −3, r1 = 56)

110 = 56 · 1 + 54 (q2 = 1, r2 = 54)

56 = 54 · 1 + 2 (q3 = 1, r3 = 2)

54 = 2 · 27 + 0 (q4 = 27 r4 = 0)

Dunque r3 = 2 = MCD(a, b) e 2 e −2 sono i due massimi comundivisori di a = −274 e b = 110 in Z.

25 / 29

NUMERI PRIMI NEI NUMERI NATURALI E NEI NUMERIINTERI

Numeri primi in N: Un numero naturale p ∈ N e detto un numeroprimo se

- p 6= 0, 1,- se x ∈ N e tale che x |p allora x ∈ {1, p}.

ESEMPI: 2 e un numero primo, mentre 4 non lo e.

26 / 29

Numeri primi in Z: Un numero intero p ∈ Z e detto un numeroprimo se

- p 6= 0, 1,−1,- se x ∈ Z e tale che x |p allora x ∈ {1,−1, p,−p}.

ESEMPI: 2 e −2 sono numeri primi.

27 / 29

TEOREMA FONDAMENTALE DELL’ARITMETICA

Ogni numero intero e prodotto di numeri primi in modo unico a menodell’ordine e del segno:

n = p1 · p2 · · · · · pr per ogni n ∈ Z

dove p1,p2, . . . pr sono numeri primi (non necessariamente distinti).

28 / 29

Siano a, b ∈ Z . Allora se

a = (−1)α · pα11 · · · · · pαk

k· p

αk+1

k+1 · · · · · pαn

n

b = (−1)β · pβ11 · · · · · pβk

k· q

βk+1

k+1 · · · · · qβm

m

dove α, β ∈ {0, 1}, αi , βi ∈ N e pi , qi sono numeri primi allora

MCD(a, b) = (−1)δ · pδ11 · · · · · pδk

k

dove dove δ ∈ {0, 1} e δi = min{αi , βi}.

29 / 29

Algebra e Matematica discreta a.a. 2015/2016 Scuola di ...parmeggi/stat3/INFL1.pdf · G....

Documents

Transcript of Algebra e Matematica discreta a.a. 2015/2016 Scuola di ...parmeggi/stat3/INFL1.pdf · G....