Congruenze esponenziali

# Congruenze esponenziali ###### tags: `md` #### Piccolo teorema di Fermat ###### Teorema Se $p$ è un numero primo e $a$ è un numero intero che non è un multiplo di $p$, allora vale $$ a^{p−1} \equiv 1 \; (p) $$ ###### Dimostrazione Dato un intero $a\not\equiv 0 \;(p)$ consideriamo i numeri $$ a,2a,...,(p−1)a $$ Questi $p−1$ numeri sono a due a due non congrui fra loro modulo $p$. Supponiamo infatti, per assurdo, che esistano $i$ e $j$ con $(0\le i < j\le p−1)$ tali che $ia\equiv ja\;(p)$ Ora sappiamo che $a$ ammette un inverso modulo $p$. Sia dunque $b$ un inverso di $a$. Moltiplicando per $b$ otteniamo: $$ iab\equiv jab\;(p) $$ ossia $$ i\equiv j \; (p) $$ Poiché avevamo supposto $0\le i < j\le p−1$ abbiamo trovato un assurdo. Dunque la lista $a,2a,...,(p−1)a$ comprende $p−1$ numeri i cui resti nella divisione per $p$ sono tutti diversi da $0$ e a due a due distinti. Allora i resti dei numeri $a,2a,...,(p−1)a$ sono esattamente, a meno di riordinarli, i numeri: $1,2,\ldots,(p−1)$ Possiamo dunque scrivere che $$ a\cdot(2a)\cdot(3a)\cdots((p−1)a)\equiv1\cdot2\cdot3\cdots(p−1)\;\;(p) $$ Questa congruenza, raccogliendo a sinistra i fattori uguali ad $a$, equivale alla seguente: $$ a^{p−1}\cdot1\cdot2\cdot3\cdots(p−1)\equiv1\cdot2\cdot3\cdots(p−1)\;\;(p) $$ Ora osserviamo che p−1 è invertibile modulo $p$ e moltiplichiamo entrambi i membri per un suo inverso. Otteniamo $$ a^{p−1}\cdot1\cdot2\cdot3\cdots(p−2)\equiv1\cdot2\cdot3\cdots(p−2)\;\;(p) $$ Poi moltiplichiamo entrambi i membri per un inverso di $p−2$, e così via. Alla fine troviamo $$ a^{p−1}\equiv1\;(p) $$ come volevamo dimostrare. ###### Dimostrazione Diamo adesso una diversa dimostrazione del piccolo teorema di Fermat dovuta ad Eulero. Per prima cosa dimostriamo che $p$ divide ${p\choose i}$ quando $0< i < p$. Infatti sappiamo che $$ {p\choose i}i! (p−i)! =p! $$ e, per il teorema di decomposizione unica in prodotto di fattori primi, $p$, che divide il membro di destra, deve dividere il membro di sinistra. Poiché $p$ non può dividere $i! (p−i)!$ (che sono prodotti di numeri positivi strettamente minori di $p$) possiamo dedurre, per la proprietà caratterizzante dei numeri primi (ossia quella che dice che se $p$ è primo e divide un prodotto $ab$ allora $p$ deve dividere $a$ o $p$ deve dividere $b$), che $p$ deve dividere ${p\choose i}$. A questo punto possiamo osservare che, dati due numeri interi $a$ e $b$, lo sviluppo del binomio $(a+b)^p$ ha, modulo $p$, una scrittura molto semplificata. Infatti vale $$ (a+b)^p=\sum^p_{i=0}{p\choose i}a^ib^{p−i}\equiv a^p+b^p\;(p) $$ dato che, appunto, $p$ divide tutti i coefficienti ${p\choose i} \text{ con } (0< i < p)$. In particolare, nel caso $b= 1$, abbiamo $$ (a+ 1)^p\equiv a^p+ 1\;\;(p) $$ Ora proviamo che, per ogni $a\in\mathbb{Z}$ vale $a^p\equiv a(p)$ Questa relazione, nel caso in cui $a$ non è multiplo di $p$, ci dà (dividendo per $a$) l'enunciato del teorema. Ci basta dimostrare che, per ogni $a\in\mathbb{N}$, $$ a^p\equiv a\;(p) $$ (il caso dei numeri negativi si ricava poi immediatamente). Lo dimostriamo per induzione su $a$. Il caso base, per $a= 0$, $$ 0^p≡0 \;(p) $$ è banale. Supponiamo ora che questa relazione sia vera fino ad $a=n$ e proviamo a dimostrare che $$ (n+ 1)^p\equiv n+ 1 \; (p) $$ (se ci riusciamo la nostra dimostrazione è terminata). Ora, per quanto visto sopra possiamo scrivere che $$ (n+ 1)^p\equiv n^p+ 1 (p) $$ Ma, per ipotesi induttiva, $n^p≡n\;(p)$ per cui $$ (n+ 1)^p\equiv n+ 1 \; (p) $$ ###### Corollario Se $p$ è un numero primo, per ogni numero intero a vale $$ a^p \equiv a \;(p) $$ ###### Dimostrazione Se $a$ non è multiplo di $p$ per il piccolo teorema di Fermat vale $$ a^{p−1}≡1 \;(p) $$ da cui si ottiene la tesi moltiplicando per $a$ entrambi i membri. È poi immediato verificare che se $a≡0 \;(p)$ allora la tesi è vera. ###### Corollario Se $n > 1$ è un numero intero tale che per qualche numero intero $a$ vale $$ a^n \not\equiv a \;(n) $$ allora $n$ non è primo. ###### Dimostrazione Si tratta della contronominale del corollario precedente. È interessante capire se con questi ragionamenti si può trovare un criterio per dire con certezza se un numero è primo (non solo per dire se un numero NON è primo). Saremmo infatti tentati di pensare che se prendiamo un numero intero $n >1$ e scopriamo che per tutti i numeri interi $a$ vale $$ a^n\equiv a\;(n) $$ allora $n$ è primo. Questo NON è vero: ci sono infiniti numeri che soddisfano questa proprietà ma non sono primi. #### Classi di resto ###### Notazione Per $i = 0,1,2,3,4,5,6,7,8,9$, chiamiamo $[i]_{10}$ l'insieme dei numeri interi la cui divisione per 10 dà resto $i$. $$ [i]_{10} = \{x \in \mathbb{Z} \;\;|\;\; x \equiv i \;(10)\} $$ Chiamiamo ora $\mathbb{Z}_{10}$ l'insieme i cui elementi sono tutte le classi di resto modulo $10$: $\mathbb{Z}_{10} = \{[0]_{10},[1]_{10},\ldots,[9]_{10}\}$ Ci mettiamo d'accordo di poter indicare una classe di resto $[i]_{10}$ anche col simbolo $[s]_{10}$ dove $s$ è un qualunque numero intero tale che $s \equiv i \;(10)$ Per esempio, $[127]_{10} = [7]_{10}$ Caso generale Sia $m$ un numero intero positivo. Per ogni $i = 0,1,2,...,m−1$ chiamiamo $[i]_m$ la "classe di resto di i modulo $m$", ossia l'insieme dei numeri che danno resto $i$ quando si considera la loro divisione euclidea per $m$: $$ [i]_m = {x \in \mathbb{Z} \;\;|\;\; x \equiv i \;(m)} $$ Chiamiamo $\mathbb{Z}_m$ l'insieme di tutte le classi di resto modulo $m$: $$ \mathbb{Z}_m = {[0]_m,[1]_m,...,[m−1]_m} $$ Si tratta dunque un insieme di cardinalità $m$. Come sopra adottiamo la convenzione per cui possiamo indicare la classe $[i]_m$ anche col simbolo $[s]_m$ dove $s$ è un qualunque numero intero tale che $s \equiv i \; (m)$ ###### Definizione Ora siamo pronti a deﬁnire la somma e la moltiplicazione di elementi di $\mathbb{Z}_{10}$. Poniamo: $$ [a]_{10} \cdot [b]_{10} = [ab]_{10} \\ [a]_{10} + [b]_{10} = [a+b]_{10} $$ Per esempio: $$ [7]_{10}\cdot [5]_{10}= [35]_{10}= [5]_{10} \\ [6]_{10}+ [8]_{10}= [14]_{10}= [4]_{10} $$ Caso generale Possiamo allora deﬁnire la somma e la moltiplicazione di elementi di $\mathbb{Z}_m$: $$ [a]_m \cdot [b]_m = [ab]_m \\ [a]_m + [b]_m = [a+b]_m $$ #### Applicazione RSA Consideriamo due numeri primi distinti $p$ e $q$, e prendiamo un numero $e$ che sia primo con $(p−1)(q−1)$. Sappiamo dunque che $e$ è invertibile modulo $(p−1)(q−1)$, e chiamiamo $d$ un suo inverso. La seguente semplice proposizione è il cuore del metodo di crittograﬁa che vogliamo descrivere: ###### Proposizione Dati $p,q,e,d$ come sopra, per ogni numero $m$ con $0 \le m < pq$ vale $$ (m^e)^d ≡ m \; (pq) $$ ###### Dimostrazione Osserviamo che per il teorema cinese del resto l'equazione $$ x\equiv m\;(pq) $$ è equivalente al sistema $$ \begin{cases} x\equiv m\;(p)\\ x\equiv m\;(q) \end{cases} $$ Dunque ci basta dimostrare che $(m^e)^d$ è una soluzione del sistema. Verifichiamo che $(m^e)^d$ è soluzione della prima equazione (per la seconda equazione si procederà in maniera del tutto analoga), ossia verifichiamo che è vera la congruenza: $$ (m^e)^d\equiv m\;(p) $$ Ora, se $p|m$ la congruenza appena scritta diventa $0\equiv 0 \; (p)$ che è vera. Se invece $p\not|\;m$ allora possiamo applicare il piccolo teorema di Fermat. Infatti per costruzione $$ ed\equiv 1\;((p−1)(q−1)) $$ dunque possiamo scrivere $$ ed= 1 +k(p−1)(q−1) $$ per un certo intero $k$. Allora $$ (m^e)^d=m^{ed}=m^{1+k(p−1)(q−1)}=m\cdot(m^{p−1})^{k(q−1)}\equiv \\ m\cdot 1^{k(q−1)}\equiv m\;(p) $$ dove abbiamo usato il piccolo teorema di Fermat per dire che $m^{p−1}\equiv 1 \; (p)$.