Lezione 13 (3 aprile 2001 h. 16.30-17.30)

   
Equazioni lineari modulo n

Osservazione 13.1   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 13.2   Siano $a,b\in\mathbb Z$, allora esiste un intero x tale che

$$a x \cong b \quad{\rm mod}\ n$$

se e solo se $(a,n)\mathrel{\big\vert}b$.

Dimostrazione.  Se $a x \cong b \quad{\rm mod}\ n$ allora $n\mathrel{\big\vert}(ax-b)$ quindi esiste k tale che ax-b=kn ossia b=ax-kn e quindi $(a,n)\mathrel{\big\vert}b$.

Viceversa supponiamo che $(a,n)\mathrel{\big\vert}b$. Siano $\alpha,\beta$ tali che $(a,n)=\alpha a +\beta n$, e sia k tale che b = k(a,n) allora $b = k(\alpha a +\beta n)$ e quindi $n\mathrel{\big\vert}(a (k\alpha) -b)$, ossia $k\alpha$ è una soluzione della congruenza.     $\square$

Osservazione 13.3   La dimostrazione precedente dà un metodo operativo per trovare una soluzione della congruenza, basta usare l'algoritmo di Euclide per determinare $\alpha$ e $\beta$ in modo che $(a,n)=\alpha a +\beta n$.

Esercizio 13.1      Si provi che quando ha soluzione, la congruenza $a x \cong b \quad{\rm mod}\ n$ è equivalente alla congruenza

$$a' x \cong b' \quad{\rm mod}\ n'$$

essendo a'=a/(a,n), b'=b/(a,n), n'=n/(a,n). (Con equivalente si intende che hanno le stesse soluzioni).
Soluzione

Proposizione 13.4   Siano $a,b\in\mathbb Z$, e sia $n\in\mathbb N$ tale che (a,n)=1 allora l'insieme degli x tali che $a x \cong b \quad{\rm mod}\ n$ sono una classe di congruenza modulo n.

Dimostrazione.  La congruenza ha soluzioni per quanto visto sopra. Passando alle classi di congruenza, si ha che se x è una soluzione, allora $\left[a\right]_n\left[x\right]_n =\left[b\right]_n$ e dato che a è invertibile, questo implica, moltiplicando entrambi membri per $\left[a\right]_n^{-1}$, che $\left[x\right]_n=\left[a\right]_n^{-1}\left[b\right]_n$, da cui la tesi.     $\square$

Osservazione 13.5   La proposizione 13.4 e l'esercizio 13.1 forniscono un metodo per trovare tutte le soluzioni di un'equazione lineare.

   
Il piccolo teorema di Fermat

Proposizione 13.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 13.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.

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 12.3 e di proposizione 11.13.

Proposizione 13.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 13.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 13.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 13.2    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 13.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 13.3      Provare che se p,q sono primi allora $\Phi(pq)=(p-1)(q-1)$
Soluzione

Esercizio 13.4      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 13.5    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