Teoria dei numeri
Lezione del giorno 30 aprile 2008 Corollario.
Siano A un campo ed f(x) un polinomio non nullo in A[x] di grado n. Il numero di radici distinte di f(x) in A è £n.
Dimostrazione:
Siano a1,a2,…,arÎA radici distinte di f(x). Per il Teorema di Ruffini si ha f(x)=(x-a1)g1(x), con g1(x)ÎA[x]. Da 0A=f(a2)=(a2-a1)g1(a2) e da a2-a1¹0A segue g1(a2)=0A (per la legge di annullamento del prodotto valida nel campo A). Di nuovo per il Teorema di Ruffini si ha g2(x)=(x-a2)g2(x), con g2(x)ÎA[x], da cui f(x)=(x-a1)(x-a2)g2(x). Così procedendo, dopo r passi, si ha:
f(x)=(x-a1)(x-a2)…….(x-ar)gr(x) con gr(x)ÎA[x]
Calcolando i gradi di ambo i membri si ha n=r+gr(g(x)), dunque r£n, perché gr(g(x))³0.
Osservazione: se A non è un campo, il Corollario precedente può non valere.
Per esempio, se A= Z4 , il polinomio f(x)=[2]x di grado 1 ha 2 radici in A: [0], [2].
Sia A un campo: possiamo considerare il gruppo moltiplicativo A*=A-{0A} degli elementi invertibili di A rispetto al prodotto.
Lemma.
Se A è un campo finito, il gruppo moltiplicativo A*=A-{0A} è un gruppo ciclico.
Dimostrazione:
Sia G=A*, ed n=G: la tesi è che esiste un generatore del gruppo G, cioè un elemento aÎG di periodo = n.
Sia S l’insieme di tutti i naturali divisori di n. Per ogni dÎS sia Sd il sottoinsieme di G formato dagli elementi di G di periodo d (a priori può essere Sd=). Supponiamo che Sd¹, e calcoliamo la cardinalità di Sd .Fissiamo un elemento a in Sd (quindi a ha periodo d): le potenze distinte di a sono in numero di d e sono a0, a1,…,ad-1. Ognuna di tali potenze è radice del polinomio di grado d:
f(x)=xd-1AÎA[x]; infatti (ai)d=(ad)i=1A. Essendo A un campo, il polinomio f(x) ha in A al più d radici, dunque le d potenze di a esauriscono tutte le radici di f(x) in A.
Ma un elemento qualunque bÎSd è radice di f(x) (perché b ha periodo d dunque bd=1A) .
Si conclude che ogni elemento di Sd è una potenza di a. Per costruzione gli elementi di Sd sono le potenze di a che hanno periodo d, dunque, per un risultato precedente sono in numero di (d).
Dunque Sd ha cardinalità (d) (se è ¹). Al variare di dÎS, i sottoinsiemi Sd sono banalmente a due a due disgiunti e la loro unione è G (se yÎG, detto d il periodo di y, si ha d divisore di n, dÎS, yÎSd).
Dunque:
n = G =
ÎS
d Sd =
n d Sd
Per un risultato precedente si ha n=
n d
(d)
=
n d Sd
. Ma Sd=0 (se Sd=) oppure Sd=(d) (se Sd¹). Dall’eguaglianza precedente segue che nessun Sd è vuoto (altrimenti
n d Sd
<
n d
(d)
) e in particolare Sn¹, ossia esiste un elemento in G di periodo n, e si ha la tesi.
Nota: La dimostrazione precedente non è costruttiva, perché non fornisce un algoritmo per il calcolo di un generatore del gruppo A* .
Teorema di Gauss (il caso n primo).
Se n è primo, il gruppo moltiplicativo Zn* è ciclico (quindi esiste qualche radice primitiva modulo n).
Dimostrazione:
Segue immediatamente dal Lemma, essendo Zn un campo finito.
Nota: La dimostrazione del Lemma precedente non è costruttiva, dunque non fornisce un algoritmo per calcolare una radice primitiva modulo n, quando n è primo: a tutt’oggi non è noto nessun algoritmo di complessità polinomiale che risolva il problema.
In ogni caso, se n è primo, sappiamo che il numero di radici primitive modulo n è ((n))=(n-1).
Per esempio se n=11, il numero di radici primitive modulo 11 è (10)=4.
