Numeri interi: divisione euclidea, divisibilit` a, massimo comune divisore e minimo comune multiplo, algoritmo di Euclide. Numeri primi, teorema di fattorizzazione unica. Piccolo teorema di Fermat e funzione di Eulero.

PROGRAMMA PRELIMINARE DI MATEMATICA DISCRETA (Modulo del corso di Matematica discreta ed Algebra Lineare)

Roberto Dvornicich Anno Accademico 2018-2019

CONTENUTI

Propriet` a dei numeri naturali. Assioma di buon ordinamento e principio di in- duzione. Esempi di dimostrazioni per induzione. I numeri di Fibonacci e successioni ricorrenti lineari.

Numeri interi: divisione euclidea, divisibilit` a, massimo comune divisore e minimo comune multiplo, algoritmo di Euclide. Numeri primi, teorema di fattorizzazione unica. Piccolo teorema di Fermat e funzione di Eulero.

Congruenze. Teorema cinese del resto. Equazioni e sistemi di congruenze, equazioni diofantee di primo grado. Relazioni di equivalenza e insiemi quoziente.

Struttura delle classi resto.

Criteri di divisibilit` a. Numero dei divisori di un intero. Il piccolo teorema di Fermat. La funzione φ di Eulero. Congruenze di secondo grado e congruenze esponenziali. Il sistema crittografico RSA.

Elementi di calcolo combinatorio: prodotti caretsiani, funzioni iniettive fra insie- mi finiti, numero dei sottoinsiemi, ccoefficienti bninomiali, permutazioni, principio di inclusione-esclusione ed esercizi relativi.

Anelli di polinomi. Grado di un polinomio, algoritmo di Euclide nei polinomi a coefficienti in un campo, massimo comune divisore. Teorema di Ruffini e principio di identit` a dei polinomi.

Fattorizzazione unica nei polinomi a coefficienti in un campo. Numeri comples- si: operazioni fondamentali e calcolo delle radici ennesime. Teorema fondamentale dell’algebra (senza dimostrazione). Polinomi irriducibili a coefficienti in C, R, Q.

Lemma di Gauss (senza dimostrazione) e calcolo delle radici dei polinomi a coef- ficienti interi. Relazione fra l’irriducibilt` a dei polinomi in Z e l’irriducibilit`a modulo p.

Criterio della derivata per le radici multiple di un poilnomio. Esistenza di campi finiti di cardinalit` a p

per p primo e n ≥ 1. Polinomi a coefficienti razionali, reali e complessi, e nei campi con un numero primo di elementi. Propriet` a del grado e divisione euclidea. Teorema di Ruffini. Polinomi irriducibili e fattorizzazione unica.

Fattorizzazione di polinomi. Criterio di Eisenstein. Radici multiple dei polinomi e criterio della derivata.

1

TESTI DI RIFERIMENTO

L. Childs, Algebra, Un’introduzione concreta, ETS Editrice (in inglese: A Con- crete Introduction to Higher Algebra, Springer UTM (1979).

Appunti delle lezioni di Alessandro Berarducci e Giovanni Gaiffi.

Slides delle lezioni e compiti degli anni passati in rete.

2