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}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$, allora se $c,d\in\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$ sono tali che $ac=ad$ (in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$) allora necessariamente $c=d$ (in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$). In quanto se $x$ è tale che $ax=1$, allora

$$ac=ad \Rightarrow xac =xad \Rightarrow 1c=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}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}}$, ma $3 \ne 0$ in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\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}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}p\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}p\mathbb{Z}}}$ allora $ac=ad$ in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}p\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}p\mathbb{Z}}}$ implica che $c=d$ (in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}p\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}p\mathbb{Z}}}$), in particolare $ab=0$ in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\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$.

Se $x_0$ è una soluzione della congruenza, allora, detto $n'=n/(a,n)$, l'insieme delle soluzioni è dato da:

$$\left[x_0\right]_{n'} = \{ x_0+k n'\mid k\in \mathbb{Z}\}$$

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.

Proviamo ora che l'insieme delle soluzioni è proprio $\left[x_0\right]_{n'}$. Proviamo innanzitutto che se $x_1\in\left[x_0\right]_{n'}$ allora è una soluzione della congruenza, infatti $x_1 = x_0+kn'$ quindi $ax_1= ax_0 + kan/(a,n)$ da cui $ax_1- ax_0 = + kan/(a,n)$ ma allora, dato che $a/(a,n)\in\mathbb{Z}$, $n$ è un multiplo di $kan/(a,n)$, ovvero

$$% latex2html id marker 10095ax_1\cong ax_0\quad{\rm mod} n.$$

Dato che $ax_0\cong b \quad{\rm mod}\ n$, questo basta per concludere che anche $ax_1\cong b \quad{\rm mod}\ n$.

Viceversa se $ax_1\cong b \quad{\rm mod}\ n$ allora $ax_1\cong ax_2\quad{\rm mod}\ n$ da cui si ricava che $a(x_1-x_0)\cong 0\quad{\rm mod} n$, ovvero $n\mathrel{\big\vert}a(x_1-x_0)$. Ma allora, dato che $n'\mathrel{\big\vert}n$, anche $n' \mathrel{\big\vert}a'(x_1-x_0)$, essendo $a'=a/(n,a)$. Ma allora, dato che per la proposizione 9.12 $(n',a')=1$, usando la proposizione 10.1, $n'\mathrel{\big\vert}(x_1-x_0)$. Questo conclude la dimostrazione.     $\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 intere).
Soluzione

Esercizio 13.2   Si provi che se $n'\mathrel{\big\vert}n$ e $x\in\mathbb{Z}$ allora $\left[x\right]_n\subseteq \left[x\right]_{n'}$.

Detto $d=n/n'$ si provi che

$$\left[x\right]_{n'} = \bigcup _{i=0}^{d-1}\left[x+in'\right]_n$$

e che per ogni $0\le i\ne j \le d-1$ si ha che $\left[x+in'\right]_n\ne\left[x+jn'\right]_n$.
Soluzione

Esercizio 13.3   Si usi l'esercizio prexcedente per provare che se $(a,n)\mathrel{\big\vert}b$ allora esistono esattamente $(a,n)$ classi di congruenza $X\in \mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$ tali che $\left[a\right]_nX=\left[b\right]_n$.
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}}} {{}_{\!\... ...{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}^*$.

Dimostrazione.  $uv(v^{-1}u^{-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}}} {{}_{\!\t... ...{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}^*$, allora è possibile definire la funzione $L_u:\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\t... ...{}_{\!\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_1)=L_u(v_2)$ vuol dire che $uv_1=uv_2$, e dato che $u$ è invertibile, $v_1=v_2$. Dato che l'insieme $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\texts... ...{}_{\!\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}}} {{}... ...{}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}}} {{}_{\!\t... ...{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}^*$ allora $u^{\Phi(n)}=1$ (in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\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}}} {{}_{\!\texts... ...{}_{\!\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}}} {{}_{\!\texts... ...{}_{\!\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}}} {{}_{\!\texts... ... {{}_{\!\scriptstyle {}p\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}p\mathbb{Z}}}$ si ha che $x^{p-1}=1$ in $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}p\mathbb{Z}}} {{}_{\!\texts... ... {{}_{\!\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.4   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}}} {{}_{\!\tex... ...{}_{\!\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}}} {{}_{\!\t... ... {{}_{\!\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}}} {{}_{\!\texts... ...{}_{\!\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 $d$ tale 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... ...yle {}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.5   Provare che se $p,q$ sono primi allora $\Phi(pq)=(p-1)(q-1)$
Soluzione

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

Esercizio 13.7   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