Teoria ed Esercizi svolti, Matematica Discreta, Capparelli

Dimostrazioni

1. Definizione di Massimo Comune Divisore (MCD)
2. Teorema sull'identità di Bezout
3. Numeri primi: dimostrazione di Euclide
4. Seconda dimostrazione dell'infinità dei numeri primi
5. Numeri perfetti e di Mersenne
6. Criteri di divisibilità per 10, per 3 e per 11
7. Criteri p-esimo di un polinomio
8. Piccolo teorema di Fermat
9. Compatibilità di una congruenza lineare
10. Teorema e invertibile e MCD(m,n)=1
11. Teorema cinese dei resti
12. Definizione di gruppo ciclico e teorema di classificazione di gruppo ciclico (primo esempio di gruppo ciclico)
13. Teorema di Lagrange
14. Teorema di Euclide che generalizza il piccolo teorema di Fermat
15. Il problema principale della teoria dei codici
16. Teorema su codice lineare con d dispari
17. Piano di Fano
18. Risolvente di Blncaca: metodo delle spartenze successive
19. Risolvente di Blncaca: metodo delle funzioni generatrici
20. Funzione generatrice per la successione di Catalan
21. Teorema di Euclide sulla partizione in parti dispari

22) Identità di condensatore di Vanderwaals dimostrata

22) me analitica e combinatoria

23) Teorema di Eulero sui comuni eulironi

24) Dimostrare che il grafo G₀ del cubo tridimensionale

es e un grafo bipartito

Seconda dimostrazione dell'infinità dei numeri primi

Esistono infiniti numeri primi.

Dimostrazione:

Supponiamo di aver elencato in ordine crescente tutti i primi p₁, p₂, ... e supponiamo per assurdo che la serie:

∑ _n=k ^∞ 1/_pn < 1/₂

converge.

Deve esistere un intero positivo k per cui

∑ _i=k+1 ⁿ 1/_pi < 1/₂

Moltiplico per un dato numero naturale N, allora

∑ _i=k+1 ⁿ N_i/_pi < N/₂

Chiamiamo p₁, p_k primi piccoli e gli altri primi grandi. Tra tutti i numeri naturali minori o uguali a N alcuni sono divisibili per almeno uno dei primi grandi ed altri invece avranno solo fattori primi piccoli. Sia N_g il numero di quelli che hanno almeno un divisore primo grande e N_p il numero degli altri (hanno solo fattori primi piccoli), è:

N = N_g + N_p

In quanto ogni numero naturale minore o uguale a N o ha almeno un fattore primo grande oppure non ne ha. Dimostriamo per contraddizione se mostriamo che per questo N si ha invece

N_g + N_p < N

Si ha il seguente criterio di divisibilità per 8:

2017

[2][10³] + [0][10²] + [1][10¹] + [7][10⁰] =

2 + 0 + 1 + 7 = 10 = 1 (mod 8)

l - cd l ≡ 0 (mod n)

allora

x̄ = ql

è una soluzione delle

congruenze.

Teorema di isomorfismo

Se G è un gruppo finito e H ⊆ G allora σ(H) | σ(G)

Dimostrazione:

Se σ(G) = n e sia H = {x₁, ..., x_n} se H = {e} allora H = G non c'è niente da dimostrare.

Se a ∈ G - H allora metto :

aH = {a x₁, a x₂, ..., a x_n} sono n nuovi elementi distinti: - se a x_i = a x_j, per la legge di cancellazione x_i = x_j contro l'ipotesi che gli elementi di H fossero distinti - se a x_i = x_j allora a = x_j x_i^-1 ∈ H contro la scelta di a (de non faro appartene mort ad H)

Ciò quindi de nuovi elementi :

se G = H ⋃ aH, allora σ(G) = 2n

quindi σ(H) | σ(G)

Altrimenti existe un b ∈ G - (H ⋃ aH). Denote :

bH = {b x₁, ..., b x_n} sono tutte distinte da quelle di prima indicate: - se b x_i = b x_j, allora x_i = x_j contro l'ipotesi che gli elementi di H fossero distinti

(1) Piano di Fano

Consideriamo il Piano di Fano

S = {1, 2, 3, 4, 5, 6, 7}

e sette rette (o blocchi):

• B₁ = {1, 5, 4}
• B₂ = {1, 6, 3}
• B₃ = {3, 4, 2}
• B₄ = {1, 2, 5}
• B₅ = {3, 2, 6}
• B₆ = {2, 6, 4}
• B₇ = {3, 5, 6}

Proprietà:

• - 2 punti appartengono ad una sola retta o blocco
• - 3 rette qualunque si intersecano in un punto

Consideriamo la matrice di incidenza definita da:

e_ij = {1 se P_j ∈ B_i, 0 se P_j ∉ B_i}

Ricorrenze di Fibonacci metodo delle funzioni generatrici

Definiamo una funzione mediante la seguente formula

F(z) = _k=0^∞ F_kz^k = F_o + F₁z + F₂z² + ...

dove, essendo F_n il n-esimo numero di Fibonacci

F(z) = zF(z) - z²F(z) =

= z + (F₂ - F₁) z² + (F₃ - F₂ - F₁) z³ + (F₄ - F₃ - F₂) z⁴ + ...

Allora

F(z) ( 1 - z - z² ) = z

F(z) = z / ( 1 - z - z² )

Decomponiamo in fratti semplici:

F(z) = 1/√5 ( 1/(1 - φz) - 1/(1 - Φz) )

trovando lo sviluppo in serie delle serie geometrica:

1/(1 - x) - _k=0^∞ x^k

si ha

F(z) = 1/√5 ( _k=0^∞ φ^k z^k - _k=0^∞ φ^-k z^k ) = _k=0^∞ F_k z^k

L’identità di Vandermonde è:

∑_k=0ⁿ ( ^rC_k ) ( ^sC_(n-k) ) = ( ^r+sC_n )

con n intero

Dimostrazione combinatoria

Se r e s sono interi non negativi o dette allora il numero de modi di scegliere n persone da un gruppo di r uomini e s donne. A sinistra essun addendo è il numero di modi di scegliere k uomini e n-k donne. L’ideale quindi deve coincidere con il secondo membro.

Per esempio: r=4, s=6, n=5

( ¹⁰C₅ ) = ( ⁴C₀ )( ⁶C₅ ) + ( ⁴C₁ )( ⁶C₄ ) + ( ⁴C₂ )( ⁶C₃ ) + ( ⁴C₃ )( ⁶C₂ ) + ( ⁴C₄ )( ⁶C₁ ) + ( ⁴C₅ )( ⁶C₀ )

252 = 1•6 + 4•15 + 6•20 + 4•15 + 1•6 + 0•1

252 = 252

Dimostrazione analitica

(1+x)^r+s = ∑_k=0^r+s ( ^r+sC_k ) x^k

(1+x)^r+s = (1+x)^r(1+x)^s

Quindi:

∑_a=0^s ( ^r+sC_r ) x^r = ∑_i=0^r ( ^rC_i ) xⁱ ∑_a=0^s ( ^sC_a ) x^a =

DETERMINARE ULTIME CIFRE

1. Determinare ultime 2 cifre di 5²⁰²³ (25)
2. Determinare ultime 3 cifre di 2⁹⁹⁹⁹ (143)
3. Determinare ultime 2 cifre di 3⁴⁶ (04)
4. Determinare ultime 2 cifre di 5³²² (37)
5. Determinare ultime 2 cifre di 7⁵⁰⁸ (43)
6. Determinare l'ultima cifra di 13²⁰³²¹ (6)
7. Determinare le ultime 2 cifre di 23¹⁰⁰² (29)
8. Determinare l'ultima cifra di 3¹⁰⁰¹ (3)