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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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