• Non ci sono risultati.

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
1
0
0

Testo completo

(1)

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

(2)

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

() = {0, 1,…, d-1} .

Ognuna di tali potenze è radice del polinomio di grado d: f(x)=xd-1AA[x]; infatti (ai)d=(ad)i=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.

Riferimenti

Documenti correlati

352 (Norme sui referendum previsti dalla Costituzione e sulla iniziativa legislativa del popolo) &#34;se prima della data dello svolgimento del referendum, la legge, o l'atto

[r]

137 Importo totale della retribuzione di risultato erogata a valere sul fondo dell'anno di rilevazione (euro) 83688 115 Importo totale della retribuzione di risultato non erogata

Valore in percentuale dell'incidenza della spesa del personale in rapporto alle spese correnti 22.99 Numero di unità di personale assunte come stagionali a progetto (l.296/2006

Lezione del giorno 30 aprile 2008 Corollario. Siano A un campo ed f(x) un polinomio non nullo in A[x] di

Calcolare la cardinalit` a del gruppo degli elementi invertibili del anello quoziente Z[X,

[r]

Corso di Laurea in Ingegneria Informatica e dell'Automazione. Anno