Lezione 9 (31 marzo 2000 h. 9-11)

   
Elementi invertibili modulo n

Definizione 9.1   Sia $a \in \mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\t... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ diremo che a è invertibile se esiste $y\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ tale che a x = 1 (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$). L'insieme degli elementi invertibili di $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ si indica con $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$.

Proposizione 9.2   a è invertibile in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ se e solo se (a,n)=1.

Dimostrazione.  Segue immediatamente da proposizione 8.4, osservando che $(n,a)\mathrel{\big\vert}1$ se e solo se (n,a)=1.     $\square$

Corollario 9.3   Se p è primo, ogni elemento non nullo di $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ è invertibile.

Dimostrazione.  Se $a\ne0$ in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ allora $p\not\mathrel{\big\vert}a$ e quindi, dato che p è primo, (p,a)=1, da cui la tesi.     $\square$

Osservazione 9.4   Si osservi che se a è invertibile in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$, allora se $c,d\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\t... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ sono tali che ac=ad (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$) allora necessariamente c=d (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$). In quanto se x è tale che ax=1, allora

$$ac=ad \Rightarrow xac =xad \Rightarrow1c=1d\Rightarrow c=d.$$

In particolare se a è invertibile, allora da ab= si deduce che b=0. In generale tale conclusione non si può inferire se a non è invertibile, ad esempio $2\cdot 3 =2\cdot 0$ in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}6\mathbb Z}} {{}_{\!\scriptscriptstyle {}6\mathbb Z}}$, ma $3 \ne 0$ in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}6\mathbb Z}} {{}_{\!\scriptscriptstyle {}6\mathbb Z}}$. Se p è primo tutti gli elementi non nulli sono invertibili, e quindi se $a\ne0$ in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ allora ac=ad in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ implica che c=d (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$), in particolare ab=0 in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ implica che a=0 o b=0.

Proposizione 9.5   Siano x,y due inversi di a in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$, allora x=y (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$).

Dimostrazione. Dal fatto che ax=1, moltiplicando entrambi i membri per y, ed usando le proprietà associativa, commutativa e dell'1 si ottiene

y =1 y=( ax)y = (x a ) y = x ( a y ) = x 1 =x.

    $\square$

La proposizione precedente garantisce che se $a \in \mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\t... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ è invertibile, allora c'è un solo $x\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ tale che ax=1. Tale x viene chiamato l'inverso di a e viene denotato con a^-1.

Proposizione 9.6   Siano $u,v \in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$ allora $uv\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\te... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$.

Dimostrazione.  uv(v^-1u^-1)=u(vv^-1)u^-1=u1u^-1=uu^-1=1.     $\square$

Osservazione 9.7   Una immediata conseguenza della proposizione precedente, è che se si fissa $u\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$, allora è possibile definire la funzione $L_u:\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$ ponendo L_u(v)=uv, e t. Per quanto osservato sopra tale funzione risulta iniettiva, infatti L_u(v₁)=L_u(v₂) vuol dire che uv₁=uv₂, e dato che u è invertibile, v₁=v₂. Dato che l'insieme $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$ è finito, L_u è bigettiva.

   
Il piccolo teorema di Fermat

Dato un numnero naturale n si indica con $\Phi(n)$ il numero di naturali minori o uguali a n e coprimi con n. La funzione $\Phi$ si chiama funzione $\Phi$ di Eulero. La seguente proposizione è una conseguenza immediata di proposizione 9.2 e di proposizione 7.8.

Proposizione 9.8   Per ogni n>0, si ha che $\left\vert\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{... ...e {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*\right\vert=\Phi(n)$.

Teorema 9.9   Sia $u\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$ allora $u^{\Phi(n)}=1$ (in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$).

Dimostrazione.  Sia $k=\Phi(n)$, e siano $x_1,\dots,x_k$ tutti gli elementi di $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$, dato che l'applicazione L_u è bigettiva, allora $l_u(x_1),\dots, L_u(x_k)$ sono ancora tutti gli elementi di $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\textsty... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^*$, ma allora, per la commutatività del prodotto, $x_1x_2\dots x_k=L_u(x_1)L_u(x_2)\dots L_u(x_k)$ e quindi

$$x_1x_2\dots x_k=ux_u1x_2\dots ux_k = u^kx_1x_2\dots x_k$$

Da, questa uguaglianza, osservando che $x_1x_2\dots x_k$ è invertibile, ne segue che u^k=1.     $\square$

Corollario 9.10 (Piccolo teorema di Fermat)   Se p è un primo allora per ogni $x\ne0$ in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$ si ha che x^p-1=1 in $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb Z}} {{}_{\!\textsty... ...} {{}_{\!\scriptstyle {}p\mathbb Z}} {{}_{\!\scriptscriptstyle {}p\mathbb Z}}$.

Dimostrazione.  Segue immediatamente dal teorema precedente, osservando che se p è primo, allora tutti i numeri più piccoli di p sono coprimi con p, e quindi $\Phi(p)=p-1$.     $\square$

Esercizio 9.1    Si provi che se p è un primo allora per ogni intero x si ha che $x^p\cong x\quad{\rm mod}\ p$.
Soluzione

   
Crittografia RSA

Proposizione 9.11   Sia c coprimo con $\Phi(n)$, allora l'applicazione $C:\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}^8$ definita da $x\mapsto x^c$ è invertibile e la sua inversa è data da D(x)=x^d essendo $cd \cong 1\quad{\rm mod}\ \Phi(n)$.

Dimostrazione.  Se c è coprimo con $\Phi(n)$ allora esiste un d come nell'enunciato, ossia tale che $cd \cong 1\quad{\rm mod}\ \Phi(n)$, ma allora $cd = k\Phi(n)+1$ e quindi, usando la proposizione dimostrata precedentemente, per ogni $x\in\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb Z}} {{}_{\!\tex... ...} {{}_{\!\scriptstyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$ si ha

$$D(C(x))= (x^c)^d = x^{cd}=x^{\Phi(n)+1} = x (x^\Phi(n))^k = x 1^k = x.$$

Del tutto analoga è la prova che anche C(D(x))=x per ogni x, da cui la tesi.     $\square$

La proposizione appena dimostrarta è alla base del metodo RSA di crittografia a chiave pubblica. Supponiamo cha A debba trasmettere un messaggio riservato a B, allora B rende noti due numeri m e c (detti rispettivamente il modulo e la chiave di codifica), che hanno la proprietà $(c,\Phi(m))=1$. L'alfabeto della trasmissione sarà allora costituito da $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}m\mathbb Z}} {{}_{\!\textsty... ... {{}_{\!\scriptstyle {}m\mathbb Z}} {{}_{\!\scriptscriptstyle {}m\mathbb Z}}^*$ e la codifica sarà costituita da sostituire la lettera x con x^c (modulo m).

Il fatto che $(c,\Phi(m))=1$, garantisce che si può determinare un numero dtale che $cd\cong 1 \quad{\rm mod}\ \Phi(m)$, ossia tale che $cd = k\Phi(m)+1$. Per decodificare il messagio è allora sufficiente elevare alla potenza d, in quanto

$$(x^c)^d = x ^{cd}=x ^{k\Phi(m)=1}= (x^{\Phi(m)})^k x = 1^k x ... ...style {}m\mathbb Z}} {{}_{\!\scriptscriptstyle {}m\mathbb Z}}$$

Chiaramente chiunque conosca c e $\Phi(m)$ è in grado di determinare la chiave di decodifica d. Ma determinare $\Phi(m)$ è molto facile se si conosce la fattorizzazione in primi di m, e fattorizzare un intero è un problema computazionalmente molto complesso. Quindi soltanto chi ha costruito m e c è in grado di determinare d facilmente. I numeri che vengono usati sono in realtà del tipo m=pq con p,q primi, per i quali si ha $\Phi(m)=(p-1)(q-1)$ e per i quali, determinare $\Phi(m)$ a partire da m è equivalente a determinare la fattorizzazione di m.

Esercizio 9.2      Provare che se p,q sono primi allora $\Phi(pq)=(p-1)(q-1)$
Soluzione

Esercizio 9.3      Supponiamo che n=pq sia con p e q primi. Si provi che se si conoscono n e $\Phi(n)$ si possono determinare pe q.
Soluzione

Esercizio 9.4    Si risolvano, se possibile, le seguenti congruenze:

1.

$x^7\cong 3\quad{\rm mod}\ 11$

2.

$x^14 \cong 2 \quad{\rm mod}\ 45$

3.

$x^6 \cong 2 \quad{\rm mod}\ 13$

4.

$x^2+3x \cong 0 \quad{\rm mod}\ 17$

Soluzione