Matematica Discreta Lezione dei giorni 1,4,8,11,15,18 aprile 2011 Teorema. Una classe [a] del monoide Z

Matematica Discreta

Lezione dei giorni 1,4,8,11,15,18 aprile 2011

Teorema. Una classe [a] del monoide Z

, con il rappresentante a scelto fra 1,...,m-1, é simmetrizzabile rispetto al prodotto fra classi  il rappresentante a della classe é coprimo con il modulo m (ossia mcd(a,m)=1).

Dimostrazione:

(): Se [a] é simmetrizzabile, esiste il suo simmetrico [b] tale che [a][b]=[ab]=[1], dunque si ha la congruenza:

ab1 (mod m)

ossia m è un divisore della differenza (ab-1) dunque esiste un intero k tale che (ab-1)=mk, ossia:

1=ab-(mk)=ab+m(-k)

Si ottiene che 1 é combinazione lineare di a,m con coefficienti interi relativi b,-m, e ricordando che il mcd(a,m) é la minima combinazione lineare positiva di a,m (si ricava dalla dimostrazione del Teorema di esistenza del massimo comune divisore) si deduce che 1=mcd(a,m) e si ha la tesi.

(): Se 1=mcd(a,m), allora, per una proprietà del massimo comune divisore, 1 é combinazione lineare di a,m a con opportuni coefficienti interi relativi x,y

1=ax+my

Da ciò si ha ax-1=m(-y), dunque m é divisore della differenza (ax-1), ossia si ha la congruenza:

ax1 (mod m)

dunque in Z

sono uguali le classi [ax]=[1]

da cui [a][x]=[1]=elemento neutro, e si conclude che [a] é simmetrizzabile (con simmetrico [x]) cioé la tesi.

Il Teorema precedente risolve non solo il problema di caratterizzare quali sono gli elementi simmetrizzabili del monoide Z

rispetto al prodotto di classi, ma per ognuno di essi illustra un algoritmo per calcolare l’inverso (cioè il simmetrico):

1) data una classe [a][0] in Z

si calcola (con l’algoritmo Euclideo) il mcd(a,m) 2) se mcd(a.m)>1 allora si conclude che [a] non é simmetrizzabile

3) se mcd(a,m)=1, allora [a] è simmetrizzabile, ed il suo simmetrico è [x] dove x è il coefficiente di a nella rappresentazione di 1 come combinazione lineare di a,m a coefficienti interi relativi:

1 = ax+my  [a]

=[x]

Per il calcolo del coefficiente x (e quindi dell’inverso di [a]) si può usare egualmente l’algoritmo Euclideo delle divisioni successive.

Sappiamo che, dato un qualunque monoide A (rispetto ad una operazione *), il suo sottoinsieme A*, contenente gli elementi simmetrizzabili, è un gruppo rispetto alla stessa operazione.

In particolare, dato il monoide Z

={[0], [1], …., [m-1]} delle classi di congruenza modulo m (rispetto all’operazione di prodotto di classi), abbiamo dimostrato che gli elementi simmetrizzabili sono le classi con rappresentante a compreso fra 1,2,…..,m-1, tali che a,m siano coprimi.

Dunque il sottoinsieme degli elementi simmetrizzabile di Z

: Z

* = {[a] Z

/ a=1,2,….,m-1; a,m coprimi}

È un gruppo, rispetto all’operazione di prodotto di classi: ovviamente la sua cardinalità coincide con la funzione di Eulero (m) del modulo m:

 Z

* = (m) Esempio.

Dato il monoide Z

delle classi di congruenza modulo 9 rispetto all’operazione di prodotto di classi:

Z

= {[0],[1],[2],[3],[4],[5],[6],[7],[8]} (di cardinalità 9)

il gruppo degli elementi simmetrizzabile contiene le classi con rappresentante compreso fra 1 e 8 e coprimo con 9 ossia:

Z

*= {[1],[2],[4],[5],[7]} (di cardinalità (9)=6)

Ricordiamo i dettagli dell’algoritmo Euclideo delle divisioni successive (che, come detto, si può utilizzare anche per calcolare il simmetrico nel caso di un elemento simmetrizzabile del monoide Z

rispetto all’operazione di prodotto di classi).

Siano dati i numeri naturali a,b (con a>b): si effettua una prima divisione di a (dividendo) per b (divisore) ottenendo quoziente q

e resto r

, dove q

, r

sono interi 0, con r

<b; si effettuano poi successive divisioni con la regola seguente: effettuata la divisione numero k, se il resto è 0 l’algoritmo si arresta, mentre se il resto è >0 si effettua un’ulteriore divisione numero k+1, in cui il dividendo e il divisore sono rispettivamente il divisore e il resto della divisione numero k; l’ultimo resto non nullo è il mcd(a,b).

Schematizzando:

a=bq

+r

(q

0, 0<r

<b) b=r

q

+r

(q

0, 0<r

<r

) r

=r

q

+r

(q

0, 0<r

<r

) .

.

r

=r

q

+r

(q

0, 0<r

<r

) r

=mcd(a,b) r

=r

q

+r

(q

0, r

=0)

Parallelamente si possono calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by nel modo seguente:

si costruiscono le 2 successioni di numeri interi relativi

s

,s

,…..,s

; t

,t

,….,t

(dove n é il numero di divisioni dell’algoritmo Euclideo) ponendo

s

=1, s

=0, s

=s

-s

q

(per ogni i>1);

t

=0, t

=0, t

=t

-t

q

(per ogni i>1)

dove q

è il quoziente della divisione numero (i-1) nell’algoritmo Euclideo.

Basta poi porre x=s

,y=t

per avere i coefficienti x, y (x è il coefficiente di a; y quello di b).

Esempio.

Verifichiamo se [33] è simmetrizzabile nel monoide Z

(rispetto al prodotto di classi) e in caso affermativo calcoliamone il simmetrico.

Calcoliamo il mcd(88,33). Utilizzando l’algoritmo Euclideo si effettuano n=5 divisioni con i seguenti valori di quoziente e resto:

q

=2, r

=23; q

=1, r

=10; q

=2, r

=3; q

=3, r

=1; q

=3, r

=0

Si conclude che mcd(89,33)=r

=1, dunque [33] è simmetrizzabile in Z

.

Calcolando le successioni s

, t

si ottiene s

=-10, t

=27, dunque la rappresentazione di 1 come combinazione lineare di 89,33 è 1=89x+33y, con x= -10, y=27.

In particolare si ottiene che [33] è simmetrizzabile in Z

con simmetrico [27] (perché 27 è il coefficiente di 33 nella combinazione lineare).

Facendo in effetti i calcoli si ottiene [33][27]=[3327]=[891]=[1] (perché 1 è il resto della divisione

di 891 per il modulo 89).

Leggi di cancellazione in un gruppo Sia A un gruppo rispetto all’operazione *.

Affermiamo che:

dati comunque gli elementi a,b,cA tali che a*c=b*c allora si ha necessariamente a=b

(è la cosiddetta legge di cancellazione a destra, perché il secondo operando c viene “cancellato a destra” in ambo i membri dell’eguaglianza).

Dimostriamo tale legge di cancellazione: se eA è l’elemento neutro di A, e se c’A è il simmetrico di c in A, si ha (utilizzando la proprietà associativa insieme con l’ipotesi a*c=b*c ):

a=a*e=a*(c*c’)=(a*c)*c’=(b*c)*c’=b*(c*c’)=b*e=b dunque a=b (tesi).

Con ragionamento analogo si ottiene la cosiddetta legge di cancellazione a sinistra valida in ogni gruppo A:

dati comunque gli elementi a,b,cA tali che c*a=c*b allora si ha necessariamente a=b.

Notare che se A non è gruppo, tali leggi di cancellazione possono anche non valere.

Per esempio nel monoide Z

delle classi di congruenza modulo 4 rispetto al prodotto di classi si ha:

[2][3]=[6]=[2]=[2][1]

eppure non è vero che [3]=[1] (quindi non si può “cancellare” l’operando [2] nei due membri dell’eguaglianza).

Una conseguenza delle leggi di cancellazione è la seguente: se A é un gruppo finito di cardinalità n, la tavola dell’operazione di A forma un quadrato latino di ordine n.

Infatti sappiamo che se gli n elementi distinti di A sono ordinati come segue A = {a

,a

,...,a

}

allora la tavola dell’operazione di A é una matrice nxn in cui nella generica casella all’incrocio fra riga i e colonna j vi é il risultato a

*a

. Se per assurdo non si ottenesse in tal modo un quadrato latino, vi sarebbero 2 elementi uguali nella stessa riga o nella stessa colonna. Ma se per esempio per assudo vi fossero 2 elementi uguali nella stessa riga i (in due diverse colonne j,k) allora si avrebbe la seguente eguaglianza:

a

*a

a

*a

e per la legge di cancellazione a sinistra si concluderebbe che a

=a

(contraddizione perché gli elementi a

,a

,...,a

sono distinti). Con ragionamento analogo, se vi fossero invece per assurdo 2 elementi uguali nella stessa colonna, si otterrebbe una contraddizione (utilizzando stavolta la legge di cancellazione a destra).

Dunque un modo per ottenere un quadrato latino di ordine n é per esempio quello di costruire la tavola dell’operazione di un qualunque gruppo di cardinalità n.

Notiamo anche che per ogni numero naturale n abbiamo a disposizione gruppi di cardinalità n: per esempio il gruppo Z

delle classi di congruenza modulo n rispetto all’operazione di somma di classi.

Potenza di un elemento di un gruppo ad esponente intero non negativo.

Siano A un gruppo rispetto all’operazione * ed aA un elemento fissato.

Vogliamo definire il concetto di potenza di base a ed esponente intero non negativo, in modo analogo a quanto si fa per le ordinarie potenze numeriche.

Per ogni numero naturale kN definiamo la potenza a

di a con esponente k nel modo seguente:

a

= a*a*….*a (dove il numero degli operandi coincide con l’esponente k) Dunque:

a

=a, a

=a*a, a

=a*a*a etc…

(notare che la validità della proprietà associativa ci permette di non specificare come si associano

gli operandi: per esempio a

=(a*a)*a = a*(a*a)).

Estendiamo poi convenzionalmente la definizione di potenza anche al caso di un esponente nullo, definendo: a

= e (elemento neutro di A).

Esempio:

Consideriamo il gruppo delle classi di congruenza modulo 20 rispetto all’operazione di somma di classi:

Z

= { [0],[1],[2],[3],….,[19] } e fissiamo a=[3].

Allora per esempio:

[3]

=[3]+[3]+[3]=[3+3+3]=[9]

[3]

=[3]+[3]+[3]+[3]+[3]+[3]+[3]+[3]=[3+3+3+3+3+3+3+3]=[24]=[4]

(perché 4 è il resto della divisione di 24 per 20) [3]

=[0] (perché [0] è l’elemento neutro).

Consideriamo invece il gruppo delle classi di congruenza modulo 20 che sono simmetrizzabili rispetto all’operazione di prodotto di classi (sappiamo che sono le classi [a] con a=1,2,…..,19 e tali che mcd(a,20)=1):

Z

* = {[1],[3],[7],[9],[11],[13],[17],[19]}

e fissiamo di nuovo a=[3].

Allora per esempio:

[3]

=[3][3][3]=[333]=[27]=[7]

(perché 7 è il resto della divisione di 27 per 20).

[3]

=[1] (perché [1] è l’elemento neutro).

Esempio:

Consideriamo il gruppo F(X)* delle funzioni biunivoche da un insieme X in sé stesso, dove X={a,b,c} ha cardinalità 3, rispetto all’operazione di composizione di funzioni.

Fissiamo la funzione biunivoca f: X  X definita da f(a)=b, f(b)=c, f(c)=a: dunque f è elemento del gruppo F(X)*.

Si ha allora, per esempio:

f

=i

=funzione identica di X (perché è l’elemento neutro rispetto alla composizione di funzioni) f

=ff dove ff: X  X è la funzione biunivoca definita da:

(ff)(a)=f(f(a))=f(b)=c, (ff)(b)=f(f(b))=f(c)=a, (ff)(c)=f(f(c))=f(a)=b

Per le potenze di un elemento a di un gruppo A valgono le analoghe proprietà delle potenze numeriche.

Comunque presi gli interi non negativi h,k si ha:

1) (a

)*(a

)=a

2) (a

)

=a

Dimostriamo per esempio la 1), distinguendo 3 casi e in ognuno di essi dimostrando la tesi:

caso 1: h=0; allora (indicato con eA il neutro di A) (a

)*(a

)=(a

)*(a

)=e*(a

)=a

=a

=a

; caso 2: k=0 (dimostrazione simile)

caso 3: h,k>0; allora (a

)*(a

)=(a*a*…*a)*(a*a*…*a) (dove nella prima parentesi vi sono h operandi, nella seconda k operandi), dunque (a

)*(a

)=a*a*…*a (con un totale di h+k operandi) e si conclude che (a

)*(a

)=a

anche in questo caso.

La dimostrazione della 2) segue uno schema simile.

Teorema. Se A è un gruppo finito di cardinalità n con elemento neutro eA, fissato un elemento aA esiste sempre qualche intero k>0, kn tale che a

= e.

Dimostrazione:

Consideriamo le seguenti potenze di a:

a

, a

, ……….., a

Tali elementi di A non sono tutti distinti (se così fosse sarebbero n+1 elementi distinti di A, in contraddizione con l’ipotesi che n è la cardinalità di A), dunque esistono almeno 2 interi t,s tali che ts, 0t,sn, a

= a

. Supponiamo per esempio t>s (se t<s si ragiona in modo analogo).

Se s=0 si ha la tesi, perché allora a

= a

= e, con t>0, tn, e il valore di k cercato è k=t.

Supponiamo dunque s>0.

Allora da a

= a

segue a

= e*a

, e poiché a

= a*a*……*a (con t operandi), a

= a*a*……*a (con s operandi), applicando s volte la legge di cancellazione a destra (valida nel gruppo A):

a

= e con t-s>0, t-stn

Si ottiene anche in questo caso la tesi, scegliendo k=t-s.

Se A è un gruppo finito di cardinalità n con elemento neutro eA, e se fissiamo un elemento aA, per il Teorema precedente esistono esponenti positivi kn tali che a

=e, dunque (per l’Assioma del minimo) possiamo considerare il più piccolo intero positivo kn tale che a

= e, detto periodo dell’elemento a.

Notiamo anche che ovviamente il periodo dell’elemento neutro è sempre k=1 perché e

= e.

Esempio. Consideriamo il gruppo delle classi di congruenza modulo 18 che sono simmetrizzabili rispetto all’operazione di prodotto di classi ([a] con a=1,2,…..,17 e tali che mcd(a,18)=1):

Z

* = {[1],[5],[7],[11],[13],[17]}

e calcoliamo per esempio il periodo dell’elemento a=[7], cioè il minimo intero positivo k tale che [7]

= [1] (perché [1] è in questo caso l’elemento neutro del gruppo).

Si ha:

[7]

= [7];

[7]

= [7][7] = [77] = [49] = [13] (perché 13 è il resto della divisione di 49 per 18);

[7]

= [7]

[7]

= [13][7] = [137] = [91] = [1] (perché 1 è il resto della divisione di 91 per 18) Dunque k=3 è il periodo dell’elemento a=[7] nel gruppo Z

*.

Facendo i calcoli per tutti gli elementi di Z

* si ottengono i seguenti risultati:

[1] ha periodo 1;

[17] ha periodo 2;

[7], [13] hanno periodo 3;

[5], [11] hanno periodo 6.

Si può notare in questo esempio che non solo il periodo di ogni elemento è  della cardinalità 6 del gruppo, ma è anche divisore della cardinalità 6 del gruppo (dimostreremo in seguito che ciò non è casuale).

Se A è un gruppo finito di cardinalità n con elemento neutro eA, abbiamo definito periodo di un elemento aA il minimo intero positivo kn tale che a

=e.

Ovviamente possono esistere altri esponenti h (oltre il periodo k) tali che a

=e, ma essi dipendono dal periodo k, come afferma il prossimo risultato:

Teorema. Sia A un gruppo finito con elemento neutro eA, e sia aA un elemento di periodo k.

Per ogni intero h0 si ha:

a

= e  h è multiplo del periodo k

Dimostrazione:

(): Se h=0 è ovvio che h è multiplo di k. Sia dunque h>0, e dividiamo h per k mediante

l’algoritmo della divisione per i numeri naturali: esistono interi q,r0 tali che h=kq+r con r<k.

Se per assurdo h non fosse multiplo di k, sarebbe r0, dunque r>0, ed inoltre:

e = a

= a

=(a

)

*a

= e

*a

= e*a

= a

con 0<r<k contraddizione perché k è il minimo intero positivo tale che a

= e.

(): Per ipotesi esiste un intero t0 tale che h=kt, da cui a

= a

= (a

)

= e

= e.

Teorema (Lagrange). Sia A un gruppo commutativo finito di cardinalità n, con elemento neutro eA.

Allora per ogni elemento aA si ha:

1) a

= e

2) il periodo k di a è divisore della cardinalità n del gruppo.

Dimostrazione:

1) Fissato aA, si definisca la funzione f: A  A ponendo f(x)=a*x per ogni xA.

La funzione f è iniettiva: infatti se per assurdo esistessero b,cA, bc, tali che f(b)=f(c) si avrebbe a*b=a*c, e per la legge di cancellazione a sinistra si otterrebbe b=c, contraddizione.

Essendo dominio e codominio finiti di eguale cardinalità, f è anche surgettiva (dunque biunivoca).

Se a

,a

,…,a

sono gli n elementi distinti di G, le immagini degli elementi a

,a

,…,a

di A:

f(a

)=a*a

, f(a

)=a*a

,…, f(a

)=a*a

sono tutti gli elementi di A (per la surgettività di f).

Dunque (dal punto di vista insiemistico):

A = { a*a

, a*a

,…, a*a

} = {a

,a

,…,a

}

(sono elenchi degli stessi elementi anche se non necessariamente nello stesso ordine).

Per la proprietà commutativa si ha:

(a*a

)*(a*a

)*……*(a*a

) = a

*a

*……*a

= e*a

*a

*……*a

Di nuovo per la proprietà commutativa (applicata al primo membro):

(a

)*(a

*a

*……*a

) = e*(a

*a

*……*a

)

e per la legge di cancellazione a destra si ha la tesi a

= e.

2) Per la 1) si ha a

=e: per il Teorema precedente ciò implica che il periodo k di a è divisore dell’esponente n.

Nota: Si può dimostrare, con altre tecniche, che la tesi del Teorema vale anche nel caso di un gruppo (finito) non commutativo. Quindi in tutti i gruppi finiti elevando qualunque elemento alla cardinalità del gruppo si ottiene sempre l’elemento neutro ed il periodo di ogni elemento è divisore della cardinalità del gruppo.

Vedremo ora una importante conseguenza di questi risultati sull’aritmetica dei numeri naturali.

Teorema di Eulero-Fermat. Siano a,n due numeri naturali, con n>1, e supponiamo a,n coprimi (quindi mcd(a,n)=1). Allora, se (n) è la funzione di Eulero di n, si ha:

a

1 (mod n).

Dimostrazione:

Sappiamo che il gruppo commutativo finito A = Z

* (contenente le classi di congruenza modulo n simmetrizzabili rispetto al prodotto di classi) ha cardinalità (n) perché contiene le classi [a] con il rappresentante a coprimo con n.

In particolare, essendo a,n coprimi per ipotesi, si ha [a]A.

Per il Teorema precedente, ogni elemento di un gruppo finito commutativo elevato alla cardinalità del gruppo dà come risultato l’elemento neutro: nel nostro caso si ha

[1]=[a]

=[a][a]….[a]=[aa….a]=[a

], da cui la tesi a

1 (mod n).

Corollario (Piccolo Teorema di Fermat).

Siano a,n due numeri naturali, e supponiamo che n sia un numero primo ed n non sia divisore di a.

Allora si ha:

a

1 (mod n).

Dimostrazione:

Notiamo che i numeri a,n sono coprimi (perché le uniche possibilità per il mcd(a,n) sono 1, n, e la possibilità mcd(a,n)=n è da escludere essendo n non divisore di a per ipotesi).

Poiché (n)=n-1 (perché n è primo) la tesi segue immediatamente dal Teorema di Eulero-Fermat.

Risoluzione di congruenze lineari

Una congruenza lineare nell’incognita x è un’equazione della forma ax  b(mod n ) con a,b,n numeri naturali,.vogliamo trovare, se esistono, interi che verificano questa congruenza.

Osserviamo che:

1) una congruenza lineare può non avere soluzioni, come per esempio le congruenze 2x  1(mod4) o 2x  3 (mod 4) (non hanno soluzioni perché 1,3 sono numeri dispari);

2) se la congruenza ax  b(mod n) ha una soluzione x

ne ha infinite: infatti per ogni k numero intero x

+ kn è una soluzione della stessa congruenza ,

perché a(x

+ kn)  ax

 b(mod n); per questo motivo quando si contano le eventuali soluzioni della congruenza ax  b (mod n) si contano solo quelle che non sono congrue tra loro modulo n, per esempio la congruenza 2x  0 (mod 4) ha x = 0 e x = 2 come soluzioni e dimostreremo che sono solo queste;

3) data la congruenza ax  b(mod n), possiamo pensare a e b ridotti modulo n perché se a’= amod n e b’ = bmod n la congruenza a’x  b’ (mod n) è equivalente a quella data( nel senso che ha le stesse soluzioni): infatti se x

è un intero tale che a’x

 b’ (modn), si ha a’x

 ax

 b’ b(mod n); per esempio la congruenza 24x  21 (mod 9) è equivalente alla congruenza 6x  3(mod 9) che come dimostreremo ha soltanto le soluzioni 2,5,8 modulo 9;

4) trovare una soluzione x

della congruenza ax  b (mod n) ha come conseguenza di trovare una soluzione negli interi dell’equazione in due variabili ax + ny = b: infatti da

ax

 b(mod n) segue ax

= b+ kn cioè ax

+ n(-k) = b (- k si trova dall’equazione di primo grado in y ax

+ ny = b);

5) se a,b,n sono divisibili per uno stesso numero naturale d, la congruenza ax  b (mod n) è equivalente alla congruenza a/dx  b/d (mod n/d).

Teorema La congruenza lineare ax = b (mod n) ha soluzioni se e solo se mcd(a,n ) è un divisore di b.

Dimostrazione. Se x

è una soluzione della congruenza data , si ha ax

= b + kn con k intero, cioè b = ax

+ (-k)n e da questa uguaglianza si ricava che mcd(a,n) deve dividere b.

Viceversa supponiamo che d = mcd(a,n) sia un divisore di b,allora a = d a/d , b = d b/d, n = d n/d. Poichè mcd(a/d, n/d) = 1, [a/d] ha inverso nel gruppo Z

* , quindi esiste [c] tale che [a/d] [c] = [1] cioè a/d c  1(mod n).

Per l’osservazione 5) la congruenza data è equivalente alla congruenza

a/d x  b/d(mod n/d) e si ha a/d ( c b/d)  b/d(mod n/d) ,quindi x

= c b/d è una soluzione della congruenza data.

Esempi 1) La congruenza 4x 6 (mod 10) ha soluzioni perché mcd(4,10) è un divisore di 6 ed è equivalente alla congruenza 2x 3 (mod 5),come nella dimostrazione del teorema calcoliamo l’inverso di [2] in Z

che è [3] , una soluzione è x

=9 ( si noti che 4,9 sono due soluzioni della congruenza data che non sono congrue modulo 10).

2) La congruenza 6x  9 (mod15) ha soluzioni ed è equivalente alla stessa congruenza

dell’esercizio 1) 2x 3 (mod 5),in questo caso si noti che 4,9,14 sono soluzioni della

congruenza data non congrue modulo 15.

Nel prossimo teorema si determinano tutte le soluzioni (se esistono ) della congruenza lineare ax  b (modn ),contando quelle non congrue modulo n.

Teorema Se la congruenza lineare ax  b(modn ) ha una soluzione x

, tutte le altre soluzioni sono i numeri x

+ k n/d per ogni k intero, d = mcd (a,n).

Tra queste soluzioni i numeri x

, x

+ n/d, x

+ 2n/d, x

+ 3n/d,….., x

+ (d-1)n/d non sono congrui modulo n e ogni altra soluzione è congrua a una di queste modulo n,quindi la congruenza data ha d soluzioni distinte modulo n.

Dimostrazione. Se ax

 b(mod n),allora per ogni k numero intero a(x

+ k n/d)   ax

+( k a/d) n  ax

 b(mod n).

Per dimostrare che ogni soluzione è di questo tipo , supponiamo che x

’ sia un’altra soluzione della congruenza data, allora ax

= b + hn e ax

’ = b + kn , sottraendo si ottiene a( x

’ – x

) = ( k-h)n, dividendo per d = mcd (a,n) si ha a/d (x

’ – x

) = (k- h) n/d. Da questa uguaglianza si ha che n/d divide il prodotto a/d ( x

’ – x

) e poiché mcd (n/d,a/d) = 1

n/d deve dividere (x

’ – x

) cioè x

’ x

(mod n/d).

Dimostriamo adesso che due soluzioni x

+ h n/d e x

+ k n/d con h,k scelti fra 0 e d-1 non sono congrue modulo n, se per assurdo lo fossero avremmo ( supponendo h maggiore di k) (h-k) n/d = t n con t0 e dividendo per n/d avremmo l’uguaglianza assurda (h-k) = t d essendo h-k  hd.

Per finire consideriamo una soluzione x

+ h n/d con h d, dividendo

h per d abbiamo h = d q + r con 0  r d e sostituendo x

+ h n/d  x

+ (qd + r ) n/d   x

+ qn + r n/d  x

+ r n/d (modulo n).

Come conseguenza di questo teorema si ha che la congruenza ax  b (modn) ha una sola soluzione se e solo se mcd(a,n) = 1.

Crittografia.

E’ la scienza che studia la possibilità che un soggetto A (mittente) spedisca un messaggio ad un utente B (destinatario) attraverso un canale di comunicazione non sicuro, in modo che per un soggetto C (intruso), che sia in grado di intercettare il messaggio, sia “difficile” conoscere le informazioni in esso contenuto.

In un sistema crittografico il messaggio originale (detto messaggio in chiaro) prima di essere trasmesso dal mittente A viene opportunamente modificato (la cosiddetta cifratura che trasforma il messaggio in chiaro in un messaggio cifrato); è il messaggio cifrato che viene trasmesso lungo il canale di comunicazione: quando il destinatario B lo riceve, ne effettua una opportuna modifica (la cosiddetta decifratura) che fornisce come risultato il messaggio in chiaro originale.

Anticamente il concetto di ”messaggio” era ristretto ad un messaggio di tipo “testuale”, cioè costituito da caratteri alfabetici.

Poiché il messaggio può sempre essere suddiviso in “blocchi” (che poi il destinatario dovrà

“incollare” per riottenere l’intera informazione originale) potremo anche in certi casi identificare il concetto di messaggio con il singolo carattere alfabetico: la cifratura e la decifratura opereranno in questo caso sulle singole lettere del testo.

Se vogliamo formalizzare la struttura di un sistema crittografico, servendoci della teoria degli

insiemi, possiamo dire che si possono individuare un insieme finito X dei messaggi in chiaro, un

insieme finito Y dei messaggi cifrati (in molti casi concreti gli insiemi X,Y saranno uguali), una funzione di cifratura f : X  Y (che trasforma ogni messaggio in chiaro xX in un messaggio cifrato y=f(x)X) e in una funzione di decifratura g : Y  X (che ritrasforma il messaggio cifrato y=f(x)Y nel messaggio in chiaro x=g(y)X).

Dal punto di vista insiemistico, la proprietà della funzione di decifratura g si traduce nel fatto che per ogni messaggio in chiaro xX si deve avere g(f(x))=x, dunque la composizione gf deve coincidere con la funzione identica i

dell’insieme X.

Vedremo dagli esempi che la funzione di cifratura e la funzione di decifratura si servono di elementi ausiliari (detti rispettivamente chiavi di cifratura e chiavi di decifratura) che sono utilizzati nella trasformazione di un messaggio in chiaro in messaggio cifrato e nella ritrasformazione di un messaggio cifrato nel messaggio in chiaro da cui esso proveniva.

Il sistema crittografico di Cesare.

E’ un sistema crittografico molto semplice (ma poco sicuro) che pare fosse utilizzato dagli antichi Romani.

Supponiamo che l’insieme dei messaggi in chiaro X e quello dei messaggi cifrati Y coincidano entrambi con l’insieme delle 21 lettere dell’alfabeto italiano:

X = Y = {A,B,C,D,E,F,G,H,I,L,M,N,O,P,Q,R,S,T,U,V,Z}

Diamo un valore numerico intero compreso fra 0 e 20 alle lettere: A=0, B=1, C=2,…., Z=20.

Fissiamo una lettera dell’alfabeto (sarà la chiave di cifratura del nostro sistema crittografico) e calcoliamo il suo valore numerico a con 0a20 (tale valore numerico è detto offset); definiamo poi la funzione di cifratura f : X  Y nel modo seguente: disponiamo in modo “circolare” gli elementi di X (in modo che la lettera successiva alla Z sia la A), e per ogni messaggio in chiaro xX (dunque x è una delle 21 lettere dell’alfabeto) definiamo il messaggio cifrato y=f(x) uguale a quella lettera che si trova (a partire dalla lettera x) spostandosi di a posizioni lungo l’alfabeto in verso orario.

Per esempio se la chiave di cifratura è la lettera D con valore numerico a=3, e se x=E allora f(E)=H (la lettera H si trova 3 posizioni più avanti rispetto alla lettera E). Ovviamente non ha molto senso scegliere come chiave di cifratura la lettera A con offset a=0, in quanto la cifratura di ogni lettera la lascerebbe invariata.

La funzione di decifratura g : Y  X utilizza una chiave di decifratura uguale a quella di cifratura, ed è definita nel modo seguente: dato yY (quindi y è una delle 21 lettere dell’alfabeto) si definisce g(y) uguale a quella lettera che si trova (a partire dalla lettera y) spostandosi di a posizioni lungo l’alfabeto in verso antiorario.

E’ ovvio che, se y=g(x) è la cifratura del messaggio in chiaro x, g(y) coincide con il messaggio in chiaro originale x.

Per rendere operativamente più semplice la cifratura, il mittente scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso destra di a posizioni (se a è l’offset cioè il valore numerico della chiave di cifratura) sempre pensando ad una struttura “circolare”: sotto ogni lettera x si trova la sua cifratura f(x).

Per esempio nel caso a=3 (chiave di cifratura è la lettera D):

A B C D E F G H I L M N O P Q R S T U V Z

D E F G H I L M N O P Q R S T U V Z A B C

In questo caso, per cifrare il testo in chiaro “ATTACCATESUBITO” applicando ad ogni lettera del testo la funzione f di cifratura, si ottiene il seguente testo cifrato (da trasmettere lungo il canale di comunicazione):

“DZZDFFDZHVAENZR”

Analogamente, per rendere operativamente più semplice la decifratura, il destinatario scrive, sotto la successione delle lettere dell’alfabeto, la stessa successione “shiftata” verso sinistra di a posizioni: sotto ogni lettera y si trova la sua decifratura g(y).

Nell’esempio precedente (con a=3):

A B C D E F G H I L M N O P Q R S T U V Z

U V Z A B C D E F G H I L M N O P Q R S T

Decifrando il testo ricevuto “DZZDFFDZHVAENZR” (lettera per lettera) si riottiene il testo originale “ATTACCATESUBITO”.

Come abbiamo visto, nel sistema crittografico di Cesare la chiave di cifratura coincide con quella di decifratura, e ovviamente deve essere concordata in anticipo fra il mittente e il destinatario.

Il sistema di Cesare è poco sicuro: l’intruso che intercetti il messaggio cifrato, potrebbe cercare di

risalire al messaggio in chiaro con il metodo della “forza bruta”, provando a decifrare il messaggio

con tutte le possibili chiavi (che sono in tutto 21) fino ad ottenere un messaggio che abbia un senso

compiuto.