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 11, per 3 e per 11
7. Teorema p-esimo di un polinomio
8. Piccolo teorema di Fermat
9. Completabilità di una congruenza lineare
10. Teorema di invertibilità e MCD(m,n)=1
11. Teorema cinese dei resti
12. Definizione di gruppo ciclico e teorema di classificazione dei gruppi ciclici (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 codici lineari con d dispari
17. Codici di Toro
18. Ricervera di Hamming: metodo dello spazio matriciale
19. Ricervera di Hamming: metodo della funzione generatrice
20. Funzione generatrice per la successione di Catalan
21. Teorema di Euclide sulle partizioni in parti dispari

Dimostrazioni

1. Definizione di Massimo Comun Divisore (MCD)
2. Lemma 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. Criterio di divisibilità per 10, per 3 e per 11
7. Forma p-irriducibile di un polinomio
8. Piccolo teorema di Fermat
9. Compatibilità di una congruenza lineare
10. Teorema p-irriducibile e MCD(m,n)=1
11. Teorema cinese dei resti
12. Definizione di gruppo ciclico e teorema di classificazione dei gruppi ciclici (primi esempi di gruppo ciclico)
13. Teorema di Lagrange
14. Teorema di Euclide da generalizzare il piccolo teorema di Fermat
15. Il problema principale della teoria dei codici
16. Teorema su catena lineare con d dispari
17. Piani di Fano
18. Riscoperta di Fibonacci: metodo della spaziatura reticolare
19. Riscoperta di Fibonacci: metodo delle funzioni generatrici
20. Funzione generatrice per la successione di Catalan
21. Teorema di Euclide sulle partizioni a parti dispari

dibite

1. Identità di concludere di Tendermonde dimostrare non banali e combinatoria
2. Teorema di Eulero su comuni eurionni
3. Dimostrare che il grado Q_n del cubo tridimensionale non è un grado bipartito

Definizione di Massimo comune divisore (MCD)

Se a e b sono due interi non entrambi nulli, allora un intero d si dice massimo comune divisore di a e b e si scrive MCD (a, b) se:

1. d > 0
2. d è un divisore comune di a e b
3. Se g è un divisore comune di a e b, allora g ≤ d

Lemma sull'identità di

Se p è un numero primo e a e b sono due numeri interi non nulli allora

• p|ab ⇒ p|a oppure p|b

Dimostrazione:

Se p|a allora l'enunciato è vero.

Se p | e voglio dimostrare che p|b. Allora

MCD(a,n)=1

Per l'identità di abbiamo

1=mp + na

per opporturi interi m e n.

Essendo per ipotesi:

al = bp (con p|al)

E per qualche intero h, abbiamo moltiplicando per l'identità di:

b = h(mp + na) = mlp + nab

Allora

• -p|mlp perché c|b
• -p|na perché per ipotesi p|ab

Allora p|b.

Esistono infiniti numeri primi: dimostrazione di Euclide

Esistono infiniti numeri primi

Dimostrazione:

Supponiamo che esiste un insieme finito {p₁, ..., p_n} costituito da tutti i numeri primi e consideriamo il numero:

N = p₁ ⋅ ... ⋅ p_n + 1

Per il teorema fondamentale dell'aritmetica N possiede un divisore primo p. Per ipotesi:

p ∈ {p₁, ..., p_n}

quindi divide la differenza

N - p₁ ⋅ ... ⋅ p_n = 1

il che è impossibile.

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:

∑_h∊H 1/p_h

converga.

Deve esistere un intero positivo t per cui

∑_h>t 1/p_h < 1/2

Moltiplico per un dato numero naturale N, allora

∑_h>t N/p_h < N/2

Chiamiamo n_p, n_g primi