Formulario Matematica discreta

Matematica discreta

Aritmetica modulare

Studio delle proprietà della somma e del prodotto in Z (insieme delle classi di congruenza modulo n).

Relazione d’equivalenza

Una relazione d’equivalenza su un insieme A è una relazione che è:

• Riflessiva: aRa
• Simmetrica: aRb ⇒ bRa
• Transitiva: aRb e bRc ⇒ aRc

Classe di equivalenza

Se R è una relazione d’equivalenza su A introduciamo la classe d’equivalenza di a:

[a] = {b ∈ A | aRb}

Relazione di congruenza

La relazione R := { (a,b) ∈ ZxZ tali che n|a-b} è detta relazione di congruenza modulo n. Si può scrivere a ≡ b mod n oppure a ≡ bₙ.

La relazione è di congruenza.

Due interi sono congrui modulo n se divisi per n danno lo stesso resto.

Proprietà di somma e prodotto

[a]ₙ + [b]ₙ = [a+b]ₙ e [a]ₙ * [b]ₙ = [a*b]ₙ.

11+3=14=2.

Es. Per la somma vale la proprietà associativa, commutativa, c’è lo zero, c’è l’opposto.

Per la moltiplicazione vale la proprietà associativa, commutativa, distributiva, ha l’unità e una classe è invertibile se esiste una classe b (inversa) tale che a*b=1.

Congruenza lineare

Una congruenza lineare è un’espressione del tipo ax ≡ c mod n.

Risolverla vuol dire determinare gli u soluzioni della congruenza lineare.

ax ≡ c mod n ha soluzioni ⇔ l’equazione diofantea ax+ny=c ha soluzioni, quindi ax ≡ c mod n ha soluzioni ⇔ d := MCD(a,n)|c e a/d x ≡ c/d mod n/d.

Esercizio: Risolvere 12x ≡ 7 mod 15.

Sol: d := MCD(12,15)=3, 3 non divide 7 quindi non ci sono soluzioni.

Esercizio: Risolvere 12x ≡ 5 mod 21.

Sol: MCD(12,21)=3, 3 divide 15, ok.

Divido per d: 4x ≡ 5 mod 7.

Risolvo l’equazione diofantea 4x+7y=5.

La mia u è l’equazione delle soluzioni particolari di x, cioè u = 10 + 7k al variare di k.

Equazioni lineari in Zₙ

Per raggrupparle divido k per d := MCD(12,21)=3. Quindi k = q*3+r, 0 <= r < d(3).

u = 10+7k = 10+7(3q+r) = 10+21q+7r = (10+7r)+21q, 0 <= r < d.

u ≡ 10+7r mod 21, 0 <= r < 3.

Le soluzioni sono quindi:

• r = 0: u ≡ 10 + 7*0 ≡ 10 mod 21, x ≡ 10 mod 21.
• r = 1: u ≡ 10 + 7*1 ≡ 17 mod 21, x ≡ 17 mod 21.
• r = 2: u ≡ 10 + 7*2 ≡ 24 ≡ 3 mod 21, x ≡ 3 mod 21.

a x=c.

Si tratta di espressioni della forma a x=c.

a x=c ha soluzioni se e solo se ax ≡ c mod n ha soluzioni.

Esempio: risolvere 6x ≡ 5 in Z₄.

Dobbiamo risolvere la congruenza lineare 6x ≡ 5 mod 4, ma il MCD(6,4)=2 non divide 5 quindi non ha soluzioni.

Funzione di Eulero φ(n)

Esempio: risolvere 12x ≡ 15 in Z₂₁.

Dobbiamo risolvere 12x ≡ 15 mod 21. Le soluzioni sono u=17, 3, 10.

Una classe in Zₙ è invertibile se e solo se il MCD(a,n)=1.

In tal caso l’inverso è x₀ dove (x₀,y₀) è soluzione particolare della diofantea ax+ny=1.

Esempio: Stabilire se 2 è invertibile in Z₁₅ e nel caso determinare l’inverso x.

Esso è x₀ dove (x₀,y₀) è soluzione particolare di 2x+15y=1.

MCD(2,15)=1, ok quindi applico Bézout: 2 * (-7) + 15 * (1) = 1 → x₀ = -7 in Z₁₅.

Teorema di Eulero-Fermat e piccolo teorema di Fermat

Siccome è negativo aggiungo 15: -7 +15=8.

2*8=16=1.

Per verificare: posso sottrarre 15 quante volte voglio.

È utile per calcolare le classi invertibili in Zₙ che indichiamo con φ(n).

• Consideriamo un numero primo positivo p e un naturale m allora: φ(p^m) = p^m – p^m-1. Es: φ(2)=2-1=1; φ(3)=3-1=2; φ(5)=5-1=4.
• φ(4)=φ(2²)=2²-2^2-1=2 ecc. per tutte le potenze di primi …
• Se a,b sono coprimi [MCD(a,b)=1] allora φ(a*b)=φ(a)*φ(b).

Es: φ(6)=φ(2*3)=φ(2)*φ(3)=(2-1)(3-1)=2.

φ(24)=φ(3*8)=φ(3*2³)=φ(3)*φ(2³)=(3-1)(2³-2²)=8.

φ(60)=φ(3*20)=φ(3*5*4)=φ(3)*φ(5)*φ(4)=(3-1)(5-1)(4-2)=16.

Qualsiasi numero si può scrivere come prodotto di numeri positivi.

Se a ∈ Z, n ∈ N, con n ≠ 0 e MCD(a,n)=1 allora a^φ(n) ≡ 1 mod n.

Se p è un primo positivo e a ∈ Z è tale che p non divide a, allora a^p-1 ≡ 1 mod p.

Esercizio: calcolare il resto della divisione 5⁸⁶⁴⁵³³ per 42.

Algoritmo RSA

Sol: MCD(5,42)=1 ⇒ a^φ(n) ≡ 1 mod n.

φ(42)=φ(2*3*7)=12.

5^φ(42) ≡ 1 mod 42.

Quindi: 5¹² ≡ 1 mod 42. Per trovare il resto posso dividere l’esponente per 12:

864533 = 72044*12+5.

5⁸⁶⁴⁵³³ = 5^72044*12+5 ≡ (5¹²)⁷²⁰⁴⁴*5⁵ ≡ 1⁷²⁰⁴⁴*5⁵ ≡ 3125 ≡ 17 mod 42.

Esercizio: “resto” di 131⁸⁶⁴⁵³³ per 42.

Sol: siccome 131>42 posso dividerlo per 42 per semplificare:

131=3*42+5 quindi 131 ≡ 5. Quindi 131⁸⁶⁴⁵³³ ≡ 5⁸⁶⁴⁵³³ e poi continuo.

Esercizio: “resto” di 7⁴³⁸² +13²⁷⁸⁹ per 30.

Sol: solito procedimento prima per uno e poi per l’altro e infine:

7⁴³⁸² ≡ 19 e 13²⁷⁸⁹ ≡ 13, quindi 7⁴³⁸² +13²⁷⁸⁹ ≡ 19+13 ≡ 2 mod 30.

Esercizio: determinare le ultime due cifre di 3¹⁴⁰.

Sol: Le ultime due cifre sono il resto della divisione per 100.

Quindi MCD(3;100)=1 e per E.F: 3^φ(100) ≡ 1 mod 100.

φ(100)=40.

140 = 3*40+20 → 3⁴⁰ ≡ 1 quindi: 3¹⁴⁰ ≡ 3²⁰ ≡ 3486784401 ≡ 1 mod 100.

Le ultime due cifre sono 01.

Algoritmo RSA

Destinatario: Sceglie due numeri primi molto grandi p e q, calcola il prodotto n=p*q e poi φ(n) e sceglie un numero e>1 tale che MCD(e,φ(n))=1. La coppia (n,e) è la chiave pubblica.

Mittente: Trasforma il messaggio in un numero M e lo suddivide in k blocchi di lunghezza tale che Mᵢ < MIN(p,q), per ogni i. Calcola il resto Cᵢ della divisione di ciascun Mᵢ per n: 0<= Cᵢ < n per i=1,...,k e spedisce al destinatario il messaggio codificato C=(C₁, C₂, …, Cₖ).

• Solo il destinatario può decodificare il messaggio: poiché MCD(e,φ(n))=1 la congruenza lineare ex ≡ 1 mod φ(n) ha soluzione. Per trovarla basta risolvere l’equazione diofantea (ex+φ(n)y=1). Possiamo trovare d tale che ed ≡ 1 mod φ(n).

Possiamo sostituire d con il resto della sua divisione per φ(n). La coppia (n,d) sarà la chiave privata con cui il destinatario decodificherà il messaggio.

Decodifica

ed ≡ 1 mod φ(n) → φ(n)|ed-1 → esiste h tale che ed=h*φ(n)+1.

Calcola il resto della divisione Cᵢ^d mod n. Cᵢ^d ≡ Mᵢ^ed mod n ≡ Mᵢ^h*φ(n)+1 ≡ (Mᵢ^φ(n))^h*Mᵢ mod n.

Poiché Mᵢ <MIN(p,q) allora MCD(Mᵢ,n)=1 → Mᵢ^φ(n) ≡ 1 mod n.

1^h*Mᵢ =Mᵢ cioè: Cᵢ^d ≡ Mᵢ mod n (0<=Mᵢ>=l<n) dove Mᵢ è il resto. Riassemblo: M = M₁,M₂,M₃,…,Mₖ.

Esempio: p=11; q=13 → n=p*q=11*13=143; φ(n)=φ(11)*φ(13)=10*12=120.

Scelgo e tale che MCD(e, φ(n))=1. e=7. La coppia (n,e)=(143,7) è la chiave pubblica.

Affinché Mᵢ <Max(p,q)=11, basta considerare blocchi di lunghezza l=1.

Codifica: M=306 → M₁=3, M₂=0, M₃=6.

M₁^e = 3⁷ =2187 ≡ 42 mod 143 =: C₁.

M₂^e = 0⁷ =0 =: C₂.

M₃^e = 6⁷ =279936 ≡ 85 mod 143 =: C₃.

Per decodificare trovo d risolvendo ex ≡ 1 mod φ(n) cioè 7x ≡ 1 mod 120 → 7x+120y=1.

Per Bézout trovo 7*(-17)+120*(1)=1. Allora -17 è una soluzione.

Scelgo d= -17+120=103. La coppia (n,d)=(143,103) è la chiave privata.

Decodifica: C₁^d =42¹⁰³ ≡ 3 mod 143 := M₁.

C₂^d = 0¹⁰³ ≡ 0 mod 143 := M₂.

C₃^d = 85¹⁰³ ≡ 6 mod 143 := M₃.

M = M₁ M₂ M₃ = 3 0 6.

Combinatorica

DEF: Studio della cardinalità di insiemi finiti.

Principio della somma

Se A e B sono insiemi disgiunti allora |A U B|= |A|+|B|.

Principio del prodotto

|A₁ x A₂ x … x Aₙ| = |A₁| x |A₂| x … x |Aₙ|.

Principio di inclusione-esclusione

• Se A e B sono due insiemi, allora |A U B| = |A| + |B| - |A ∩ B|.
• Se A, B e C sono tre insiemi, allora |A U B U C| = |A|+|B|+|C|-|A ∩ B|-|A ∩ C|-|B ∩ C|+|A ∩ B ∩ C|.

Metodo delle scelte successive

|P|= k₁ * k₂ * … * kₙ.

Coefficiente binomiale

(n sopra k) = n! / (k! (n-K)!).

Binomio di Newton

(x+a)ⁿ = Σ_k=0ⁿ (n sopra k) x^n-ka^k.

Esempi

Su 100 studenti 80 hanno superato matematica, 70 logica e 60 entrambe.

Quanti di loro hanno superato almeno una delle due parti? Quanti nessuna?

S: insieme studenti |S|= 100.

M: studenti che hanno superato mate |M|=80.

L: studenti che hanno superato logica |L|=70.

M ∩ L: studenti che hanno superato entrambe |M ∩ L|=60.

M ∪ L: studenti che hanno superato