Aritmetica modulare/Congruenze lineari

Questo modulo tratta delle cosiddette congruenze lineari, ovvero le congruenze che coinvolgono polinomi di primo grado. In particolare sarà dimostrato il cosiddetto teorema cinese del resto, che riguarda la risolubilità di un sistema di congruenze lineari.

Congruenze semplici

Abbiamo già incontrato la congruenza lineare $ax\equiv 1\mod n$, stabilendo che è risolubile se e solo se a è coprimo con n. Una congruenza più generale è

$ax\equiv b\mod n$

che rappresenta la "congruenza lineare base". Una caratteristica importante di questa congruenza è che può avere un qualunque numero di soluzioni, eccetto infinito; tuttavia, se esistono soluzioni, è sempre possibile ridursi ad un'unica soluzione variando opportunamente il modulo n.

Una condizione necessaria e sufficiente perché la congruenza sia risolubile è che b sia un multiplo del massimo comun divisore tra a e n. La dimostrazione segue immediatamente dalle proprietà dell'identità di Bézout: risolvere $ax\equiv b\mod n$ equivale infatti a trovare x e y tali che

$ax+ny=b$

e questo è possibile se e solo se MCD(a,n)|b. Un altro modo di vedere la cosa, nel caso che a ed n siano coprimi, è osservare (in modo simile a quanto fatto nella dimostrazione del piccolo teorema di Fermat e del teorema di Eulero) che i numeri

$1a,2a,\ldots ,(n-1)a$

sono tutti distinti (altrimenti si avrebbe $(i-j)a\equiv 0\mod n$, e poiché MCD(a,n)=1, i = j) e diversi da 0. Quindi ogni elemento di $\mathbb {Z} _{n}$ appare tra quei numeri, ed esattamente uno è uguale a b.

Supponiamo ora che la congruenza sia risolubile, sia d =MCD(a,n), e poniamo a=Ad, n=Nd, b=Bd. Allora possiamo riscrivere $ax+ny=b$ come

$Adx+Ndy=Bd$

e semplificando d,

$Ax+Ny=B$

Poiché abbiamo tolto tutti i fattori comuni tra a ed n, abbiamo che A ed N sono coprimi, inoltre, portandoci nelle congruenza modulo N, abbiamo

$Ax\equiv B\mod N$

che ammette esattamente una soluzione, come dimostrato prima: sia ${\overline {x}}$. I valori

$x_{k}={\overline {x}}+kN$

sono ancora soluzioni delle congruenza per ogni valore intero di k (in particolare, $x_{0}={\overline {x}}$). Per k < d, inoltre, questi valori sono minori di n, e quindi sono incongruenti modulo n. Questi sono tutti e soli i valori minori di n che, modulo N, sono congrui a ${\overline {x}}$. Se y, modulo n, è diverso da tutti gli $x_{i}$, allora non è una soluzione della congruenza perché non vi sono altre soluzioni modulo N: quindi la congruenza originale ammette esattamente d soluzioni modulo n.

Sistemi di congruenze lineari

Una volta risolte congruenze in un unico modulo, è possibile passare a risolvere sistemi di congruenze lineari: la situazione di partenza è un sistema del tipo

${\begin{cases}x\equiv a_{1}\mod n_{1}\\x\equiv a_{2}\mod n_{2}\\\vdots \\x\equiv a_{k}\mod n_{k}\end{cases}}$

dove MCD(n_i,n_j)=1 per ogni $i\neq j$.

Ci si può sempre ridurre a questo caso a partire da un sistema in cui ogni equazione è del tipo

$a_{i}x\equiv b_{i}\mod n_{i}$

nel caso in cui in quest'ultima esistono soluzioni, risolvendo la congruenza lineare come nel paragrafo precedente, eventualmente modificando il modulo.

Poiché esistono $N=n_{1}n_{2}\cdots n_{k}$ diverse scelte di sequenze $(a_{1},a_{2}\ldots ,a_{k})$, è naturale cercare le soluzioni del sistema nel modulo N: dimostreremo che, in questo modulo, la soluzione esiste ed è unica.

Definiamo infatti $N_{i}={\frac {\prod _{j=1}^{k}n_{j}}{n_{i}}}$, ovvero il prodotto di tutti gli $n_{j}$ eccetto $n_{i}$: questo è ovviamente divisibile per tutti gli $n_{j}$, eccetto $n_{i}$, con cui è coprimo perché è il prodotto di fattori coprimi con $n_{i}$. Di conseguenza ogni $N_{i}$ ha un inverso modulo $n_{i}$; sia $N_{i}^{*}$. Consideriamo il numero

${\overline {x}}=a_{1}N_{1}N_{1}^{*}+a_{2}N_{2}N_{2}^{*}+\cdots +a_{k}N_{k}N_{k}^{*}$

Modulo $n_{i}$ (per ogni i), si cancellano tutti i termini meno $a_{i}N_{i}N_{i}^{*}$. Quindi

${\overline {x}}\equiv a_{i}N_{i}N_{i}^{*}\mod n_{i}\equiv a_{i}\mod n_{i}$

perché il prodotto $N_{i}N_{i}^{*}$ è per definizione, congruo a 1 modulo $n_{i}$. Quindi il numero ${\overline {x}}$ è una soluzione del sistema.

Abbiamo quindi N soluzioni diverse, una per ogni sequenza degli a. Consideriamo un'altra soluzione ${\overline {y}}$ del sistema. La differenza ${\overline {x}}-{\overline {y}}$ è congrua a 0 per ogni $n_{i}$, cioè è divisibile per ogni $n_{i}$, e quindi è divisibile per il loro prodotto N. Quindi la soluzione è unica modulo N.

Isomorfismi

Modulo 45 visto come modulo 9 per modulo 5

		mod 5
		0	1	2	3	4
mod 9	0	0	36	27	18	9
	1	10	1	37	28	19
	2	20	11	2	38	29
	3	30	21	12	3	39
	4	40	31	22	13	4
	5	5	41	32	23	14
	6	15	6	42	33	24
	7	25	16	7	43	34
	8	35	26	17	8	44

L'esistenza e l'unicità modulo N delle soluzioni dei sistemi di congruenze lineari permette di stabilire una corrispondenza biunivoca dal prodotto cartesiano $\mathbb {Z} _{n_{1}}\times \mathbb {Z} _{n_{2}}\times \cdots \times \mathbb {Z} _{n_{k}}$ a $\mathbb {Z} _{N}$ che, come si può vedere facilmente, rispetta le operazioni. In linguaggio algebrico, questo equivale a dire che c'è un isomorfismo tra il prodotto cartesiano e l'insieme $\mathbb {Z} _{N}$.

Questo può essere sfruttato per risolvere delle congruenze, ad esempio di un polinomio di grado elevato, da un modulo n qualsiasi a diversi moduli più piccoli. Ad esempio, volendo trovare le soluzioni di

$2x^{5}-6x^{4}+3x^{3}-5x+5\equiv 0\mod 15$

è possibile risolvere invece le due congruenze

$2x^{5}-6x^{4}+3x^{3}-5x+5\equiv 0\mod 3\Longrightarrow 2x^{5}-2x+2\equiv 0\mod 3$

$2x^{5}-6x^{4}+3x^{3}-5x+5\equiv 0\mod 5\Longrightarrow 2x^{5}-x^{4}+3x^{3}\equiv 0\mod 5$

Ora $x^{5}$ assume, per il piccolo teorema di Fermat, gli stessi valori di x; quindi la congruenza modulo 3 è impossibile, e così è quella originaria.

Questo sistema è utile per trovare il numero di soluzioni di un'equazione a partire dal numero di soluzioni della stessa equazione in moduli più piccoli: se ad esempio

$f(x)\equiv 0\mod n$

è spezzata in

${\begin{cases}f(x)\equiv 0\mod n_{1}\\f(x)\equiv 0\mod n_{2}\\\vdots \\f(x)\equiv 0\mod n_{k}\end{cases}}$

dove i vari moduli sono a due a due coprimi, e $\rho (n_{i})$ indica il numero di soluzioni della congruenza modulo $n_{i}$, allora $\rho (n)=\rho (n_{1})\rho (n_{2})\cdots \rho (n_{k})$ perché ogni possibile gruppo di soluzioni nei diversi moduli genera una diversa soluzione modulo n.

Un'applicazione: la funzione di Eulero

A partire da queste considerazioni si può provare che la funzione di Eulero è moltiplicativa, cioè per ogni a e b coprimi si ha

$\phi \left(ab\right)=\phi (a)\phi (b)$

Il punto di partenza è la considerazione che un numero n è coprimo con un prodotto ab se e solo se è coprimo sia con a che con b. Infatti, se i fattori di n sono distinti da quelli di ab, saranno a maggior ragione diversi sia da quelli di a che da quelli di b, viceversa, se i fattori di n non compaiono né nella fattorizzazione di a né in quella di b, non potranno essere in quella di ab.

Consideriamo ora un $x\in \mathbb {Z} _{ab}$: per quanto abbiamo detto prima, lo possiamo identificare come una coppia $y\in \mathbb {Z} _{a},~z\in \mathbb {Z} _{b}$ (dove a e b sono tra loro coprimi), e si ha che

$x\equiv y\mod a,~~~~x\equiv z\mod b$

Quindi, poiché ridurre modulo n non cambia l'essere coprimo con n, x è coprimo con ab se e solo se y è coprimo con a e z con b. Per quanto abbiamo dimostrato precedentemente, ogni coppia (y,z) di elementi coprimi (rispettivamente con a e b) corrisponde ad un unico x coprimo con ab e, viceversa, ogni x coprimo con ab corrispondente ad una coppia (y,z). Ora questo tipo di coppie sono $\phi \left(a\right)\phi (b)$ (essendo $\phi \left(n\right)$ la quantità di numeri minori di n coprimi con n), mentre il numero di x coprimi con ab è $\phi \left(ab\right)$; poiché questi due numeri sono uguali,

$\phi \left(ab\right)=\phi (a)\phi (b)$

per ogni coppia di a e b coprimi.

A partire da questo è facile calcolare il valore di $\phi \left(n\right)$ per ogni n: infatti questo può essere scomposto nel prodotto

$n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}$

dove i $p_{k}$ sono primi e diversi tra loro. A questo punto resta da calcolare solamente $\phi \left(p^{a}\right)$: ma questo è facile, perché gli unici numeri minori di $p^{a}$ e non coprimi con esso sono i multipli di p, e questi sono in numero di $p^{a-1}$; quindi $\phi \left(p^{a}\right)=p^{a}-p^{a-1}=p^{a-1}(p-1)$.

A questo punto si ottiene

$\phi (n)=p_{1}^{a_{1}-1}(p_{1}-1)p_{2}^{a_{2}-1}(p_{2}-1)\cdots p_{k}^{a_{k}-1}(p_{k}-1)$

o, in forma più elegante,

$\phi (n)=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{k}}}\right)$

Il lemma di Thue

Un'altra congruenza lineare interessante, questa volta nella due incognite x e y, è

$ax\equiv y\mod p$

dove p è un numero primo

È ovvio che questa congruenza ha p soluzioni, una per ogni scelta di x: il lemma di Thue afferma che esiste una coppia $(x_{0},y_{0})$ che la verifica tale che $|x_{0}|,|y_{0}|<{\sqrt {p}}$ ed entrambi sono diversi da 0.

Consideriamo infatti i numeri ax - y (modulo p) tali che

$0\leq x\leq [{\sqrt {p}}],~~0\leq y\leq [{\sqrt {p}}]$

dove [a] indica la parte intera di a, ovvero il più piccolo intero non maggiore di a. Questi valori sono in numero di $([{\sqrt {p}}]+1)^{2}>({\sqrt {p}}-1+1)^{2}=p$. Quindi esistono due coppie $(x_{1},y_{1})$ e $(x_{2},y_{2})$ tali che $ax_{1}-y_{1}\equiv ax_{2}-y_{2}\mod n$; inoltre $x_{1}\neq x_{2}$, perché altrimenti si avrebbe

${\begin{cases}ax_{1}-y_{1}\equiv c\mod p\\ax_{1}-y_{2}\equiv c\mod p\end{cases}}$

e quindi

$y_{1}\equiv ax_{1}-c\mod p$

e

$y_{2}\equiv ax_{1}-c\mod p$

ovvero $y_{1}=y_{2}$ e le coppie non sarebbero distinte. Consideriamo l'espressione

$a(x_{1}-x_{2})-(y_{1}-y_{2})=(ax_{1}-y_{1})-(ax_{2}-y_{2})$

Questa è palesemente congrua a 0 modulo n. $x_{1}-x_{2}$ è la differenza tra due quantità minori di $[{\sqrt {p}}]$, e quindi è essa stessa minore di $|{\sqrt {p}}|$. Allo stesso modo $y_{1}-y_{2}<{\sqrt {p}}$. Quindi ponendo

$x_{0}=x_{1}-x_{2},~~y_{0}=y_{1}-y_{2}$

si ha la coppia desiderata.

Questo lemma può essere usato per dimostrare il teorema di Fermat sulle somme di due quadrati, che afferma che un primo p è rappresentabile come somma di due quadrati se e solo se $p\equiv 1\mod 4$. La dimostrazione è presentata nell'ultimo modulo.