Algebra - Matematica Discreta

Parte di Algebra

LOGICA: scritto + orale facoltativo + orale obbl. come abbona

ALG e GEST: scritto + orale facoltativo

Numeri naturali ↔ numeri interi positivi

N = {0,1,2,3,...}

Proprietà dei numeri naturali

1. Proprietà commutativa _somma a + b = b + a   ∀ a,b ∈ ℕ
2. Proprietà associativa _somma (a + b) + c = a + (b + c)   ∀ a,b,c ∈ ℕ
3. Esiste elemento neutro _somma a + 0 = a   ∀ a ∈ ℕ
4. Prop. associativa commutativa _prodotto a · b = b · a   ∀ a,b ∈ ℕ
5. Prop. associativa _prodotto a · (b · c) = (a · b) · c   ∀ a,b,c ∈ ℕ
6. Elemento neutro _prodotto a · 1 = 1 · a = a   ∀ a ∈ ℕ
7. Prop. distributiva _prodotto rispetto a _somma a · (b+c) = a · b + a · c   ∀ a,b,c ∈ ℕ

Legata all’insieme dei n. naturali c'è il processo di dimostrazione per induzione → con una serie di passaggi logici, si arriva ad una dimostrazione serve per dimostrare le proprietà legate ai numeri naturali → serve per dimostrare che una proprietà P(n) è vera per ogni numeri naturali.

Oss: La base induttiva di solito è 0 e 1, ma può essere anche un altro numero m.

In questo caso si dimostra una proprietà P(n) ∀ n ≥ m.

Principio di induzione

Se p(n) è una formula tale che

• p(0) è vera Base induttiva
• ∀m ∈ ℕ, se p(m) è vera allora p(m+1) è vera

Allora, anche p(m) è vera ∀m ∈ ℕ

Es. 1

Dimostrare che la somma dei primi n numeri naturali è uguale a

_m(m+1)²

Ovvero

1 + 2 + 3 + ⋯ + m = _m(m+1)² p(m)

OSS: se m = 1

1 = ₁₍₁₊₁₎² → 1 = 1

se m = 2

1 + 2 = ₂₍₂₊₁₎² → 3 = 3

(però ora ho dimostrato solo per due numeri)

Allora uso il princ. di induzione

Dimostrazione per ind.

Base induttiva m = 1

Dimostriamo che p(1) è vera

se m = 1

1 = _{1 (1+1)}² SI poiché 1 = 1

Supponiamo che p(m) sia vera

p(m) è vera, cioè che

1 + 2 + ⋯ + m = _m(m+1)²

E dimostriamo che

(m+1)⟹ m+1 p(m+1)

1 + 2 + ⋯ + m + (m+1) = (_m(m+1)²) + (m+1)

= _{m(m+1) + 2(m+1)}²

= _(m+1)(m+2)²

Fine della dimostrazione

Dimostrare che

∑_k=2^m (1 - ₁^k2) = (m+1)/2m    ∀ m ≥ 2

↳ esplicito

↳ dimostro P(m)

↳ suppongo P(m) vera e dimostro P(m+1)

Teorema

a, b ∈ ℤ

_{m.c.m (a,b)} = ^|a∙b|⁄_M.C.D.(a,b)

Esempio precedente: m.c.m (207, 144)

m.c.m (207, 144) = ^207∙144⁄₃ = 51 429

Es per casa. MCD e m.c.m tra 1876 e 365

[₁] [_{684 740}]

1. a : b →1876 : 365 → 5 51 → 1876 = 5 * 365 + 51
2. b : r1 →365 : 51 → 7 8 ...
3. r1 : r2 →51 : 8 → 6 3 ...
4. 8 : 3 → 2, 2, ...
5. 3 : 2 → 1, 1 → ...3 = 19 * 2

MCD 1 OK!

6. 2 : 1 → 2 ...

m.c.m (1876, 365) = ^{1876 ∙ 365}⁄₁ = 684 740

OK!

(Prova con fattorizzazione)

1876 365

938 2 365 5

469 7 73 73

OK! MCD = 1 (non ho fattori comuni)

OK! mcm = 2^2 * 7 * 67 * 5 * 73 = 684 740

1876 = 2^2 * 7 * 67

365 = 5 * 73

Definizione a, b ∈ ℤ → Se M.C.D (a,b) = 1 a e b si dicono coprimi (o primi tra loro)

2es) trovare le coordinate intere della retta

M.C.D. (2, 9) = 1

3 = > 3 sol intere

(x₀, y₀) = (3, -1) sol particolare

x = 3 + 9t

y = -1 - 2t

t ∈ ℤ

(3 + 9t; -1 + 2t) t ∈ ℤ

Teo. Diofante: a, b ∈ ℤ non entrambi nulli

Dimostrazione :

(x₀, y₀) sol. particolare

M.C.D(a, b) = d

osi che

t ∈ ℤ è una soluzione

Sostituisco nell’equazione

a(x + b₁)t + b(y - a₁)t = c

a⟶x₀ + a⟶b + b⟶y = c s1 sola porche (x₀, y₀) è soluzione

Dimostriamo che

Se (x,y) è sol. dell’equazione allora assume la forma

(x,y) sol.

x = x₀ + t b₁

y = y₀ - a₁ t

x = (x + b) t = a(x - x₀) + b(y - y₀) = 0

Osserviamo che

M.C.D. (a / d, b / d) = 1

≡_m è transitiva

a ≡_m b, b ≡_m c ⟹ a ≡_m c

infatti a ≡_m b ⟹ m|a-b

⟹

b ≡_m c ⟹ m|b-c

⟹ m|(a-b)+(b-c)

⟹ m|a-c ⟹ a ≡_m c

OSS.: a, b ∈ Z (importantissima)

a:b ==> ∃ q, r t.c. a = bq+r 0 < r ≤ |b|

posso scrivere a-r = bq b|a-r

quindi

a ≡_r r

dividendo = resto

divisione

ES.: Trovare tutti gli m ∈ Z t.c. m ≡ 7

m ≡₃ 7

⟹ |3| m = 7

⟹ ∃ K t.c. m = 7=3k

m = 3k+7 k ∈ Z

• ..., 2, 1, 4, 7, 10, 13, 16, ...

= {1̅₇} CLASSE DI 7

DEF: Le classi di equivalenza della ≡_m sono dette

classi di congruenza mod m oppure classi di resto

TEOREMA: m intero positivo

Allora ogni a ∈ Z è congruo modulo m ad uno ed

uno solo tra gli interi 0, 1, ..., m-1 cioè i possibili resti della

divisione per m

DIM.: Eseguo a:m , m intero positivo

Per il teorema della div. euclidea ∃! q, r t.c. a = mq+r

0 < r < m

⟹ a = mq+r ⟹ m|a-r

⟹ a ≡_m r e r ∈ {0, 1, ..., m-1}

DIMOSTRATO

CHE è CONGRUO

⟹ ORA DIMOSTRIAMO CHE r è UNICO

DIM. TEOREMA CIN. RESTO

m = b₁y₁ ⇒ m = bx + y₁

quindi ax + t = bx + y₁

⟹ at - bs = y - x

OSS. CHE a, b, y - x ∈ ℤ

è quindi una eq. diofantea nelle incognite t, s [ax + by = z]

Per il teorema sulle eq. diofantee l' eq. ha soluzione se MCD (a, b) | y - x

Per il teorema di euclide esteso si trova una soluz. particolare(t₀, s₀) e le soluzioni di ⧒ sono

(t₀, s₀) = (t₀ - ^b/_{mcd(a, b)} λ, s₀ + ^a/_{mcd(a, b)} λ), λ ∈ ℤ

SOSTITUISCO t₀ - ^b/_{mcd(a, b)} λ in m = x + at

e ottengo m = x + at₀ - ^ab/_{mcd(a, b)} λ =

= x + at₀ - m.c.m (a, b) λ

PONGO m₀ = x + at₀

ALLORA LA SOL. È DELLA FORMA

m = m₀ + λ m.c.m. (a, b) con λ ∈ ℤ

Oppure si sostituisce s₀ + ^a/_{mcd(a, b)} λ in m = b₀ + y₁

e si prendano come sol. particolari m₀ = y₁ t₀

X ≡ … 40t … X = 40t + 11

X ≡ … 43s … X = 43s + 12

40t + 11 = 43s + 12

40t - 43s = -1

DIOFANTEA

euclide esteso

43 = 1 . 40 + 3 . 3

3 = 43 - 40 . 1

40 = 13 . 3 + 1

1 = 40 - 3 . 13

TROVO s e t:

t = 40 - 3 . 13

t = 40 - (43 - 40) . 13

t = 40 - 43 . 13 + 40 . 13

t = 1(40 - 43 . 13)

(t₀, s₀) = (154, 143)

X₀ = 40 . 154 + … = 6160t + 616t

X = 6161 + mcm (40, 43) λ, λ ∈ ℤ

X = 6161 + 1720 λ

X = 6161 + 3 …

6161 + 1720₁

1001

altri del

X ≡ … 1001 … X = 1001 + 1720t

X ≡ … 49

X = 49 . … X = 29 + 49s

1720t - 49s = 29 - 1001 = 1720t + 49s = …

1720 = 49 . 35

35 = 49 - 1 . 14

14 = 35 - …

4 = 14 - …

1 = …

ora euclide esteso