Maria De Falco » 3.Struttura dell'anello degli interi modulo m, funzione di Eulero

Richiami sulle congruenze modulo m

Sia mє Z.
Si ricordi che:
(1) Se a e b sono numeri interi, si dice che a è congruo a b modulo m se a-b è un multiplo di m; in questo caso, si scrive a≡b (mod m).
(2) La relazione binaria così definita è una congruenza nell’anello (Z, +, ∙), che viene chiamata congruenza modulo m.
(3) La classe di equivalenza di un numero intero a viene indicata con il simbolo [a]_m e chiamata classe di congruenza di a modulo m; per ogni numero intero a, si ha [a]_m ={ a+km | kє Z}; in particolare, [0]_m coincide con l’insieme dei multipli di m.
(4) L’insieme quoziente { [a]_m | a є Z} viene indicato con il simbolo Z_m.
In Z_m si introducono le operazioni quoziente + e ∙ ponendo per ogni coppia (a,b) di numeri interi

[a]_m+[b]_m=[a+b]_m e [a]_m ∙ [b]_m=[a ∙ b]_m

(5) Se m≠0, allora ogni numero intero a è congruo modulo m al resto della divisione euclidea di a per m.
(6) Se m>1, Z_m={ [0]_m , [1]_m , … , [m-1]_m }.

Richiami sulle congruenze modulo m

Se un numero intero m è multiplo di un numero intero n, allora ovviamente [a]_m ⊆ [a]_n. Si ha inoltre
Proposizione 3.1
Sia m un numero intero tale che m>1. Se m=nt con n,t>1, allora per ogni numero intero a,

[a]_n = [a]_m U [a+n]_m U … U [a+(t-1)n]_m

l’insieme { [a]_m , [a+n]_m , … , [a+(t-1)n]_m ha } ha ordine t

Dimostrazione
Per ogni j=0,…, t-1, si ha [a+jn]_m ⊆ [a+jn]_n =[a]_n ,
⇒ [a]_m U [a+n]_m U … U [a+(t-1)n]_m ⊆ [a]_n .
Viceversa sia b un elemento di [a]_n e sia k un numero intero tale che b=a+kn. L’algoritmo della divisione euclidea applicato a k e t assicura che esistono q,r tali che k=tq+r con 0 ≤ r≤ t-1 ,
⇒ b=a+kn=a+mq+rn=(a+rn)+mq⇒ b è un elemento di [a+rn]_m .

Richiami sulle congruenze modulo m

Dunque [a]_n = [a]_m U [a+n]_m U … U [a+(t-1)n]_m
Siano ora i e j numeri interi tali che 0≤ i≤ j≤ t-1 e [a+in]_m = [a+jn]_m,
⇒ (j-i)n è un multiplo di m; d’altra parte 0≤ (j-i)n < tn=m
⇒ j-i=0.
Dunque l’insieme { [a]_m , [a+n]_m , … , [a+(t-1)n]_m } ha ordine t.

Primi richiami sui gruppi ciclici

I concetti presentati in questa slide fanno parte dei contenuti dei corsi di Algebra del primo anno, ma vengono esplicitamente richiamati, in quanto verranno più volte utilizzati nel seguito.
(1) Se G è un gruppo e gє G, allora <g> = { gⁿ | n є Z}.
Se il gruppo G è dato con notazione additiva, allora <g> = { n g | n є Z}.
(2) Sia G un gruppo e sia gє G.
Si dice che g è periodico se <g> è finito, e, in questo caso, l’ordine di <g> si chiama periodo di g.
Si dice invece che g è aperiodico se <g> è infinito.
(3) Si ricordi che un gruppo C si dice ciclico se esiste un elemento x di C tale che C=<x>; in questo caso si dice che x è un generatore di C.
(4) I sottogruppi e i quozienti di un gruppo ciclico sono ciclici.

Primi richiami sui gruppi ciclici

(5) Il gruppo (Z,+) è un gruppo ciclico infinito i cui unici generatori sono 1 e -1.
Se m è un numero intero, allora <m> coincide con l’insieme dei multipli di m.
Una parte non vuota H di Z è un sottogruppo di (Z,+) se e solo se esiste un intero m tale che H=<m>.
(6) Se m è un numero intero, il gruppo (Z_m ,+) è un gruppo ciclico finito di ordine m.
[1]_m e [-1]_m=[m-1]_m sono generatori di (Z_m ,+).
Nella Lezione 5 verranno descritte alcune proprietà dei gruppi ciclici finiti.

Anello degli interi modulo m

(Z ,+ , ∙) è un anello commutativo unitario; gli unici elementi invertibili di (Z , ∙) sono 1 e -1.
Per ogni numero intero m, (Z_m ,+ , ∙) è un anello commutativo unitario.
Lo studio della struttura dell’anello (Z_m ,+ , ∙) costituisce la branca dell’aritmetica detta aritmetica modulare, che ha molte applicazioni, non solo in crittografia, ma anche in diverse branche della matematica e dell’informatica.
Si affronterà ora il problema di individuare gli elementi invertibili di (Z_m , ∙)
Teorema 3.2
Sia m un numero intero tale che m >1, e sia a un numero intero. Allora:
(1) [a]_m è un elemento invertibile di (Z_m , ∙) se e solo se a e m sono coprimi.
(2) se a e m sono coprimi e u , v sono numeri interi tali che 1=au+mv, allora [u]_m=[a]_m^-1 .

Anello degli interi modulo m

Dimostrazione
Si supponga in primo luogo che [a]_m sia un elemento invertibile di (Z_m , ∙)
⇒ esiste un numero intero a’ tale che [a]_m ∙ [a']_m = [1]_m
⇒ aa’ ≡ 1 (mod m)
⇒ esiste un numero intero k tale che 1=aa’+km
⇒ 1 e -1 sono gli unici divisori comuni di a e m.
Viceversa, se a e m sono coprimi, allora esistono u,v є Z tali che au+mv=1
⇒ [a]_m ∙ [u]_m = [1]_m
⇒ [a]_m è un elemento invertibile di (Z_m , ∙) .

Elementi invertibili modulo m

Teorema 3.3
Sia m un numero intero tale che m>1.

(Z_m , + , ∙) è un campo se e solo se m è un numero primo.

Dimostrazione
Si supponga in primo luogo che (Z_m , + , ∙) sia un campo. Sia a un divisore di m tale che a sia diverso da m e da -m
⇒ a non è un multiplo di m
⇒ [a]_m è un elemento di Z_m diverso da [0]_m
⇒ [a]_m è un elemento invertibile di Z_m
⇒ a e m sono coprimi
⇒ a=± 1.
Dunque m è primo.

Elementi invertibili modulo m

Viceversa, si supponga che m sia primo.
Sia [a]_mun elemento di Z_m\{[0]_m}
⇒ a non è un multiplo di m
⇒ a e m sono coprimi
⇒ [a]_mè un elemento invertibile di (Z_m , ∙).
Dunque (Z_m , + , ∙) è un campo.

Elementi invertibili modulo m

Sia m un numero intero tale che m>1.
Con il simbolo U(Z_m ) si indica l’insieme

{ [a]_m є Z_m | [a]_m è un elemento invertibile di (Z_m , ∙) }.

Allora U(Z_m) è una parte stabile di (Z_m , ∙) e la struttura algebrica Z_m* = (U(Z_m) , ∙) è un gruppo.

Definizione della funzione di Eulero

Definizione 3.4
Si consideri la funzione φ definita ponendo:

φ (n)= |{ b є N tali che 1 ≤ b ≤ n e (b,n)=1}|

Tale funzione φ si chiama Funzione di Eulero.
Ovviamente, φ (1)=1 e se p è un numero primo positivo, φ(p)=p-1.
Più in generale, se p è un numero primo positivo e β è un numero naturale positivo, si ha
{b є N tali che 1 ≤ b ≤ p^β e (b,p^β)=1} =
= {b є N tali che 1 ≤ b ≤ p^β e p non divide b} =
= {b є N tali che 1 ≤ b ≤ p^β} \ {ph | 1 ≤ h ≤ p^β-1}
⇒ φ (p^β) = p^β – p^β-1 = p^β-1(p-1)
Segue dal Teorema 3.3 che |Z_m*|=φ(m).
In seguito verranno presentate altre proprietà della funzione di Eulero.