Appunti di Matematica Discreta

(1)

Appunti di Matematica Discreta

Giuseppe Sollazzo

(2)

Indice

1 Numeri naturali 4

1.1 Generalit`a . . . 4

1.2 Insiemi generici di naturali . . . 5

1.3 Operazioni sui naturali . . . 5

1.3.1 Addizione . . . 5

1.3.2 Moltiplicazione . . . 5

1.3.3 Propriet`a dell’addizione e della moltiplicazione . . . 6

1.3.4 Elevamento a potenza . . . 6 1.3.5 Sottrazione . . . 7 1.3.6 Divisione . . . 7 1.4 Insiemi ordinati . . . 9 1.5 Propriet`a di N . . . 9 1.6 Relazione d’ordine . . . 10

1.6.1 Divisibilit`a e relazione d’ordine . . . 10

2 Numeri primi 11 2.1 Massimo Comune Divisore . . . 11

2.1.1 Propriet`a del Massimo Comune Divisore . . . 11

2.1.2 Algoritmo di Euclide o delle divisioni successive . . . 12

3 Numeri interi 15 3.1 Generalit`a . . . 15

3.2 Operazioni sui numeri interi . . . 15

3.2.1 Addizione . . . 15 3.2.2 Sottrazione . . . 16 3.2.3 Propriet`a dell’addizione . . . 16 3.2.4 Gruppi . . . 16 3.2.5 Moltiplicazione . . . 17 3.3 Anelli . . . 18

3.3.1 Propriet`a degli anelli . . . 18

3.3.2 Divisori . . . 19

3.3.3 Invertibilit`a . . . 19

3.3.4 Dominio di integrit`a, Corpo, Campo . . . 19

3.3.5 M.C.D. in Z . . . 19

3.4 Equazioni . . . 19

3.4.1 Teoremi sulle equazioni in Z . . . 20

(3)

INDICE 3

4 Congruenze 23

4.1 Definizione di congruenza . . . 23

4.2 Propriet`a delle congruenze . . . 23

4.3 Equivalenze . . . 24

4.4 Classi di Congruenza Modulo n . . . 25

4.5 Altre propriet`a delle congruenze . . . 26

4.5.1 Propriet`a che coinvolgono il modulo . . . 26

4.5.2 Propriet`a di una congruenza di modulo fissato . . . 26

4.6 Somma e prodotto in Zn . . . 26

4.7 L’anello Zn . . . 27

4.8 Congruenze di primo grado a un’incognita . . . 27

4.9 La funzione di Eulero . . . 29

5 Numeri razionali 30 5.1 Generalit`a . . . 30

5.2 Somma e prodotto in Q . . . 30

5.3 Il campo Q . . . 31

6 Altri insiemi numerici 32 6.1 L’insieme R . . . 32

6.2 L’insieme C . . . 32

7 Alcune strutture fondamentali 33 7.1 Generalit`a . . . 33

7.1.1 Propriet`a . . . 33

7.2 Il gruppo (Kn_{, +) . . . .} ₃₃

7.2.1 Somma di n-ple . . . 34

7.2.2 Prodotto per scalari . . . 34

8 Matrici 35 8.1 Generalit`a . . . 35

8.2 Somma di matrici . . . 35

8.3 Prodotto di un numero per una matrice . . . 36

8.4 Prodotto righe per colonne di matrici . . . 36

8.4.1 Propriet`a del prodotto tra matrici . . . 36

8.5 Matrice trasposta . . . 36

(4)

Capitolo 1

Nozioni fondamentali sui

numeri naturali

1.1 Generalit`

a

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

Questo insieme presenta alcune propriet`a fondamentali, dette Assiomi di

Peano

1. Ogni numero ∈ N ha un solo successivo 2. Lo zero `e un numero

3. Lo zero non `e successivo di alcun numero

4. Ogni numero naturale non nullo `e successivo solo di un altro numero naturale

5. Vale il Principio di induzione

Principio di induzione 1 Supponiamo di avere una proposizione P sui

natu-rali. Allora: a) P(0) `e vera

b) P(n) `e vera ⇒ P(n+1) `e vera

Per il principio di induzione se a) e b) sono vere, allora P `e vera per tutti i numeri naturali.

(5)

1.2. INSIEMI GENERICI DI NATURALI 5 - Nota - Sarebbe più corretto enunciare il principio di induzione definendo nel caso b) “se P è vera per n, allora P è vera per il successore di n” dato che non si conosce ancora il significato di addizione.

Inoltre, nella sua forma generalizzata, il principio di induzione dice che se sup-poniamo P(n) vera per n ≥ m allora P `e vera ∀ n ≥ m.

1.2 Insiemi generici di naturali

Il discorso appena concluso vale per ogni insieme che sia un sottoinsieme dei naturali. Le operazioni possono essere generalizzate e definite come applicazioni

che da 2 elementi di un generico insieme A restituiscono un elemento dello stes-so insieme A.

f : A × A → A cio`e f (a, b) = c

Dato quindi un insieme possiamo definire quali sono le operazioni possibili su questo insieme. Definiamo, cio`e, una struttura algebrica:

ad esempio, (A, ∗) `e una struttura algebrica che rappresenta un insieme A su cui `e definita la moltiplicazione. L’insieme A si dice sostegno della struttura1_.

Una struttura con un’operazione si dice commutativa se l’operazione definita gode di tale propriet`a:

(A, ∗) `e commutativa se ∀a, b ∈ Aa ∗ b = b ∗ a

Per indicare una struttura commutativa basta scrivere (A, +), cio`e usiamo il “linguaggio dell’addizione” (notazione additiva in opposizione a quella molti-plicativa2_).

1.3 Operazioni sui naturali

1.3.1 Addizione

Dati a, b ∈ N si scrive a + b = c

c si definisce somma di a e b.

Possiamo dare una definizione ricorsiva dell’addizione:

a + b =

½

a se b = 0 (a + d) + 1 se b = d + 1

Quindi la somma di due numeri consiste nel contare, a partire dal primo ad-dendo, tante unit`a quante sono le unit`a del secondo addendo

1.3.2 Moltiplicazione

Dati a, b ∈ N si scrive a · b = c

c si definisce prodotto di a e b.

1_{Per rappresentare una struttura algebrica basta indicare il suo sostegno, quando `e evidente}

dal contesto che si sta parlando di una struttura algebrica

2_{Quando si parla in notazione additiva di elemento neutro ci si riferisce allo 0, e si parla}

(6)

6 CAPITOLO 1. NUMERI NATURALI

Possiamo dare una definizione ricorsiva della moltiplicazione:

a · b =    0 se b = 0 a se b = 1 a · d + a se b = d + 1

Quindi il prodotto di due numeri consiste nel sommare a se stesso il primo fattore (a), tante volte quante sono le unit`a del secondo fattore

1.3.3 Propriet`

a dell’addizione e della moltiplicazione

∀a, b, c ∈ N valgono le seguenti propriet`a: • ELEMENTO NEUTRO

Esiste ed `e unico l’elemento neutro della somma: a + 0 = a Esiste ed `e unico l’elemento neutro del prodotto: a · 1 = a

• PROPRIET `A ASSOCIATIVA (a + b) + c = a + (b + c) (a · b) · c = a · (b · c) • PROPRIET `A COMMUTATIVA a + b = b + a a · b = b · a • LEGGE DI ANNULLAMENTO a + b = 0 sse a = b = 0 a · b = 0 sse a = 0 ∨ b = 0 • LEGGE DI CANCELLAZIONE a + b = a + c sse b = c a · b = a · c sse b = c, con a 6= 0

• PROPRIET `A DISTRIBUTIVA della somma rispetto al prodotto (a + b) · c = a · c + b · c

1.3.4 Elevamento a potenza

∀a, b ∈ Nsi definisce elevamento a potenza: an₌

½

1 se n = 0

(7)

1.3. OPERAZIONI SUI NATURALI 7 Propriet`a dell’elevamento a potenza

1. an_{· a}m_{= a}n+m

2. (an₎m_{= a}n·m

3. am_{· b}m_{= (a · b)}m

1.3.5 Sottrazione

∀a ≥ b, a − b = c. c si dice “differenza” di a e b ed indica quel numero tale che a = b + c.

La sottrazione cos`ı definita non `e un’operazione, in quanto non si pu`o effettuare su ogni coppia di valori a, b ∈ n

Propriet`a della sottrazione 1. a − b = 0 ⇐⇒ a = b

2. se b ≥ c, (a + b) − c = a + (b − c) ⇒ (a + b) − b = a3

3. a − b = (a + c) − (b + c) sse b ≥ c, altrimenti a − b = (a − c) − (b − c)

1.3.6 Divisione

Enunciamo il

Teorema della divisione 2 Siano a, b ∈ n e sia b 6= 0. Esistono e sono unici

q, r ∈ N tali che a = b · q + r, 0 ≤ r < b4

Dimostrazione Occorre 1)dimostrare l’esistenza di q, r; 2)dimostrarne l’unicit`a. 1. Dimostrazione dell’esistenza di q ed r.

Si presentano i seguenti casi:

(a) se a < b otteniamo q = 0, r = a5

(b) se a = b otteniamo q = 1, r = 0

(c) se a > b sappiamo che ∃c1∈ N, c16= 0, tale che a = b + c1. Allora:

• se c1< b allora q = 1, r = c1

• se c1= b allora q = 2, r = 0

• se c1> b allora ∃c2∈ N tale che c1= b + c2e quindi a = 2b + c2.

A questo punto, iteriamo il procedimento finch`e non giungiamo a una soluzione.

Il passo generale `e:

se ci−1> b allora ∃ci ∈ N tale che ci−1 = b + ci, a = i · b + ci.

Quindi:

3_{Non `e una vera implicazione; la freccia indica che da quelle premesse possiamo ricavare}

l’espressione (a + b) − b = a

4_{Neanche la divisione `e un’operazione in quanto associa coppie di naturali ad altre coppie}

di naturali, cio`e N × N → N × N

(8)

– se ci< b allora q = i, r = ci

– se ci= b allora q = i + 1, r = 0

– se ci= b allora si ripete.

Ovviamente riesco a dimostrare l’esistenza se ad un certo punto il procedimento si ferma e trovo il valore di c.6

Perch`e questo procedimento funziona? Abbiamo costruito un insieme di valori a, c1, c2, . . . in cui si ha sempre a < c1< c2< . . .. `E un insieme di

naturali, che sicuramente ammette un minimo cs tale che a = b · s + cs.

csnon pu`o essere maggiore di b perch`e altrimenti potremmo scrivere cs=

b + cs+1mentre per definizione si ha che cs> cs+1, un assurdo logico dato

che cs`e il minimo. Perci`o

• se cs< b allora q = s, r = cs

• se cs= b allora q = s + 1, r = 0

2. Dimostrazione dell’unicit`a di q ed r.

Supponiamo per assurdo che q ed r non siano unici. Allora avremmo:

a = q · b + r, 0 ≤ r < b a = q1· b + r1, 0 ≤ r1< b

Dobbiamo dimostrare che q = q1 e che r = r17

Supponiamo r ≥ r1. Avremo la seguente uguaglianza: b · q + r = b · q1+ r1.

Ad entrambi i membri sottraiamo r1 ottenendo una nuova uguaglianza:

b · q + r − r1= b · q1

Essendo r ≥ r1 per definizione di maggiore sappiamo che b · q1 ≥ b · q8

dunque q1≥ q.

Ad entrambi i membri dell’equazione precedente sottraiamo b · q:

b · q + (r − r1) − b · q = b · q1− b · q cio

r − r1= b · (q1− q) per cui se q1= q sarebbe r − r1= 0 cio`e r = r1il che

sarebbe assurdo perch`e vorrebbe dire q1≥ q, e quindi r = b · (q1− q) + r1)

e quindi sarebbe r > b in contrasto con l’ipotesi avanzata.

Per cui dati a, b 6= 0 si ha che q `e il pi`u grande naturale tale che a ≥

q · b, a ≤ (q + 1) · b

Divisibilit`a

Dati b, a ∈ N, b 6= 0, diciamo che b | a cio`e che b `e un divisiore di a se esiste

c ∈ N tale che a = b · c9_.

Enunciamo alcune propriet`a:

• ∀a : a | a in quanto a = 1 · a10

• ∀a : 1 | a11

6_{Ovviamente, questo prima o poi succede :)} 7_{Qui vale la propriet`}_{a di tricotomia tra r e r}

1 e tra q e q1 8_{Perch`e b · q = r − r}₁

9_{Notare che b e c sono entrambi divisori di a e che b deve essere diverso da 0 perch`e 0 `e}

un “multiplo” di tutti i numeri in quanto risulta ∀b : 0 = b · 0

(9)

1.4. INSIEMI ORDINATI 9

• Ogni numero a ∈ N ha almeno 2 divisori impropri : a e 112

• b | a ∧ b divisore proprio di a ⇒ b < a13

1.4 Insiemi ordinati

Una struttura definita come (A, ≤) serve a indicare un insieme ordinato. L’in-sieme N è naturalmente ordinato. Ciò significa che l’elemento a è pi`u piccolo dell’elemento b se nel contare a viene prima di b e si scrive a < b oppure a ≤ b. Per generalizzare questo ragionamento scriviamo:

a ≤ b ⇐⇒ ∃c ∈ N tale che b = a + c

A questo punto enunciamo il

Teorema del minimo 3 Sia ® 6= H ⊆ N. Allora H ammette minimo.

Dimostrazione Per l’assioma della scelta, possiamo sempre scegliere un elemen-to a dall’insieme H. Allora:

• Se 0 ∈ H, allora 0 `e il minimo.

• Se 0 /∈ H, prendo 1. Se 1 ∈ H, allora 1 `e il minimo. • . . .

• Se a − 1 ∈ H, allora a - 1 `e il minimo. Altrimenti il minimo `e a.

1.5 Propriet`

a di N

• PROPRIET `A RIFLESSIVA ∀a ∈ N, a ≤ a14 • PROPRIET `A ANTISIMMETRICA ∀a, b ∈ N, a ≤ b ∧ b ≤ a ⇐⇒ a = b15 • PROPRIET `A TRANSITIVA ∀a, b, c ∈ N, a ≤ b ∧ b ≤ c ⇒ a ≤ c • PROPRIET `A DI TRICOTOMIA ∀a, b ∈ N, a ≤ b ∧ a 6= b ⇒ a < b16

• ORDINAMENTO DELLA SOMMA a ≤ b ⇒ a + c ≤ b + c

• ORDINAMENTO DEL PRODOTTO a ≤ b ⇒ a · c ≤ b · c

12_{ne consegue che 1 non ha divisori propri perch`e se 1 = b · c, b 6= 1 ∧ c 6= 1 ⇒ b > 1 ∨ b = 0}

il che contrasta con le ipotesi

13_{Significa che ogni divisore proprio `e strettamente minore del numero di cui `e divisore. Ad}

esempio, scriviamo a = b · c, b 6= 1, c 6= 0, b 6= a. Possiamo scrivere b = a + d, d 6= 0 perch`e

b 6= a. Potendo scrivere a = (a + d) · c otteniamo a = ac + dc che implica a > a (assurdo).

14_{Perch`e a = a + b se b = 0}

15_{Dato che b=a+c, a=b+d, dunque a=a+(c+d) e ci`}_{o implica c+d=0 che `e vero sse c=d=0,}

per cui a=b

16_{per esempio, 5 < 7 perch`e 5 ≤ 7 ∧ 5 6= 7. Nella propriet`}_{a di tricotomia, ovviamente, solo}

(10)

1.6 Relazione d’ordine

Se abbiamo un insieme A e una relazione R tra gli elementi di A, diciamo che A `e ordinato secondo la relazione R se per tale relazione valgono le propriet`a:

• riflessiva: ∀a ∈ A, aRa

• antisimmetrica: ∀a, b ∈ A, aRb ∧ bRa ⇒ a = b • transitiva: ∀a, b, c ∈ A, aRb ∧ bRc ⇒ aRc

Se vale anche la propriet`a di tricotomia, allora la relazione si dice totale.17

Per indicare che su un insieme vale una relazione d’ordine possiamo scrivere (A, R) oppure(A, ≤)

1.6.1 Divisibilit`

a e relazione d’ordine

La divisibilità è una relazione d’ordine parziale, in quanto “a è divisore di b se

a | b”

(N, |) `e un insieme ordinato perch`e:

• vale la propriet`a riflessiva ∀a ∈ N, a | a

• vale la propriet`a antisimmetrica ∀a, b, c ∈ N, a | b ∧ b | a ⇐⇒ a = b • vale la propriet`a transitiva ∀a, b, c ∈ N, a | b ∧ b | c ⇒ a | c18

• non vale la propriet`a di tricotomia

La divisibilit`a `e compatibile con il prodotto ma non con la somma.

17_{ad esempio, il principio di induzione non `e una relazione d’ordine totale dato che valgono}

solo 3 propriet`a

18_{dato che possiamo scrivere b = a · d e c = b · h ottendendo c = a · d · h = a · (d · h) per cui}

(11)

Capitolo 2

Numeri primi

p si dice numero primo se p > 1 ∧ p non ha divisori propri.

Teorema 4 Ogni numero o `e primo o `e prodotto di potenze di numeri primi.

Cio`e a = pr1

1 ·pr22· · · prnn dove p1, p2, . . . , pnsono numeri primi, e r1, r2, . . . , rn≥

1.

Dimostrazione di Euclide Supponiamo di avere un numero qualsiasi: tale nu-mero può avere dei divisori propri o può non averli. Se li ha, ne ha almeno 2. Il più piccolo di tali divisori è un numero primo, perchè se cos`ı non fosse tale numero avrebbe a sua volta 2 divisori, più piccoli di quelli che avevamo all’inizio.

Se risulta p1< p2< · · · < pn−1< pn abbiamo la Fattorizzazione standard di un

numero naturale.

2.1 Massimo Comune Divisore

Dati a, b ∈ N il pi`u grande dei divisori comuni di a e b si chiama Massimo Comune Divisore di a e b e si scrive d = M CD(a, b) oppure d = (a, b).

Se M CD(a, b) = 1 allora a e b sono copr`ımi o primi fra loro1_.

2.1.1 Propriet`

a del Massimo Comune Divisore

1. Se a | b allora M CD(a, b) = a3

2. Se a = b · q + t allora tutti i divisori comuni della coppia (a,b) sono divisori comuni della coppia (b,r). In particolare M CD(a, b) = M CD(b, r)

1_{Su n numeri la definizione di MCD `e analoga; ovviamente se 2 di questi n numeri hanno}

M CD = 1 allora il MCD degli n numeri `e 1

2_{In quanto possiamo scrivere b = a · h e c = a · k da cui otteniamo b + c = a · (h + k) per}

cui a | (b + c)

3_{da cui discende: M CD(a, a) = a, M CD(a, 0) = a, M CD(a, 1) = 1}

(12)

12 CAPITOLO 2. NUMERI PRIMI

2.1.2 Algoritmo di Euclide o delle divisioni successive

Per trovare il Massimo Comune Divisore di due numeri esiste un procedimento ideato da Euclide che consiste nell’effettuare delle divisioni successive tra varie coppie di numeri. Dati a, b ∈ N, a 6= b, a > b, 0 ≤ r1< b scriviamo a = b · q1+ r1. • Se r1= 0 allora M CD(a, b) = b • Se r16= 04, abbiamo b = r1· q2+ r2, 0 ≤ r2< r1. – Se r2= 0 . . .

• all’i-esimo passo avremo ri= ri+1· qi+2+ ri+2, 0 ≤ ri+2< ri+1.

Quando trovo rn= 0 allora M CD(a, b) = rn−1.

In sintesi ad ogni iterazione del procedimento dividiamo il resto precedente per il resto attuale, finch`e da tali divisioni non otteniamo un resto nullo.

Dimostrazione. Dobbiamo dimostrare 1) che il procedimento finisce, 2) che troviamo un resto nullo, 3) rn−1= M CD(a, b).

Procediamo cos`ı. Prima di tutto abbiamo un insieme a, b, r1, . . . , ri, . . . che `e

sicuramente un insieme ordinato, visto l’algoritmo con cui viene costruito. Si ha cio`e a > b > r1> · · · > ri> · · ·.

1. Tale insieme, per il teorema del minimo, ammette sempre un minimo: quindi ad un certo punto l’algoritmo termina la sua esecuzione.

2. È scontato che il resto sarà 0 perchè in caso contrario l’algoritmo non terminerebbe, in contrasto con quanto abbiamo appena affermato. 3. Essendo M CD(a, 0) = a è ovvio che se rn= 0 avremo M CD(rn−1, rn) =

rn−15.

Euclide si occupava delle misurazioni dei segmenti. Ecco qual è il significato del suo algoritmo: se r = 0 le due grandezze considerate sono commensurabili, cioè sono entrambe misurabili dall’unità di misura individuata nel loro Massimo Comune Divisore.

NOTA

-• Se M CD(a, b) = d allora a = d · a0_{∧ b = d · b}0 _{dove (a}0_{, b) = 1}6

• (a, b) = 1 ∧ a | b · c ⇒ a | c

Teorema 5 Siano a, b, d ∈ N. Allora sono equivalenti le seguenti affermazioni:

1. d | a ∧ d | b, dato un qualunque c divisore comune di a e b risulta che c | d.

4_{Essendo in N, r} 1> 0

5_{A questo proposito ricorda la regola dei divisori comuni enunciata precedentemente:}

(a, b) = (rn−2, rn−1) = (rn−1, rn)

(13)

2.1. MASSIMO COMUNE DIVISORE 13

2. d = M CD(a, b)

Dimostrazione Dobbiamo dimostrare sia che l’affermazione 1) implica l’affer-mazione 2), sia che l’afferl’affer-mazione 2) implica l’afferl’affer-mazione 1).

• Poniamo M CD(a, b) = d0_{. Dobbiamo dimostrare che d = d}0_.

Per l’ipotesi 1, sappiamo che d0 _{| d, per cui d}0 _{≤ d. Essendo per`o}

d0 _{= M CD(a, b) dovrebbe essere necessariamente d ≤ d}0_{. Perci`o per}

la propriet`a antisimmetrica sappiamo che d = d0_.

• La dimostrazione `e immediata in quanto sappiamo che (a, b) = (b, r) = · · · = (rn−2, rn−1) = (rn−1, rn) = rn−1

Corollario 6 ∀a, b, k ∈ N, se (a, k) = 17 _{e k | a · b allora k | b.}

Dimostrazione Consideriamo i due prodotti k · b e a · b. Risulta che k | k · b ma per ipotesi sappiamo anche che k | a·b. Se dimostriamo che M CD(k ·b, a·b) = b allora abbiamo dimostrato il teorema.

Poniamo M CD(k · b, a · b) = d: dato che b `e un divisore comune tra k · b e a · b, risulta che b | d cio`e possiamo scrivere d = b · h.

Perch`e sia dimostrato il teorema dobbiamo dimostrare che h = 1.

Poniamo k · b = d · m e a · b = d · n. Se sostituiamo la d con h · b otteniamo le seguenti uguaglianze

k · b = b · h · m che per la legge di cancellazione diventa k = h · m a · b = b · h · n che per la legge di cancellazione diventa a = h · n

Essendo M CD(a, k) = 1 per ipotesi, necessariamente risulta che h = 1 perch`e

h | (a, k)

Primo teorema di Euclide 7 Sia p un numero primo. Se p | a · b allora

p | a ∨ p | b.

Dimostrazione Poich`e p `e primo, se p non dividesse a risulterebbe (p, a) = 1. Ma allora, per il teorema precedente, sarebbe p | b.8

Con i teoremi appena enunciati siamo in grado di dimostrare il Teorema Fon-damentale dell’Aritmetica, che afferma che ogni numero è rappresentabile come prodotto di numeri primi, affermando inoltre che tale fattorizzazione è unica. Si ricordi, a questo proposito, che il Massimo Comune Divisore di due numeri si può calcolare anche moltiplicando i fattori comuni della fattorizzazione standard dei due numeri.

Secondo teorema di Euclide 8 Esistono infiniti numeri primi.

7_{Cio`e se a e k sono coprimi}

8_{Si deduce in maniera immediata che se p `e primo e p | a · b dove a e b sono primi, allora}

(14)

14 CAPITOLO 2. NUMERI PRIMI

Dimostrazione9_{Supponiamo di conoscere i primi n numeri primi:}

p1, p2. . . pn.

Dobbiamo dimostrare che ce n’`e uno pi`u grande, p, di quelli considerati. Definiamo la successione dei numeri in modo tale che risulti p1< p2< · · · < pn.

Consideriamo il numero N = p1·p2·· · · pn. Tale numero `e sicuramente maggiore

di pn.

Consideriamo anche il numero M = N + 1. Quindi:

• se M `e primo abbiamo dimostrato il teorema perch`e M > pn

• se M non `e primo, possiamo scrivere M = p · R dove p `e il pi`u basso numero primo della fattorizzazione di M.

Dobbiamo dimostrare che p > pn10.

Poniamo p = pj. Allora p | N in quanto pj | N . Inoltre pM e quindi

p | (M − N ) = p | 1; ciò è assurdo perchè per definizione di numero primo,

p `e necessariamente diverso da 1.

9_{Esistono varie dimostrazioni. Noi useremo quella di Euclide.} 10_{Che in questo caso equivale a dimostrare p 6= p}

(15)

Capitolo 3

Numeri interi

3.1 Generalit`

a

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

Z `e il prodotto cartesiano tra l’insieme N e l’insieme composto dai segni + e -,

in cui +0 = −0 = 0

Terminologia

• I numeri con lo stesso segno si dicono concordi, quelli di segno diverso si

dicono discordi.

• Per valore assoluto di un numero si intende il numero stesso privato del

segno.

• I numeri strettamente maggiori di 0 si chiamano Positivi, e il loro insieme

si indica con il simbolo Z+_.1 _{Invece i numeri non negativi sono dati da}

Z+_{∪ {0}}

• I numeri strettamente minori di 0 si chiamano Negativi, e il loro insieme

si indica con il simbolo Z−_{. Invece i numeri non positivi sono dati da}

Z−_{∪ {0}}

• I numeri +n e −n si dicono opposti: si tratta di numeri con lo stesso

valore assoluto ma con segno diverso.2

3.2 Operazioni sui numeri interi

3.2.1 Addizione

∀a, b, c ∈ Z si scrive a+b = c. Il numero c `e la somma di a, b ottenuta come segue:

1_{Con tale insieme, di solito, i matematici identificano l’insieme dei naturali} 2_{Osserva che −(−a) = a}

(16)

16 CAPITOLO 3. NUMERI INTERI

1. se a e b sono concordi, c `e concorde con essi ed ha per valore assoluto la somma dei loro moduli: | a + b |=| a | + | b |

2. se a e b sono discordi e | a |≥| b |, c `e concorde con a e | c |=| a | − | b | 3. se a e b sono discordi e | a |<| b |, c `e concorde con b e | c |=| b | − | a |

3.2.2 Sottrazione

∀a, b, c ∈ Z si scrive a − b = c. Il numero c `e cos`ı calcolato: c = a + (−b).3

3.2.3 Propriet`

a dell’addizione

∀a, b, c ∈ Z valgono le seguenti propriet`a:

• PROPRIET `A ASSOCIATIVA: (a + b) + c = a + (b + c)

• ESISTENZA DELL’ELEMENTO NEUTRO: a + 0 = a

• ESISTENZA DELL’OPPOSTO: ∀a ∈ Z∃ − a ∈ Z tale che a + (−a) = 0 • PROPRIET `A COMMUTATIVA: a + b = b + a

• UNICIT `A DELL’ELEMENTO NEUTRO: L’elemento neutro `e unico

• UNICIT `A DELL’OPPOSTO: L’opposto `e unico

• OPPOSTO DI UNA SOMMA: L’opposto di una somma `e uguale alla

somma degli opposti: −(a + b) = −a − b

• LEGGE DI CANCELLAZIONE: a + b = a + c sse b = c

3.2.4 Gruppi

Sia (G, ·) una struttura algebrica. Enunciamo le seguenti propriet`a:4

1. ASSOCIATIVIT `A: ∀a, b, c ∈ G : (a · b) · c = a · (b · c)

2. ESISTENZA DELL’ELEMENTO NEUTRO: ∃e ∈ G, ∀a ∈ G : a · e =

e · a = a

3. ESISTENZA DELL’INVERSO: ∀a ∈ G∃a−1_{∈ G : a · a}−1_{= a}−1_{· a = e}

4. COMMUTATIVIT `A: ∀a, b ∈ G : a · b = b · a. Se vale la proprietà 1) (G, ·) è un semigruppo. Se valgono le proprietà 1) e 2) (G, ·) è un monoide. Se valgono le proprietà 1), 2) e 3) (G, ·) è un gruppo.

Se valgono le propriet`a 1), 2), 3) e 4) (G, ·) `e un gruppo commutativo o abeliano.

3_{Cio`e la somma di a con l’opposto di b}

(17)

3.2. OPERAZIONI SUI NUMERI INTERI 17 Sia (G, ·) un gruppo (o monoide), risulta:

1. L’elemento neutro `e unico 2. L’inverso di un elemento `e unico

3. L’inverso di un prodotto `e uguale al prodotto degli inversi con l’ordine scambiato: ∀a, b ∈ G : (a · b)−1 _{= b}−1_{· a}−1

4. Vale la legge di cancellazione a destra e a sinistra: se a · b = c · b allora a = c;

se b · a = b · c allora a = c.

Dimostrazioni delle propriet`a appena enunciate5

1. Unicit`a dell’elemento neutro: supponiamo che l’elemento neutro non sia unico: e 6= e0_{. Allora:}

a · e = e · a∀a; in particolare per a = e0_{: e}0_{· e = e · e}0_{= e}0

a · e0_{= e}0_{· a∀a; in particolare per a = e : e · e}0_{= e}0_{· e = e}

e quindi:

e · e0_{= e}0_{, e · e}0_{= e per cui e = e}0_.

2. Unicit`a dell’inverso: supponiamo che l’inverso non sia unico: a−1_{, b.}

Allora:

a · a−1_{= a}−1_{· a = e}

a · b = b · a = e;

scriviamo b = b · e = b · a · a−1 _{= (b · a) · a}−1 _{da cui:}

e = e · a−1_{⇒ a}−1_{= b}

3. L’inverso di un prodotto `e uguale al prodotto degli inversi con ordine invertito: cio`e a · b · b−1_{· a}−1_{= e}6

per la propriet`a associativa abbiamo a · b · (b−1_{· a}−1_{) = (a · b · b}−1_{) · a}−1₌

[a · (b · b−1_{)] · a}−1_{= (a · e) · a}−1_{= a · a}−1_{= e}

4. Legge di cancellazione: abbiamo a · b = c · b.

Moltiplichiamo entrambi i membri per b−1 _{e applichiamo la propriet`a}

as-sociativa: a · (b · b−1_{) = c · (b · b}−1₎

quindi a · e = c · e ⇒ a = c In Z vale l’ordinamento:

a ≤ b sse ∃c ∈ Z, c non negativo, tale che b = a + c. Da questa affermazione

consegue che tutti i positivi sono maggiori dei negativi, e che lo zero `e maggiore di tutti i negativi e minore di tutti i positivi. L’ordinamento in Z `e totale.

3.2.5 Moltiplicazione

∀a, b ∈ Z, definiamo prodotto di a e b il numero c tale che a · b = c determinato

come segue:

(18)

a) a,b concordi: c è positivo, | c |=| a | · | b | b) a,b discordi: c è negativo, | c |=| a | · | b | Proprietà della moltiplicazione

∀a, b, c ∈ Z valgono le seguenti propriet`a:

• PROPRIET `A ASSOCIATIVA: (a · b) · c = a · (b · c)

• ESISTENZA DELL’ELEMENTO NEUTRO: ∃1 ∈ Z tale che a · 1 = a • LEGGE DI ANNULLAMENTO DEL PRODOTTO: a · b = 0 ⇐⇒ a =

0 ∨ b = 0

• LEGGE DI CANCELLAZIONE: a · b = a · c, a 6= 0 ⇒ b = c • PROPRIET `A COMMUTATIVA: a · b = b · a

• PROPRIET `A DISTRIBUTIVA DELLA SOMMA RISPETTO AL PRODOT-TO: (a + b) · c = a · c + b · c

3.3 Anelli

(A, +, ·) `e un anello se:

1. (A, +) `e un gruppo commutativo; 2. (A, ·) `e un semigruppo;7

3. vale la propriet`a distributiva della somma rispetto al prodotto a sinistra ((a + b) · c = a · c + b · c) e a destra (c · (a + b) = c · a + c · b).

3.3.1 Propriet`

a degli anelli

1. ∀a ∈ A : a · 0A= 0A· a = 0A

2. ∀a ∈ A : (−a) · b = a · (−b) = −(a · b) Dimostrazione delle propriet`a

1. a · 0A= a · (0A+ 0A) = a · 0A+ a · 0A. Essendo un elemento dell’anello,

esiste l’opposto −(a · 0A)

Quindi a · 0A+ (−a · 0A) = a · 0A+ a · 0A+ (−a · 0A) cio`e

a · 0A− a · 0A= a · 0A+ a · 0A− a · 0A.

Per cui 0A = a · 0A+ (a · 0A− a · 0A) cio`e 0A = a · 0A+ 0A e quindi

a · 0A= 0A

2. Dobbiamo dimostrare che a · b + (−a) · b = 0A. Applichiamo la propriet`a

distributiva a destra:

a · b + (−a) · b = (a − a) · b che significa 0A· b = 0A

(19)

3.4. EQUAZIONI 19

3.3.2 Divisori

Prima di tutto definiamo A∗ _{l’anello A ad esclusione dell’elemento nullo, cio`e:}

A∗_{= A − 0} A.

Allora :

∀b ∈ A∗_{, b | a se ∃c ∈ A tale che a = b · c.}

Per quanto riguarda i divisori dello 0, per gli anelli c’`e una definizione parti-colare:

∀b, c ∈ A∗_{, b · c = 0 allora b | 0 ∧ c | 0, con b 6= 0 ∧ c 6= 0.}

3.3.3 Invertibilit`

a

Definiamo l’anello con unit`a quell’anello in cui esiste l’elemento neutro per l’op-erazione definita dal segno · e indichiamo tale elemento con 1A. La definizione

di invertibilit`a in un anello commutativo `e la seguente:

a ∈ A `e invertibile se ∃a−1_{∈ A tale che a · a}−1_{= 1} A.

3.3.4 Dominio di integrit`

a, Corpo, Campo

(A, +, ·) `e un Dominio di integrit`a se non contiene divisori dello 0A.

(A, +, ·) `e un Corpo se (A∗_{, ·) `e un gruppo.}

(A, +, ·) `e un Campo se `e un corpo commutativo.

(A, ·) non può essere un gruppo perchè lo 0 non è invertibile in un anello. Z non può essere un corpo o un campo perchè Z∗ _{non è un gruppo.}

3.3.5 M.C.D. in Z

La definizione di più grande dei divisori comuni potrebbe non andare bene perchè il teorema di unicità del MCD non sarebbe più verificato. Per cui potrem-mo dire che il MCD di due numeri in Z è quel numero che in potrem-modulo è il più grande dei divisori comuni, cioè ammettiamo l’esistenza di due MCD +d e −d.

3.4 Equazioni

Si definisce equazione8_{di almeno due incognite un’uguaglianza del tipo ax+by =}

0 con a, b ∈ Z.9_.

8_{Le uguaglianze si dividono in identit`}_{a che sono sempre vere (es. 2 = 1 + 1) ed equazioni,}

che sono vere solo per determinati valori (es. 3x = 0 vera solo per x = 0)

9_{Come si vedr`}_{a, ci sono equazioni che non hanno soluzioni negli interi. Ad esempio, 2x +}

3y = 0 avrebbe come soluzione y = −2

(20)

Teorema 1 Scriviamo a0_{x + b}0_{y = a con a, b ∈ Z.}

Se (a0_{, b}0_{) = d, a}0_{= d · aeb}0_{= d · b allora tutte le soluzioni intere sono date da:}

½

x = b · t

y = −a · t ∀t ∈ Z

Dimostrazione Se d = (a0_{, b}0_{) allora ax + by = 0 `e equivalente a a}0_{x + b}0_{y = 0.}

Allora dobbiamo dimostrare: 1. che ci sono delle soluzioni:

ax + by ⇒ ax = −by cio`e a | −by10_{. Essendo inoltre (a, b) = 1 : a | y cio`e}

∃t ∈ Z tale che y = a · t.

Sostituendo nell’equazione precedente si ha ax = −bat con a, b non en-trambi uguali a 0. Possiamo quindi applicare la legge di cancellazione, ottenendo x = −bt c.v.d.

2. che per qualunque t la coppia `e una soluzione:

dobbiamo dimostrare che a0_{(−bt) + b}0_{(at) = 0. Infatti si ha a}0_{(−bt) +}

b0_{(at) = da(−bt) + db(at) = d(−abt + bat) = d · 0 = 0}

3. che non esistono altre soluzioni oltre quelle date dal sistema precedente: dobbiamo quindi dimostrare che se la coppia x1, y1 `e una soluzione (cio`e

risulta che a0_x

1+ b0y1= 0 allora esiste un intero t tale che

½

x1= −b · t

y1= a · t ∀t ∈ Z

Infatti `e a0_x

1+ b0y1= 0 ossia d(ax1+ by1= 0, cio`e ancora ax1+ by1= 0

per cui risulta ax1= −by1e quindi a | −by1.

Poich`e (a, b) = 1 allora per uno dei teoremi del MCD risulter`a che a | y1

cio`e che esiste un intero t tale che y1 = at. Sostituendo nell’equazione

precedente otteniamo a(x1+ bt) = 0. Poich`e a 6= 0 si ha x1+ bt = 0 cio`e

x1= −bt.

3.4.1 Teoremi sulle equazioni in Z

Teorema 2 Siano a, b, d ∈ Z non nulli. Sono equivalenti:

1. d = a, b

2. d `e il minimo tra gli interi positivi della forma ax + by con x, y ∈ Z.

esempio: nell’equazione 6x + 10y 2 `e il minimo intero che possa essere

espresso in tale forma perch`e l’equazione non sar`a mai uguale a 1.

Corollario (1) 3 Siano a, b, d ∈ Z e sia d = (a, b). Allora l’equazione ax+by =

d ha sempre soluzioni intere.

Corollario (2) 4 L’equazione ax + by = 1 ha soluzioni intere SSE (a, b) = 1.

(21)

3.4. EQUAZIONI 21 Corollario (3) 5 Se (a, b) = 1, l’equazione ax + by = c ha sempre soluzioni

intere.

Corollario (4) 6 L’equazione ax+by = c ha soluzioni intere SSE M CD(a, b) |

c.

esempio: L’equazione 6x + 10y = 3 non ha soluzioni intere.

Teorema 7 Siano a0_{, b}0_{, c}0_{∈ Z. Se (a}0_{, b}0_{) = d, a}0_{= da, b}0 _{= db e se d | c}0 _allora

le soluzioni intere dell’equazione a0_{x + b}0_{y = c}0 _{sono tutte e sole le coppie di}

interi: ½

x = x0+ bt

y = y0− at ∀t ∈ Z

dove x0, y0 `e una soluzione particolare dell’equazione (cio`e a0x0+ b0y0= c0)11.

3.4.2 Metodi di risoluzione delle equazioni in Z

I teoremi appena enunciati ci possono guidare nella ricerca di una soluzione, potendoci ad esempio dire in partenza se un’equazione non ha soluzioni. Per trovare tali soluzioni ci sono due metodi che vanno usati a seconda dei casi (sostanzialmente in base alla grandezza dei coefficienti coinvolti).

Metodo di Eulero

Si basa sull’osservazione che conoscendo una soluzione particolare tutte le soluzioni sono note e dello stesso tipo.

Il metodo di Eulero afferma che data un’equazione, esistono sempre due soluzioni intere x1, y1 e x2, y2tali che 0 ≤ x1≤ |b| e 0 ≤ y2≤ |a|.

Ora, se dividiamo l’intero x0 del sistema precedente per b, otteniamo x0 =

q · b + r, 0 ≤ r ≤ |b|. Se poniamo t = −q nello stesso sistema, otteniamo x = x0− qb = r < |b|12. Tale soluzione `e ovviamente unica.

Il metodo di Eulero consiste nel risolvere l’equazione rispetto all’incognita che ha il coefficiente minore (in modulo). Supponiamo sia x, otterremmo x = c−by_a . Prendiamo y = 0, 1, . . . , b − 1, avremo una sola soluzione in cui il valore di x sar`a intero.

Lo svantaggio di questo metodo `e che per valori di a e b molto grandi costringe ad eseguire molti calcoli.

Metodo di riduzione (Autori vari)

Meno semplice del metodo di Eulero, si basa sull’osservazione che se uno dei coefficienti, per esempio a, divide c, allora una delle soluzioni `e x = c

a, y = 013.

In particolare, se M CD(a, b) | c allora x = c d.

Il metodo consiste nel trovare a partire dall’equazione data un’equazione con uno dei coefficienti che divide il termine noto e quindi attraverso opportune considerazioni ricavare la soluzione dell’equazione data.

Tale metodo `e un’applicazione dell’algoritmo euclideo per la ricerca del MCD.

11_{Quindi basta trovare una soluzione particolare per trovarle tutte.}

12_{Strettamente minore in quanto il resto della divisione intera `e per ovvi motivi strettamente}

minore del divisore.

(22)

Supponiamo a > 1, b > 1 (se cos`ı non fosse basterebbe porre −y al posto di y). L’algoritmo di Euclide si applica ai coefficienti a,b facendo le seguenti posizioni: 1. Abbiamo ax + by = c. Da a = q1b + r1 otteniamo (per sostituzione)

b(q1x + y) + r1x = c.

Poniamo t1= q1x + y otteniamo bt1+ r1x = c.

2. Abbiamo bt1+ r1x = c. Da b = q2r1+ r2 otteniamo (per sostituzione)

r1(q2t1+ x) + r2t1= c.

Poniamo t2= q2t1+ x otteniamo r1t2+ r2t1= c.

3. Abbiamo r1t2+ r2t1= c. Da r1= q3r2+ r3 otteniamo (per sostituzione)

r2(q3t2+ t1) + r3t2= c.

Poniamo t3= q3t2+ t1otteniamo r2t3+ r3t2= c.

4. · · · ·

5. Alla fine avremo rn−1tn+ rntn−1= c dove rn= 0 e rn−1= M CD(a, b).

Allora, se rn−1non divide c l’equazione non ha soluzione.

Altrimenti una soluzione dell’equazione rn−1tn+rntn−1= c `e tn= 0, tn−1= _rc_n.

Per sostituzione si ottengono il valore tn−2. Iterando tale procedimento a un

(23)

Capitolo 4

Congruenze

4.1 Definizione di congruenza

Fissato n ∈ Z, due interi si dicono congruenti modulo n e si scrive a ≡n b se

n | (a − b) cioè se la loro differenza è un multiplo di n. Se ciò non è vero, i due

numeri si dicono incongrui.

4.2 Propriet`

a delle congruenze

1. a ≡nb ⇐⇒ a ≡−nb

2. PROPRIET `A FONDAMENTALE: Sono equivalenti: (i) a ≡nb

(ii) a e b diviso n danno lo stesso resto Dimostrazione della propriet`a (ii)

1. Dimostrazione che (i) ⇒ (ii)

n | (a − b) cio`e a − b = h · n. Possiamo dividere a e b per n:

otteniamo a = q1n + r e b = q2n + r1.

Dimostrare la propriet`a equivale dunque a dimostrare che r e r2 sono

uguali, 0 ≤ r < n, 0 ≤ r1< n.

Scriviamo l’equazione a − b = h · n nella forma a = h · n + b e sostituiamo la b: otteniamo a = h · n + q2· n + r1 che possiamo anche scrivere come

a = (n + q2) · n + r1.

Possiamo affermare che (n+q2)·n e r1sono quoziente e resto della divisione

di a per n quindi, essendo per definizione unici, abbiamo dimostrato che

r = r1.

2. Dimostrazione che (ii) ⇒ (i)

Tale dimostrazione `e immediata perch`e se dividiamo a e b per n otteniamo lo stesso resto:

a − b = (q1− q2) · n cio`e n | (a − b) c.v.d.

(24)

24 CAPITOLO 4. CONGRUENZE

1. RIFLESSIVA ∀a ∈ Z : a ≡na

2. SIMMETRICA ∀a, b ∈ Z : a ≡nb ⇐⇒ b ≡na

3. TRANSITIVA ∀a, b, c ∈ Z : a ≡nb ∧ b ≡na ⇒ a ≡nc

4. COMPATIBILIT `A CON SOMMA E PRODOTTO

∀a, b, c, d ∈ Z, a ≡n b ∧ c ≡nd : (a + c) ≡n (b + d) ∧ (a · c) ≡n(b · d).

Dimostrazione della propriet`a 4

1. Dimostrazione che vale la compatibilit`a con la somma

Possiamo scrivere a, b, c, d come risultato di una divisione per n, ottenendo: (i) a = h · n + r

(ii) b = k · n + r (iii) c = h1· n + r1

(iv) d = k1· n + r1

con 0 ≤ r < n, 0 ≤ r1< n.

Allora riscriviamo le uguaglianze della propriet`a usando questi risultati:

a + c = (h + h1)n + r + r1

b + d = (k + k1)n + r + r1

cio`e dalla definizione di divisore e di congruenza abbiamo:

(a + c) ≡n(r + r1) e (b + d) ≡n (r + r1) in quanto a + c − (r + r1) `e multiplo

di n.

Applicando la propriet`a transitiva alle due uguaglianze ottenute, otteni-amo (a + c) ≡n(b + d).

2. Dimostrazione che vale la compatibilit`a con la somma

Anche qui seguiamo un procedimento analogo: scriviamo a·c = A·n+r·r1

e b · d = B · n + r · r1.

Otteniamo cos`ı le seguenti congruenze:

(a · c) ≡n (r · r1) e (b · d) ≡n (r · r1) da cui otteniamo per la propriet`a

transitiva: (a · c) ≡n(r · r1)

4.3 Equivalenze

L’equivalenza `e denotata dal seguente simbolo: ≡. Dati un insieme A e una relazione R, la relazione si dice relazione di equivalenza se valgono le pro-priet`a:

1. RIFLESSIVA: ∀a ∈ A : aRa

2. SIMMETRICA: ∀a, b ∈ A : aRb ⇐⇒ bRa 3. TRANSITIVA: ∀a, b, c ∈ A : aRb ∧ bRc ⇒ aRc

Si definisce Classe di Equivalenza ([a] l’insieme cos`ı costituito:

{x ∈ A | xRa}, ∀a. Si tratta cio`e di ogni sottoinsieme di A formato da elementi

(25)

4.4. CLASSI DI CONGRUENZA MODULO N 25 Si definisce Insieme quoziente modulo ' l’insieme di tutte le classi di equivalenza di A. Ovvero, l’insieme, appartenente a una partizione di A, che ha per elementi le classi di equivalenza di A.1

4.4 Classi di Congruenza Modulo n

Le classe di congruenza modulo n sono gli insiemi di interi costituiti da numeri congruenti modulo n.

Ognuna di queste classi `e indicata dal simbolo [a]/≡ oppure [a]/≡noppure [a]/n

oppure semplicemente [a].

L’insieme di tali classi `e detto Insieme Quoziente e si indica con Zn.

Se n = 0, a ≡n b sse la loro differenza 0, cio`e se i due numeri sono uguali.

Quindi una congruenza modulo 0, in realt`a un’uguaglianza.

Se n = 1 si ha una sola classe di congruenza che è costituita da tutto Z perchè 1 è divisore di tutti gli interi.

Supponiamo quindi n ≥ 2. Poich`e l’insieme quoziente Zn `e una partizione di Z

allora:

a) Ogni classe di congruenza `e non vuota

b) Due classi diverse non hanno elementi in comune c) Ogni intero sta in una sola classe di congruenza

Per la proprietà fondamentale delle congruenze, una classe contiene solo el-ementi che divisi per n danno lo stesso resto (più il resto stesso). Di solito è quindi proprio il resto che viene scelto come rappresentante, come conseguenza del fatto che due resti diversi sono sempre incongrui. Quindi le classi di con-gruenza modulo n, sono tante quanti sono i resti: esattamente n. Tali classi si chiamano classi di resti o classi di residui modulo n.

Per esempio: Zn= {[0], [1], . . . , [r], . . . , [n − 1]}; cos`ı si indica il fatto che i resti

della divisione di un intero per n sono tutti e soli gli interi r tali che 0 ≤ r < n.

Se A `e un insieme di numeri, a ∈ A allora:

• con a + 1 si intende l’insieme di numeri ottenuto sommando a, a tutti gli

elementi di A

• con a ∗ 1 si intende l’insieme di numeri ottenuto moltiplicando a, a tutti

gli elementi di A

• · · ·

Quindi per Zn:

0 = {m ∈ Z | m = pn∀p ∈ Z} = nZ

1_{Una partizione di A `e una classe di sottoinsiemi di A tale che: 1)Ogni insieme non `e vuoto,}

(26)

1 = {m ∈ Z | m = pn + 1∀p ∈ Z} = 1 + nZ

• · · ·

n-1 = {m ∈ Z | m = pn + n − 1∀p ∈ Z} = n − 1 + nZ

4.5 Altre propriet`

a delle congruenze

4.5.1 Propriet`

a che coinvolgono il modulo

1. a ≡nb ⇐⇒ ac ≡ncbc

2. ac ≡nbc ∧ M CD(c, n) = d ⇒ a ≡n d b

3. a ≡mnb ⇒ a ≡mb ∧ a ≡nb

4. Per l’implicazione inversa della 3) occorre una condizione aggiuntiva, cio`e:

a ≡m∧a ≡n b ∧ M CD(m, n) = 1 ⇒ a ≡mnb

4.5.2 Propriet`

a di una congruenza di modulo fissato

1. ac ≡nbc ∧ M CD(c, n) = d ⇒ a ≡n d b

2. a ≡nb ⇒ am≡nbm

3. a ≡nb, c ≡nd ⇒ ax + cy ≡nbx + dy∀x, y ∈ Z

4. a ≡nb ⇒ f (a) ≡n f (b)∀f polinomio a coefficienti interi

Dalla 4) discendono numerose proprietà quali le regole di divisibilità per 3 e per 11. Ad esempio, sappiamo che un numero è divisibile per 11 se la differenza tra la somma delle cifre pari e la somma delle cifre dispari è 0, 11 o un suo multiplo. Allora questa verifica si effettua partendo dal presupposto che un numero naturale scritto in base 10 è una somma di potenze di 10 con un loro coefficiente: esempio 436 = 6 · 100_{+ 3 · 10}1_{+ 4 · 10}2_.

Allora un numero a pu`o essere cos`ı descritto: a = an· 10n+ · · · + a1· 10 + a0.

Sappiamo che 10 ≡11−1 possiamo scrivere:

an· 10n+ · · · + a1· 10 + a0≡11an· (−1)n+ · · · + a1· (−1) + a0

Il secondo termine della congruenza indica che le cifre pari sono positive e quelle dispari negative: la loro differenza, dunque, dev’essere 0 o multiplo di 11.

4.6 Somma e prodotto in Z

n

Possiamo definire due operazioni all’interno dell’insieme quoziente Zn:

1. La somma, definita come funzione + : Zn× Zn → Zn si indica come

[a] + [b] = [c] = [a + b] ed `e la classe che ha come rappresentate la somma dei rappresentanti delle due classi-addendi.

2. Il prodotto, definito come funzione · : Zn × Zn → Zn si indica come

[a] · [b] = [c] = [a · b].

Ovviamente in entrambi i casi il rappresentante pu`o essere sostituito dal resto che rappresenta la classe in cui si sta operando.2_.

2_{Ad esempio, in Z}

(27)

4.7. L’ANELLO ZN 27

Potrebbe sorgere un dubbio: se sostituiamo i rappresentanti con altri rappre-sentanti, la definizione resta valida? Se cos`ı non fosse la definizione di somma e prodotto non avrebbe senso perch`e non sarebbe pi`u possibile individuare le classi somma e prodotto. Dobbiamo quindi verificare che le definizioni sono ben poste, dimostrando che cambiando rappresentanti non cambia risultato. Chiamiamo a0 _{un rappresentante della stessa classe di a, tale che a ≡}

n a0 e b0

un rappresentante della stessa classe di b, tale che b ≡n b0.

Occorre verificare che a + b ≡n a0+ b0 e che a · b ≡na0· b0. Questo, però, è già

dimostrato perch`e la congruenza `e compatibile con la somma e col prodotto.3

4.7 L’anello Z

n

La struttura (Zn, +, ·) `e un anello commutativo con unit`a. In questa

struttura non valgono sempre:

• la legge di annullamento del prodotto; per esempio, in Z12[3] · [4] = [12] =

[0] pur essendo 3, 4 6= 0. Ne concludiamo, inoltre, che esistono divisori dello 0.

• la legge di cancellazione del prodotto; per esempio in Z12[3]·[6] = [18] = [6]

che può anche essere scritto [3] · [6] = [1] · [6]. Se valesse la legge di cancellazione, allora risulterebbe [3] = [1] ma sappiamo che ciò non è vero.

Un altra proprietà che possiamo enunciare riguarda l’invertibilità: La classe [a] è invertibile se ∃[b] tale che [a] · [b] = [b] · [a] = 1. Inoltre se [b] esiste, allora è unica.

Dimostrazione dell’unicit`a: Supponiamo che la classe abbia due inverse: [b] e

[b0_{]. Risulterebbe [a] · [b}0_{] = [b}0_{] · [a] = 1 e analogamente [a] · [b] = [b] · [a] = 1.}

Prendiamo la prima di tali uguaglianze.

Abbiamo quindi che [b0_{] = [1] · [b}0_{] cio`e [b}0_{] = [ab][b}0_{]. Applichiamo la propriet`a}

associativa e riscriviamo l’uguaglianza come [b0_{] = [ab}0_{][b] e dunque, essendo per}

ipotesi [ab0_{] = 1 risulta ovvio che [b] = [b}0_{]. Dunque la classe inversa `e unica,}

c.v.d.

In un anello Zn ci sono sempre e solo 2 elementi invertibili: [1] e [n − 1] che

hanno come inversi loro stesse. Ad esempio, in Z12: [11] · [11] = [1].

4.8 Congruenze di primo grado a un’incognita

Si tratta di risolvere congruenze nella forma ax ≡nb che equivale alla scrittura

[a] · [x] = [b].

3_{Un esempio del prof. Tinaglia pu`}_{o rendere pi`}_{u facile comprendere il concetto di}

(28)

Un intero `e una soluzione della congruenza se sostituito a x la rende vera. Se

x1`e una soluzione della congruenza, allora sono soluzioni tutti gli elementi della

classe [x1].4

Due soluzioni x1, x2 si dicono coincidenti se x1 ≡n x2. In caso contrario si

dicono distinte.

Ovviamente, risolvere una congruenza significa trovare la classe o le classi di resti che la rendono vera, o riconoscere che `e impossibile trovare tali classi.

Teorema 1 La congruenza ax ≡n b ha soluzioni se e solo se M CD(a, b) | b.

Sia d = M CD(a, n) con a = da0_{, b = db}0_{, n = dn}0_.

Allora la congruenza ha un numero d di soluzioni date da:

x = x0+ n0h con h = 0, 1, . . . , d − 1 dove x0 `e una soluzione particolare della

congruenza.

Dimostrazione Prima di tutto dimostriamo che esiste una soluzione se e solo se M CD(a, n) | b.

Riprendiamo la definizione di congruenza di primo grado: ax ≡n b significa

che n | (ax − b). Quindi ∃y tale che ax − b = ny, ax − ny = b. Sappiamo che un’equazione del genere ha soluzioni se e solo se M CD(a, n)|b. Quindi il teorema dimostrato in quanto se b = db0 _{le soluzioni sono tutte e solo quelle}

date dalle soluzioni dell’equazione a0_{x − n}0_{y = b.}

Inoltre sappiamo che se x0, y0`e una soluzione particolare di questa equazione,

le sue soluzioni sono tutte e solo quelle date da: ½

x = x0+ n0h

y = y0+ a0h

Ovviamente quello che ci interessa per la soluzione della congruenza `e la x, cio`e quei valori dati dalla prima delle due equazioni del sistema.

Le soluzioni sono quindi:

x1= x0+ n0h + nt

x2= x0+ n0h1+ nt

. Quando queste sono coincidenti (cio`e sono congruenti modulo n)?

x1≡nx2se e solo se (x0+ n0h + nt) ≡n (x0+ n0h1+ nt. Da questa congruenza

possiamo, per le propriet`a enunciate all’inizio, cancellare gli addendi uguali e i multipli di n, perci`o otteniamo:

x1 ≡n x2 ⇐⇒ n0h ≡n n0h1 che per le propriet`a riguardanti le congruenze

e il Massimo Comune Divisore d, pu`o anche essere scritta n0_{h ≡}

n0_d n0h₁ cio`e

h ≡d h1

Corollario 2 Dato che ax ≡n1 ha soluzioni se e solo se (a, n) = 1 allora una

classe in Zn `e invertibile se e solo se (a, n) = 1.

Corollario 3 In Zn ogni classe [a] 6= [0] `e invertibile se e solo se n `e primo.

Corollario 4 In Zn l’anello (Zn, +, ·) `e un campo se e solo se n `e primo.

4_{Cio`e sono soluzioni della congruenza tutti gli x}

(29)

4.9. LA FUNZIONE DI EULERO 29

4.9 La funzione di Eulero

`

E molto importante conoscere gli elementi invertibili di Zn o almeno il loro

numero. Esiste una funzione che ci permette di conoscere questo numero: la funzione di Eulero, che associa ad ogni naturale n il numero di naturali m, primi con n, tali che m ≤ n. Tale numero si indica con ϕ(n).

Come determinare tale numero?

Se n 6= 1, ϕ(n) `e il numero di naturali m primi con n e minori di n e si dimostra che:

1. se p `e primo, ϕ(p) = p − 1 e ϕ(pn_{) = p}n_{− p}n−1_{= p}n_{· (1 −}1

p);

2. se (a, b) = 1 allora ϕ(ab) = ϕ(a)ϕ(b).

Formula generale Definita con n = (p1)h1(p2)h2· · · (pm)hmla fattorizzazione

standard di un numero naturale, possiamo applicare la seguente formula:

ϕ(n) = n(1 −_p1 1)(1 − 1 p2) · · · (1 − 1 pm) Per esempio, n = 600 : ϕ(600) = 600(1 −1 2)(1 −13)(1 −15)

Teorema di Eulero-Fermat 5 Se (a, n) = 1 allora aϕ(n)_≡ n 1.

Quindi, dato [a], [a]−1_{≡ a}ϕ(n)−1

Teorema di Fermat (corollario) 6 Se n `e primo e n non divide a allora

an−1_≡ n1 5

Teorema di Wilson 7 Sono equivalenti le seguenti:

1. n `e primo 2. (n − 1)! ≡n −1.

Per esempio, 5 `e primo perch`e 24 ≡5−1 o meglio 24 + 1 ≡50.6

5_{In realt`}_{a questo teorema `e meglio definito come corollario in quanto `e solo un’applicazione}

del teorema principale di Eulero-Fermat.

6_{Questo teorema non `e di grande utilit`}_{a pratica, in quanto per capire se un numero `e primo,}

(30)

Capitolo 5

Numeri razionali

5.1 Generalit`

a

Passiamo a considerare ora l’insieme dei numeri razionali, che si indicano con il simbolo Q e sono ottenuti dal seguente prodotto cartesiano: Z × {Z − {0}} che consiste cio`e delle coppie ordinate (a,b) con b 6= 0 solitamente scritte sotto la forma grafica a

b.

Solitamente, si suole chiamare a numeratore e b denominatore della frazione

a b.

Due coppie a

b,dc sono equivalenti se e solo se ab = cd cio`e se ad = bc.

Se (m, n) = 1 la frazione m

n si dice ridotta ai minimi termini.

Infatti, il numero razionale m

n `e definibile come la totalit`a delle frazioni

equiv-alenti ad esso (ottenibile moltiplicando m ed n per uno stesso intero). Per cui: Q `e l’insieme di tutte le frazioni ridotte ai minimi termini. Z `e l’insieme ⊂ Q delle frazioni m

n tali che m `e multiplo di n.

5.2 Somma e prodotto in Q

1. Si definisce somma dei due numeri razionali a

b+cd il numero razionale dato

da ad+bc bd .

2. Si definisce prodotto dei due numeri razionali a

b · cd il numero razionale

dato da ac bd.

Anche in questo caso occorre verificare che la definizione è ben posta, cioè che sostituendo a, b, ced con altri elementi l’uguaglianza è sempre valida. Verifichiamo dunque che se a

b =a 0 b0 e c_d = c 0 d0 allora a 0 b0 +c 0 d0 =a 0_d0_+b0_c0 b0_d0 .

Ci`o equivale a verificare che se ab0 _{= a}0_{b e cd}0_{= c}0_{d allora}

per la somma b0_d0_{· (ad + bc) = bd · (a}0_d0_{+ b}0_c0₎

e per il prodotto acb0_d0_{= a}0_c0_bd.

Infatti, poich`e avevamo posto ab0 _{= a}0_{b e cd}0 _{= c}0_{d, abbiamo b}0_d0_{(ad + cb) =}

b0_d0_{ad + b}0_d0_{cb = (ab}0_)dd0_{+ (cd}0_)bb0 _{= a}0_bdd0_{+ c}0_dbb0 _{= bd(a}0_d0_{+ c}0_b0_)eb0_d0_{ac =}

(ab0_)(cd0_{) = a}0_bc0_{d. Quindi le definizioni date sono ben poste.}

(31)

5.3. IL CAMPO Q 31

5.3 Il campo Q

(Q, +, ·) `e un campo, in cui modulo e ordinamento sono definiti come in Z:

∀a, b : a ≤ b se ∃c ≥ 0 tale che b = a + c. L’ordinamento `e totale, compatibile

(32)

Capitolo 6

Altri insiemi numerici

Ci sono altri due insiemi numerici di cui diamo delle definizioni sommarie.

6.1 L’insieme R

I numeri reali, indicati dal simbolo R, sono costituiti dai reali razionali (iden-tificabili con Q) che hanno una rappresentazione decimale finita o periodica e dai reali irrazionali, che invece hanno una rappresentazione decimale non finita e aperiodica.

La struttura (Q, +, ·) `e un campo. Per i reali razionali vale lo stesso ordinamento dell’insieme Q, per cui tale ordinamento `e totale.

6.2 L’insieme C

I numeri complessi si indicano con il simbolo C. La struttura (C, +, ·) `e un campo.

(33)

Capitolo 7

Alcune strutture

fondamentali

7.1 Generalit`

a

Possiamo definire alcune strutture fondamentali. Ad esempio, definiamo queste due operazioni:

∗ : A × B −→ A · : A × B −→ A

Si considera strutturato il codominio: (A, ∗), (A, ·).

Si dice che A `e una struttura su B o che A `e una B-struttura.

Consideriamo un campo K dove K `e uno degli insiemi N, Z, Q, R, C, Zm. Noi

studieremo gli spazi vettoriali V, che sono dei gruppi abeliani che sono anche K-strutture.

7.1.1 Propriet`

a

Valgono le seguenti propriet`a: 1. ∀v ∈ V : 1 · v = v

2. ∀a, b ∈ K, ∀v ∈ V : a(bv) = (ab)v

3. ∀a ∈ K, ∀v1, v2∈ V : a(v1+ v2) = av1+ av2

4. ∀a, b ∈ K, ∀v ∈ V : (a + b)v = av + bv

7.2 Il gruppo (K

n

_{, +)}

Kn_{, per n ≥ 1 intero, `e l’insieme delle n-ple ordinate di elementi di K e quindi}

un suo elemento X `e della forma (x1, x2, . . . , xi, . . . , xn) dove x1si chiama prima

componente, xi`e la componente i-esima, xn la componente n-esima.

(34)

34 CAPITOLO 7. ALCUNE STRUTTURE FONDAMENTALI

7.2.1 Somma di n-ple

La somma di n-ple viene cos`ı definita: + : Kn_{× K}n _{−→ K}n_.

Quindi, date due n-ple X = (x1, x2, . . . , xi, . . . , xn) e Y = (y1, y2, . . . , yi, . . . , yn),

la n-pla somma `e la seguente:

X + Y = (x1+ y1, x2+ y2, . . . , xi+ yi, . . . , xn+ yn)

Vogliamo ora dimostrare che la struttura (Kn_{, + `e un gruppo abeliano.}

Ver-ifichiamo dunque se valgono le propriet`a di un gruppo abeliano:

(i) (X + Y ) + Z = X + (Y + Z): la dimostrazione `e immediata perch`e la somma si effettua componente per componente ottenendo (xi+ yi) + zy=

xi+(yi+zi), dove le componenti appartengono a K, dove vale la propriet`a

associativa.

(ii) X + Y = Y + X: per lo stesso motivo, anche questa propriet`a `e verificata (iii) ∃0 = (0, 0, . . . , 0, . . . , 0), elemento neutro tale che X + 0 = X: stesso

discorso

(iv) esistenza dell’opposto: si tratta delle componenti cambiate di segno in quanto: X + (−X) = 0 (dimostrabile con lo stesso criterio)

7.2.2 Prodotto per scalari

Il prodotto per scalari `e un’operazione cos`ı definita:

· : K × Kn_{−→ K}n_{. Il prodotto si ottiene moltiplicando per un intero, tutte le}

componenti della n-pla:

aX = (ax1, . . . , axi, . . . , axn). Anche in questo caso valgono le propriet`a della

moltiplicazione, e si nota che se n = 1, il prodotto in Kn _{equivale al prodotto}

(35)

Capitolo 8

Matrici

8.1 Generalit`

a

Dato il campo K si definisce matrice del tipo m × n una tabella della forma:

A =       a11 · · · a1j · · · a1n · · · · · · · · · · · · · · · ai1 · · · aij · · · ain · · · · · · · · · · · · · · · am1 · · · amj · · · amn      

dove le righe sono n-ple e le colonne sono m-ple. Ogni elemento `e dunque contrassegnato dal simbolo aij dove i indica la riga e j la colonna su cui giace

l’elemento.

Quando m = n la matrice si dice quadrata, in caso contrario `e rettangolare e allora n si chiama ordine della matrice.

Di solito una matrice A ∈ Km,n_{si indica con A = (a}

ij)j=1,...,ni=1,...,mo semplicemente

con (aij).

8.2 Somma di matrici

La somma di matrici `e un’operazione cos`ı definita: + : Km,n_{× K}m,n_{−→ K}m,n_.

Date A = (aij), B = (bij) si scrive A + B = C, dove C = (cij) `e la matrice

somma ottenuta dalla somma di elementi omonimi delle due matrici addendi:

cij = aij+ bij.

Anche Km,n _{`e un gruppo commutativo, in quanto le sue propriet`a vanno a}

cadere in K.

(36)

36 CAPITOLO 8. MATRICI

8.3 Prodotto di un numero per una matrice

Il prodotto di un numero per una matrice `e un’operazione che si esegue molti-plicando ogni elemento della matrice per l’intero. In simboli:

a · A = C dove C = (cij) e cij = a · (aij).

8.4 Prodotto righe per colonne di matrici

Date le due matrici A ∈ Km,n_{, B ∈ K}n,p _{in cui cio`e il numero di colonne di A}

`e uguale al numero di righe di B.

Sapendo che A = (ars), B = (bhk), scriviamo A · B = C dove gli elementi della

matrice C sono cos`ı individuati:

cij=

Pn

q=1aiq· bqj.

C ∈ Km,p _{cio`e la matrice risultante dal prodotto ha lo stesso numero di righe}

di A e lo stesso numero di colonne di B.

Praticamente si esegue la somma tra il prodotto di ogni elemento di una riga di A con ogni elemento di una colonna di B. Un esempio pratico:

µ 2 3 1 4 3 2 ¶ ·   3 1 4 3_{2 1 3 1} 3 3 2 1   = µ 2 · 3 + 3 · 2 + 1 · 3 2 · 1 + 3 · 1 + 1 · 3 2 · 4 + 3 · 3 + 1 · 2 2 · 3 + 3 · 1 + 1 · 1 4 · 3 + 3 · 2 + 2 · 3 4 · 1 + 3 · 1 + 2 · 3 4 · 4 + 3 · 3 + 2 · 2 4 · 3 + 3 · 1 + 2 · 1 ¶

8.4.1 Propriet`

a del prodotto tra matrici

(i) A · (B · C) = (A · B) · C

(ii) (a · A) · B = A · (a · B) = a · (A · B) (iii-i) (A + B) · C = AC + BC

(iii-ii) C · (A + B) = CA + CB

8.5 Matrice trasposta

Si definisce trasposta quella matrice ottenuta scambiando le righe con le colonne. In simboli:

data la matrice A ∈ Km,n_{, la sua trasposta `e la matrice A}t _{∈ K}n,m _{tale che}

at ij = aji.

Nota che (At₎t_{= A e che (AB)}t_{= B}t_At _{cio`e la trasposta di un prodotto `e il}

(37)

8.6. MATRICI QUADRATE 37

8.6 Matrici quadrate

Per matrice quadrata si intende una matrice in cui il numero di righe `e uguale al numero di colonne, cio`e A ∈ K, m = n. In questo caso il numero m viene denominato ordine della matrice.

Si dice diagonale principale la n-pla formata dagli elementi aijin cui i = j.

Si dice diagonale secondaria la n-pla formata dagli elementi aijin cui i + j =

n + 1.

I due elementi aij e ajisi dicono coniugati.

Vediamo ora alcuni particolari tipi di matrici che meritano una nomenclatura che li differenzi:

• Matrice identica

`

E la matrice in cui sono nulli tutti gli elementi ad esclusione di quelli della diagonale principale: I =      1 0 · · · 0 0 1 · · · 0 .. . ... . .. ... 0 0 · · · 1     

Per cui: I = (δij) dove vale la seguente propriet`a:

(δij) =

½

0 se i 6= j 1 se i = j

• Matrice triangolare alta

Si tratta di una matrice in cui sono nulli tutti gli elementi sotto la diagonale principale.

• Matrice triangolare bassa

Si tratta di una matrice in cui sono nulli tutti gli elementi sopra la diago-nale principale.

• Matrice diagonale

Si tratta di una matrice in cui sono nulli tutti gli elementi che non stan-no sulla diagonale principale (ovvero `e una matrice contemporaneamente triangolare alta e bassa).

Da ciò che abbiamo detto è evidente che il prodotto in Kn,n _è

sem-pre possibile e che quindi (Kn,n_{, ·) `e un monoide il cui elemento}

neu-tro è la matrice identità di ordine n, mentre (Kn,n_{, +, ·) è un anello non}