Per il Teorema di Ruffini si ha f(x)=(x-a1)g1(x), con g1(x)A[x]

Matematica Discreta II

Lezione del giorno 14 novembre 2007

Una conseguenza importante del Teorema di Ruffini è la seguente:

Corollario. Siano A un anello commutativo con unità in cui vale la legge di annullamento del prodotto, f(x)A[x] un polinomio non nullo di grado n, A un elemento fissato.

Allora: il numero di radici distinte di f(x) in A è £n.

Dimostrazione:

Siano a1,a2,…,atA le radici distinte di f(x) in A. 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 in 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 t passi, si ha:

f(x)=(x-a1)(x-a2)…….(x-at)gt(x) con gt(x)A[x]

Calcolando i gradi di ambo i membri (e ricordando che, per le ipotesi su A, il grado del prodotto di polinomi è la somma dei gradi dei fattori) si ha che n è la somma di t e del grado di g(x) (che è non negativo), dunque t£n.

Osservazione: se in A non vale la legge di annullamento del prodotto, il Corollario precedente può non valere.

Per esempio, se A= Z8 , il polinomio f(x)=[4]x di grado 1 ha 4 radici distinte in A: [0], [2], [4], [6] . Per dimostrare una importante proprietà della funzione di Eulero, premettiamo il seguente risultato:

Lemma. Sia n un numero naturale ed S l’insieme dei divisori di n. Allora la funzione f: S  S definita da f(x)=n/x è biunivoca.

Dimostrazione:

Notiamo che se xS allora esiste un naturale y tale che xy=n, ed ovviamente f(x)=n/x=yS.

Si verifica facilmente che f è iniettiva, e dunque (essendo dominio e codominio finiti di eguale cardinalità) f è anche surgettiva.

Teorema. Sia n un numero naturale ed S l’insieme dei divisori di n. Allora si ha: n= 

S d

d)

(

Dimostrazione:

Per ogni dS sia Sd = {x naturale / 1£x£n , mcd(x,n)=d}: tale insieme è non vuoto perché almeno dSd .

Al variare di dS gli insiemi Sd formano una partizione di {1,2….,n}: infatti ogni elemento x{1,2….,n} appartiene a qualche Sd (basta scegliere d=mcd(x,n)) e ovviamente, se c,dS sono distinti, gli insiemi Sd, Sc non hanno elementi comuni (se per assurdo fosse xSdSc si avrebbe mcd(x,n)=c=d, contraddizione). Calcolando la cardinalità si ottiene n = {1,2,….,n}= 





 S d

Sd . Fissato dA, sia Td = {x naturale / 1£x£n/d ; x, n/d coprimi}. Notiamo che Td= (n/d).

Definiamo la funzione g : Sd  Td ponendo g(x)=x/d (notare che se xSd allora 1£x£n , mcd(x,n)=d, dunque 1£x/d£n/d e x/d, n/d sono coprimi perché è noto che dividendo 2 numeri naturali per il loro mcd si ottengono numeri coprimi: in totale si ha g(x)=x/dTd) .

La funzione g è biunivoca: l’iniettività è facile da dimostrare; per la surgettività basta osservare che se yTd (dunque 1£y£n/d ; y, n/d coprimi), allora x=yd è tale che g(x)=x/d=y ed inoltre 1£x=yd£n, mcd(x,n)=d (infatti d è per costruzione divisore comune di x,n; inoltre se c è un divisore comune di

x,n, allora, essendo 1=mcd(y,n)=yz+nr con z,r interi, si ha d=xz+ndr=multiplo di c): si è dunque trovato un elemento xSd tale che g(x)=y.

Essendo g biunivoca:Sd=Td= (n/d), per ogni dS.

Da quanto dimostrato sopra si ha:

n = {1,2,….,n}= 





 S d

Sd = 

S d

(n/d)

 .

Sfruttando la funzione biunivoca f. A  A definita nel Lemma, si ha che A=f(A)={n/d / dS}, da cui, potendo nella sommatoria commutare l’ordine degli addendi:

n = 

S d

(n/d)

 = 

S d

(d)

e si ottiene la tesi del Teorema.

Teorema. 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è esiste un elemento di G di periodo = n.

Sia S l’insieme di tutti i naturali divisori di n. Per ogni dS sia Xd il sottoinsieme di G formato dagli elementi di G di periodo d (a priori può essere Xd=). Supponiamo che Xd¹, e calcoliamo la cardinalità di Xd .Fissiamo un elemento  in Xd (quindi  ha periodo d): le potenze distinte di  cosituiscono il sottogruppo ciclico () generato da  e sono in numero di d essendo

() = {⁰, ¹,…, ^d-1} .

Ognuna di tali potenze è radice del polinomio di grado d: f(x)=x^d-1AA[x]; infatti (aⁱ)^d=(a^d)ⁱ=1A per ogni i=0,1,….d-1. Essendo A un campo, il polinomio f(x) ha in A al più d radici, dunque le d potenze di  esauriscono tutte le radici di f(x) in A.

Ma un elemento qualunque Xd è radice di f(x) (perché  ha periodo d dunque ^d=1A) .

Si conclude che ogni elemento di Xd è una potenza di . Dunque gli elementi di Xd sono le potenze di  che hanno periodo d, cioè i generatori del gruppo ciclico () di cardinalità d, e per un risultato precedente sono in numero di (d). Si deduce che Xd ha cardinalità (d) (se è ¹). Al variare di dS, i sottoinsiemi Xd 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Xd), ossia formano una partizione di G.

Dunque:

n = G = 

dS

Xd

Per un Teorema precedente si ha n= 

dS

(d)= 

dS

Xd . Ma Xd=0 (se Xd=) oppure

Xd=(d) (se Xd¹). Dalla precedente eguaglianza delle sommatorie segue che nessun Xd è vuoto (altrimenti 

dS

Xd < 

dS

(d), contraddizione) e in particolare, per d=n, Xn¹, ossia esiste un elemento in G di periodo n, e si ha la tesi.

Dal Teorema precedente segue un risultato già anticipato in precedenza: se n è primo (quindi Zn è campo finito) il gruppo moltiplicativo Zn* = {[1], [2], …., [n-1]}={1,2,….,n-1} è un gruppo ciclico (si è già detto che un generatore a di Zn* è chiamato radice primitiva modulo n).

Nota: La dimostrazione del Teorema precedente non è costruttiva, dunque non fornisce un algoritmo per calcolare una radice primitiva modulo n, quando n è primo.