Aritmetica modulare/Congruenze lineari

Indice del libro

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 modifica

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

 

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   equivale infatti a trovare x e y tali che

 

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

 

sono tutti distinti (altrimenti si avrebbe  , e poiché MCD(a,n)=1, i = j) e diversi da 0. Quindi ogni elemento di   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   come

 

e semplificando d,

 

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

 

che ammette esattamente una soluzione, come dimostrato prima: sia  . I valori

 

sono ancora soluzioni delle congruenza per ogni valore intero di k (in particolare,  ). 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  . Se y, modulo n, è diverso da tutti gli  , 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 modifica

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

 

dove MCD(ni,nj)=1 per ogni  .

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

 

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

Poiché esistono   diverse scelte di sequenze  , è naturale cercare le soluzioni del sistema nel modulo N: dimostreremo che, in questo modulo, la soluzione esiste ed è unica.

Definiamo infatti  , ovvero il prodotto di tutti gli   eccetto  : questo è ovviamente divisibile per tutti gli  , eccetto  , con cui è coprimo perché è il prodotto di fattori coprimi con  . Di conseguenza ogni   ha un inverso modulo  ; sia  . Consideriamo il numero

 

Modulo   (per ogni i), si cancellano tutti i termini meno  . Quindi

 

perché il prodotto   è per definizione, congruo a 1 modulo  . Quindi il numero   è una soluzione del sistema.

Abbiamo quindi N soluzioni diverse, una per ogni sequenza degli a. Consideriamo un'altra soluzione   del sistema. La differenza   è congrua a 0 per ogni  , cioè è divisibile per ogni  , e quindi è divisibile per il loro prodotto N. Quindi la soluzione è unica modulo N.

Isomorfismi modifica

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   a   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  .

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

 

è possibile risolvere invece le due congruenze

 
 

Ora   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

 

è spezzata in

 

dove i vari moduli sono a due a due coprimi, e   indica il numero di soluzioni della congruenza modulo  , allora   perché ogni possibile gruppo di soluzioni nei diversi moduli genera una diversa soluzione modulo n.

Un'applicazione: la funzione di Eulero modifica

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

 

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  : per quanto abbiamo detto prima, lo possiamo identificare come una coppia   (dove a e b sono tra loro coprimi), e si ha che

 

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   (essendo   la quantità di numeri minori di n coprimi con n), mentre il numero di x coprimi con ab è  ; poiché questi due numeri sono uguali,

 

per ogni coppia di a e b coprimi.

A partire da questo è facile calcolare il valore di   per ogni n: infatti questo può essere scomposto nel prodotto

 

dove i   sono primi e diversi tra loro. A questo punto resta da calcolare solamente  : ma questo è facile, perché gli unici numeri minori di   e non coprimi con esso sono i multipli di p, e questi sono in numero di  ; quindi  .

A questo punto si ottiene

 

o, in forma più elegante,

 

Il lemma di Thue modifica

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

 

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   che la verifica tale che   ed entrambi sono diversi da 0.

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

 

dove [a] indica la parte intera di a, ovvero il più piccolo intero non maggiore di a. Questi valori sono in numero di  . Quindi esistono due coppie   e   tali che  ; inoltre  , perché altrimenti si avrebbe

 

e quindi

 

e

 

ovvero   e le coppie non sarebbero distinte. Consideriamo l'espressione

 

Questa è palesemente congrua a 0 modulo n.   è la differenza tra due quantità minori di  , e quindi è essa stessa minore di  . Allo stesso modo  . Quindi ponendo

 

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  . La dimostrazione è presentata nell'ultimo modulo.