Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 Zm.
In Zm 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, Zm={ [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

e

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> = { gn | 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 (Zm ,+) è un gruppo ciclico finito di ordine m.
[1]m e [-1]m=[m-1]m sono generatori di (Zm ,+).
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, (Zm ,+ , ∙) è un anello commutativo unitario.
Lo studio della struttura dell’anello  (Zm ,+ , ∙) 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 (Zm , ∙)
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 (Zm , ∙) 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 (Zm , ∙)
⇒ 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 (Zm , ∙) .

Elementi invertibili modulo m

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

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

Dimostrazione
Si supponga in primo luogo che  (Zm , + , ∙) 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 Zm diverso da [0]m
⇒ [a]m è un elemento invertibile di Zm
⇒ a e m sono coprimi
⇒ a=± 1.
Dunque m è primo.

Elementi invertibili modulo m

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

Elementi invertibili modulo m

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

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

Allora U(Zm) è una parte stabile di (Zm , ∙)  e la struttura algebrica Zm* = (U(Zm) , ∙) è 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 |Zm*|=φ(m).
In seguito verranno presentate altre proprietà della funzione di Eulero.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion