Richiamiamo la notazione vista in Zm. Sia
p(x) =
n
X
k=0
akxk∈ Z[x] (4.1)
Sia p un intero, primo, qualsiasi. Allora il polinomio p(x) =
n
X
k=0
[ak]pxk ∈ Zp[x] (4.2)
si dice la riduzione modulo p di p(x) e quindi
f : Zp → Zp (4.3)
`
e la corrispondente funzione polinomiale. Osserviamo che, a differenza di
quanto avveniva in Zm, ogni funzione f: Zp → Zp e`polinomiale, fondamen-
talmente perché Zp non ha divisori dello zero, vediamo. Diamo la seguente
Definizione.
Sia A un anello commutativo. Un elemento a ∈ A `e un divisore dello 0 se esiste un b6= 0 in A con a · b=0. Diremo anche che a divide 0.
Teorema 4.0.10.
Sia m un intero positivo e α = [a] una classe in Zm. Allora α `e un divisore
dello 0 se e solo se (a,m)>1.
Ora questa proprietá degli anelli finiti, che non siano campi, evidenzia un limite nel momento in cui considerato un certo polinomio vogliamo valutar- lo, attraverso la corrispondente funzione polinomiale, in un Zm qualsiasi. Ad
esempio, posto m=4, consideriamo il polinomio p(x)= a3x3 di terzo grado,
ora se consideriamo la corrispondente funzione polinomiale f(x)= [a3]4x3con
a3 6= 0, riscontriamo un comportamento un pó lacunoso, in quanto x3 ≡ 0
(mod 4) per x=2, ovvero per certi valori (appunto i divisori dello zero) ‘col- lassa’ il grado, contravvenendo alla stessa definizione di funzione polinomiale che assicura che la funzione ha grado n se il coefficente n-esimo `e diverso
dallo zero. In un campo Zp con p primo questo non succede mai perché vale
il Teorema di Fermat, per cui xp−1 ≡ 1 (mod p), con x intero qualsiasi, e la
congruenza xp−1 ≡ 0 (mod p) `e verificata soltanto nel caso in cui x=0.
Quindi considerato ci`o, poiché tutte le funzioni f: Zp → Zp sono polinomiali,
se le pensiamo come le funzioni biiettive del gruppo simmetrico, troviamo che questo insieme coincide con Sp. Ora, poiché vale
Teorema 4.0.11.
Sia A un insieme con n elementi, n>0. Allora S(A) ha n! elementi. Ovvero le biiezioni da un insieme finito A di ordine n in s`e stesso sono n!, quindi possiamo affermare che l’insieme dei polinomi biiettivi in Zp ha p!
elementi. A questo punto vogliamo individuare tali polinomi. Con questo intento possiamo restringere la nostra attenzione, senza perdere di generalitá, ai polinomi di grado ≤ p − 1 in quanto per il Teorema di Fermat vale
xp ≡ x ⇒ xp+1 ≡ x2 ⇒ xp+2 ≡ x3 ⇒ ...x2p−2≡ xp−1 (4.4)
cio`e ogni esponente maggiore di p si comporta nello stesso modo di un espo- nente piú piccolo, compreso tra 0 e p-1.
Iniziamo dal campo Z2, tenendo conto di (4.4) possiamo osservare che ci
sono i polinomi di primo grado della forma f(x)= ax+b e questi soltanto.
Tali polinomi formano un sottogruppo di Sp di ordine p(p-1). L’ordine del
sottogruppo di un gruppo finito, per il Teorema di Lagrange, deve dividere l’ordine del gruppo e p(p-1) `e dato dal numero delle disposizioni semplici di n elementi in k modi diversi, Dn,k = (n−k)!n! . Osserviamo infatti che gli ele-
menti di Z2 sono 0,1 e le possibili disposizioni o ‘collocazioni’ per questi due
elementi sono due, un elemento come coefficiente della x e un elemento come
termine noto, quindi 2!
(2−2)!, ricordando che 0!=1. Quindi in Z2 i polinomi
biiettivi sono solo due ( ricordiamo che ∀ˆa ∈ Z t.c a ≡ ˆa (mod m) vale ˆ
a∈ [a]m), ed entrambi di primo grado.
Vediamo in Z3. Ci saranno sempre i polinomi di primo grado, che rappresen-
tano sempre un sottogruppo di Sp di ordine p(p-1) ma ovviamente saranno
di piú per la precisione 3!
(3−2)! ovvero 6, dati dalle seguenti espressioni (tutte
le possibili disposizioni semplici degli elementi di Z3)
x, 2x, x+ 1, x+ 2, 2x + 1, 2x + 2
Ricordando che l’insieme dei polinomi biiettivi in un campo Zpcoincide con il
gruppo simmetrico Sp e che, per quanto osservato precedentemente, l’ordine
di Sp e`p!, concludiamo che tanto in Z2 quanto in Z3 i polinomi biiettivi sono
tutti e solo quelli di primo grado perché in entrambi i casi p!= p(p-1). Vediamo che ‘qualcosa‘ cambia in Z5 visto che 5!6= 5(5-1), ovvero il numero
dei polinomi di primo grado, che per la formula vista sopra `e 20, non satura
il numero dei polinomi biiettivi in Z5 che `e 5! ovvero 120. Comprendiamo
quindi che in Z5 ci sono anche polinomi biiettivi di grado > 1, vediamo in
dettaglio. In generale un polinomio di grado due del tipo ax2 + bx + c (a6=
0) `e biiettivo ⇔ ax2 + bx lo `e. Ora vediamo che ax2 + bx = x(ax+b) ha
due radici: [0]5 e -ba che (tenendo conto del fatto che in un campo tutti gli
elementi tranne lo zero sono invertibili) sará [˜b]5 · [a−1]5 dove ˜b ≡ -b (mod
5)). Dunque, volendo richiedere la biiettivitá, possiamo ammettere solo il caso in cui b = [0]5. Ma in questo caso, pur ottenendo il polinomio ax2, non
in particolare iniettivo, perché a · [12]
5 = a · [42]5 = a). Dunque i polinomi di
secondo grado non sono biiettivi. Che dire di quelli di terzo grado?
Consideriamo il polinomio ax3+ bx2+ cx + d (a6= 0) di terzo grado, anche in
questo caso osserviamo che ax3+ bx2+ cx + d `e biiettivo ⇔ ax3+ bx2+ cx
lo `e ⇔ x(x2+ b ax+ c a) lo `e. Ora posto b′ = ba; c′
= ca (a6= 0) consideriamo il polinomio x(x2+ b′
x+ c′
) che si annulla sicuramente in x=0, ora per la biiettivitá, x=0 deve essere l’unica radice, pertanto devono verificarsi uno dei due seguenti casi: o il polinomio x2 + b′
x+ c′
si annulla anch’esso in x=0 (e questo si verifica se e solo se c′
= [0]5) oppure il suo discriminante (b′)2 − 4c′ = (b′)2 + c′ (mod 5) non
deve essere un quadrato in Z5, ovvero il polinomio x2+ b ′
x+ c′
deve essere irriducibile in Z5. Vediamo che, posto ∆ = (b
′
)2 + c′
, non `e un quadrato
in Z5 quando ∆= 2, oppure ∆= 3, ovvero quando c
′
= 2 − (b′
)2 caso (1);
oppure c′
= 3 − (b′
)2 caso (2). Si distinguono i seguenti: caso (1) c′
= 2,1 e 3 per (b′
)2 = 0,1 e 4 rispettivamente (a meno di congruenze); caso (2) c′
= 3,2 e 4 per (b′
)2 = 0,1 e 2 rispettivamente (a meno di congruenze). Vediamo
la seguente tabella che indica i valori (di b′
e c′
) che devono comparire nel polinomio x2+ b′
x+ c′
affinché la condizione di biiettivitá sia soddisfatta
b′ c′ 0 2 1 1 2 3 3 3 4 1 oppure b′ c′ 0 3 1 2 2 4 3 4 4 2 Ci sono quindi le seguenti possibilitá
x(x2+ 2) x(x2 + x + 1) x(x2+ 2x + 3) x(x2+ 3x + 3) x(x2+ 4x + 1)
Ora per verifica diretta (ponendo x=0,1,2,3,4 (mod 5)) proviamo l’iniettivi
tá dei suddetti polinomi ad esempio prendendo il primo polinomio x(x2+2)
verifichiamo x x(x2+ 2) 0 0 1 3 2 2 3 3 4 2
Osserviamo che il polinomio assume lo stesso valore, 3, in corrispondenza di x=1, 3. Questo ci basta per scartarlo dalla lista dei polinomi biiettivi. Proce- dendo con tale verifica su tutti gli altri polinomi riscontriamo che risultano iniettivi i seguenti
x(x2+ 2x + 3) x(x2+ 3x + 3) x(x2+ x + 2) x(x2+ 2x + 4) (4.5)
Ora ricordando che avevamo posto b′
= ab; c′
= ac (a6= 0) e che il polinomio di partenza era ax3+ bx2+ cx + d, quindi moltiplicando tutti i polinomi della
lista (4.5) per a e sommando loro d (al variare di a e d in Z5) otteniamo
ben 20 diversi polinomi per ciascuno di essi, tale numero `e dato sempre da Dn,k = (n−k)!n! dove n= 5 ovvero tutti i possibili valori di a tra gli elementi del
campo, k=2 inteso come quantitá di modi attraverso i quali assegnare tali valori, uno per b′
e uno per c′
, quindi in totale avremo 80 polinomi biiettivi di terzo grado. Resta fuori il caso in cui b′
= c′
= 0 in corrispondenza dei quali valori troviamo il polinomio x(x2) che ha radice tripla x=0. Ora, al
variare di a e d in Z5 troveremo 20 polinomi del tipo ax3+ d, che vanno a
sommarsi agli 80 precedentemente individuati. Ora ricordando i 20 polino- mi lineari che avevamo riconosciuti come polinomi biiettivi, in apertura del
discorso, in totale avremo in Z5 ben 120 polinomi biiettivi, che `e il numero
che ci aspettavamo di trovare visto che l’insieme dei polinomi biiettivi di Z5
coincide con S5. Con questo riscontriamo anche che nessun altro polinomio
di grado ≤ 4 puó quindi essere biiettivo in Z5.
Diamo una tabella riassuntiva delle funzioni polinomiali di ordine piccolo sull’anello Zm per 1 ≤ m ≤ 10. Nella seconda riga c’`e il numero di elementi
dell’anello delle funzioni polinomiali. Nella terza riga l’ordine del gruppo Gm
di quelle biiettive e nella quarta il tipo di gruppo.
m 1 2 3 4 5 6 7 8 9 10 |PAn| 1 4 27 64 3125 108 7 7 1024 19683 12500 |Gm| 1 2 6 8 120 12 720 128 1296 240 Gm id S2 S3 D4 S5 D6 S7 2-Syl ? S2× S5 Legenda:
• Sme`il gruppo simmetrico su m elementi. Se m `e primo, allora Gm ∼= Sm
• Dm e`il gruppo delle simmetrie dell’ m-agono regolare.
• Per m = 8, poiché 8! = 27· 32 · 5 · 7, il gruppo G
8, di ordine 128 = 27, `e
uno dei 2-sottogruppi di Sylow di S8, e la sua struttura `e ben nota.
• Per m=9, G9 ha ordine 1296 = 24 · 34 e poiché 9!= 27· 34· 5 · 7, allora G9
contiene almeno uno dei 3-sottogruppi di Sylow di S9, ma la sua struttura `e
da determinare.
• Un teorema afferma che se n= m· q, con m e q coprimi, allora Gn∼=Gm×Gq.
Ne consegue che, per esempio, G6 ∼= G3×G2 ∼= S3×S2 ∼= D6. Analogamente,
G10 ∼= G2 × G5 ∼= S2× S5, d’ordine 2 · 120 = 240. Pertanto, la tabella per
l’ordine Gm si puó agevolmente ampliare, con l’esclusione delle potenze dei