Le classi di resto modulo n

Cosa sono le classi di resto modulo n ? Cosa sono le congruenze ? Che cosa centra il piccolo teorema di Fermat ?

Disquisitiones Arithmeticae

Nel 1798 Carl Friederich Gauss all’età di 21 anni scrisse in latino un libro intitolato disquisitiones arimeticae (disquisizioni aritmetiche); il libro in realtà fu pubblicato nel 1801 ma nulla toglie alle capacità precoci di questo matematico che poi divenne noto come il Principe dei matematici.

L’opera è un riassunto di tutti i risultati allora noti di teoria dei numeri esposti in modo organico, correggendo alcune dimostrazioni e riempendo alcune lacune. Insomma una cosa simile a ciò che fece Euclide per la geometria.

Oggi esistono delle traduzioni in inglese e in francese ma, inaspettatamente, non esiste una traduzione in italiano: peccato.

I primi 4 capitoli sono dedicati alle congruenze che oggi chiamiamo anche classi di resto modulo n, anche se n è il nome di un parametro che potremmo chiamare in qualsiasi modo, e che in teoria dei gruppi vengono generalizzate come classi laterali, in inglese coset (coinsiemi).

Vediamo nel dettaglio di cosa si tratta.

Il modulo n

Prendiamo un intero positivo, chiamiamolo modulo ed indichiamolo con n.

Ora prendiamo gli interi a distanza di un modulo l’uno dall’altro, otteniamo una cosa come nel disegno qui sotto:

Il disegno si riferisce al modulo 5, la prima riga sono i numeri interi ma dobbiamo focalizzarci sullo 0, 5, tutti i numeri a distanza di 5 quindi 10, 15, ecc ed in senso opposto -5, -10, ecc.

nella seconda riga i punti sono sempre distanziati di un modulo ma partendo da 1

nella terza riga si parte da 2, nella terza si parte da 3 e nella quarta si parte da 4.

Nell’ultima riga si partirebbe da 5 ma si ottiene ancora la prima riga.

In generale, per n intero positivo, avremo n righe: 0, 1, …, n-1.

Le n classi

Ogni riga ottenuta nel disegno precedente forma un insieme di interi, li possiamo indicare con il numero di partenza ed utilizzare i seguenti simboli:

[0] \space [1] \dots [n-1] \newline \{0\} \space \{1\} \dots \{n-1\} \space

alcuni testi usano la notazione con le parentesi quadre alcuni le graffe, non c’è nessuna differenza ma io preferisco le quadre.

Le classi sono insiemi di numeri, possiamo specificarli meglio algebricamente:

r \in \{0, 1, \dots, n-1\}\newline a \in [r] \newline a=nq+r \quad q \in \Z

fissato un r preso tra 0 e n-1 ed aggiungendo i multipli interi del modulo n, si generano tutti gli elementi a della classe [r].

È ovvio che le classi non hanno elementi comuni e partizionano gli interi in n insiemi.

In un altro post ho spiegato le classi di equivalenza, una classe di equivalenza ed il partizionamento di un insieme sono la stessa cosa, quale relazione lega gli elementi di una stessa classe? Prima di tutto gli diamo un nome: congruenza e gli associamo un simbolo, appartenere alla stessa classe significa essere congruenti:

a, b \in [r] \newline a \equiv b \newline a = b \pmod n

a volte la congruenza si scrive con le tre linee sovrapposte, a volte con un semplice uguale seguito da qualche cosa che espliciti il modulo, a volte nella seconda scrittura si sostituisce l’uguale con il simbolo delle tre linee, di tutto un po’; io utilizzo le tre linee esplicitando il modulo solo se serve.

Appartenere allo stesso insieme implica banalmente le seguenti proprietà per la congruenza:

a, b \in [r] \quad b, c \in [r] \newline a \equiv a \newline a \equiv b \quad b \equiv a \newline a \equiv b \quad b \equiv c \rArr a \equiv c

la prima dice che un numero è congruente a sé stesso, la seconda è la proprietà simmetrica, la terza è la transitiva. Tutte insieme dicono che la congruenza è una relazione di equivalenza. Non ci vedo nulla da dimostrare per cui va bene così.

Tutto ciò spiega perché gli insiemi che partizionano gli interi si chiamano classi di equivalenza secondo il modulo n. Rimane da spiegare perché si chiamano classi di resti.

I resti

Prendiamo un elemento generico a della classe [r]:

a=nq+r

Proviamo a dividere a per n. Essendo numeri interi, si ottiene q con resto r; come abbiamo imparato alle elementari.

Al variare di q si ottengono tutti i numeri a che danno resto r nella divisione per il modulo n; direi che ora è chiaro il perché del nome.

Notiamo che i resti stessi appartengono alla classe e che potremmo utilizzare un elemento qualsiasi della classe per indicarla, non ci sono elementi comuni. Quindi niente ambiguità.

I resti che vanno da 0 a n-1 io li chiamo ridotti, per distinguerli dagli altri numeri che possono rappresentare la classe, infatti togliendo un multiplo opportuno di n da un elemento della classe si arriva ad un punto in cui non è possibile sottrarne ancora, quello che rimane è il resto della divisione o resto ridotto come lo chiamo io.

Secondo questa convenzione abbiamo:

[0]=[n]

infatti l’elemento n indicato nella classe di destra è divisibile per n con resto 0, quindi appartiene alla classe di sinistra.

Prendiamo due elementi della stessa classe, abbiamo:

a, b \in [r] \newline a=nq+r \quad b=np+r \newline a-b=n(q-p)

quindi la differenza è divisibile per il modulo.

Il primo capitolo del libro di Gauss inizia come segue, essendo in latino vi porto una mia libera traduzione:

Se un numero a divide la differenza dei numeri b e c, b e c sono detti congruenti relativi ad a; altrimenti, b e c sono noncongruenti. Il numero a è chiamato il modulo. Se i numeri b e c sono congruenti, ognuno di loro è chiamato residuo dell’altro. Se non sono congruenti sono detti nonresidui.

La definizione di Gauss di congruenza è:

b\equiv c \newline b-c=ak

il che significa che due numeri sono congruenti se la differenza è divisibile per il modulo.

Pari e dispari

C’è un’idea che conosciamo tutti, i numeri pari ed i numeri dispari. Ci sono un paio di modi per definire cosa sono i numeri pari: sono i numeri interi divisibili per 2. I dispari invece no. Ecco, i pari sono ben definiti mentre i dispari per esclusione.

Cosa significa divisibile per 2 ? Bene, si prende un intero, lo si divide per 2 e se il resto è 0 allora è pari altrimenti è dispari.

Un’altro modo di vedere la cosa è uno sì e uno no. Cioè 1 è dispari, il successivo, 2 , è pari, il successivo 3 è dispari, il successivo 4 è pari, ecc.

Osserviamo ora che se un numero è divisibile per 2 è nella forma 2k con k un intero qualsiasi, di conseguenza il suo successivo è 2k+1 che quindi è dispari. Proviamo a vedere il successivo ancora cioè:

(2k+1)+1=2k+2=2(k+1)

che essendo un multiplo di 2 è banalmente pari.

Otteniamo che un dispari si può definire come il numero che diviso per 2 ha resto 1. Un pari invece ha come resto 0.

Abbiamo così diviso i numeri in due classi, quelli con resto 0 quando vengono divisi per 2 chiamati numeri pari e quelli con resto 1 quando vengono divisi per 2 chiamati numeri dispari.

Guardando la definizione di classi di resto troviamo una bella somiglianza, infatti i pari e i dispari sono i resti delle classi modulo 2, la classe [0] contiene i multipli di 2 quindi i pari, la classe [1] contiene i multipli di 2 sommati a 1 quindi i dispari.

Possiamo anche vedere le classi di resto come una generalizzazione dei pari e dispari.

Sistemiamo un dettaglio

Abbiamo detto che il modulo è un numero positivo. Per il modulo 2 abbiamo i pari e dispari. Proviamo con il modulo 1. In questo caso la divisione per 1 fornisce solo il resto 0. Guardando il disegno iniziale vediamo che i numeri a distanza di modulo 1 sono i numeri interi stessi. Si ottiene solo una classe dunque, la classe [0] che coincide con l’insieme dei numeri interi.

Normalmente, il modulo 1 viene considerato un caso banale.

Gruppi

Ho già scritto un post sui gruppi, quando Gauss scrisse il suo libro questo concetto non era ancora chiaro, io approfitto di questo concetto invece per sistemare le classi nel contesto dei gruppi in modo che fin dall’inizio sia chiaro di cosa si tratta.

Un gruppo è un insieme in cui è definita un’operazione che sia associativa, non necessariamente commutativa, che esista un elemento neutro come lo 0 o l’1, che per ogni elemento esista un anti elemento come l’opposto o l’inverso. Utilizzerò questa idea di gruppo per quanto segue.

Somma di classi

Prendiamo due interi a, b di cui conosciamo i resti r e s rispetto ad un modulo n: cosa possiamo dire del resto della somma dei due numeri cioè a+b ?

a \in [r], b \in [s] \newline a=nq+r \quad b=np+s \newline a+b=n(q+p)+(r+s) \newline

dall’ultima equazione vediamo che a+b e r+s sono congruenti, la differenza è divisibile per n,

[a+b]=[r+s] \newline a+b \equiv r+s

Bisogna fare attenzione che r+s non è in generale un resto ridotto, ma si può ridurre sottraendo n un po’ di volte, quanto basta.

Tutto ciò apre la strada ad una definizione di somma tra classi,

[r]\pmb{+}[s]:=[r+s]

Il simbolo + a sinistra è la somma tra classi che definiamo tramite il membro a destra. Il membro a destra è la classe individuata da r+s.

Dal fatto che la somma di numeri è commutativa e associativa segue che la somma tra classi è commutativa e associativa, è abbastanza banale. Ciò che non è banale è stabilire chi sono gli elementi opposti e l’elemento neutro.

Prendiamo la classe di resti 0, supponiamo sia s=0 nella definizione precedente, in tal caso r+0=r e quindi possiamo dire che la classe [0] si comporta come elemento neutro; bene.

Ora cerchiamo di capire chi è l’elemento opposto di una classe qualsiasi [r]. Se cerchiamo l’elemento s per cui r+s=0 andiamo fuori strada infatti i resti ridotti sono numeri positivi e quindi non possono fare zero.

Come ne usciamo ? Non è possibile ? Bisogna ancora investigare una cosa, in realtà non dobbiamo ottenere r+s=0 bensì che r+s sia un multiplo del modulo n, in questo caso la somma appartiene alla classe [0] e questo ci basta.

Con questa osservazione in mente ci basta ed avanza che sia s=n-r, in questo caso r+s=r+(n-r)=n e quindi appartiene alla classe [0]. In simboli:

[r]\pmb{+}[n-r]=[0]

Cosa abbiamo ottenuto ? Abbiamo ottenuto che le classi formano, rispetto alla somma definita, un gruppo abeliano. Ecco un risultato inaspettato e per nulla ovvio ai tempi di Gauss: bravo.

Quanto fa pari + dispari ?

Nel caso del modulo n=2 abbiamo due classi che abbiamo chiamato pari e dispari. Alla luce di quanto detto possiamo fare la somma, vedere chi dei due è l’elemento neutro e chi l’opposto, proviamo.

Chiamiamo le due classi P e D e facciamo la somma:

P:=[0] \quad D:=[1] \newline P+P=[0] +[0] =[0+0]=[0] =P \newline P+D=[0] +[1] =[0+1]=[1] =D \newline D+P=[1] +[0] =[1+0]=[1] =D \newline D+D=[1] +[1] =[1+1]=[0] =P \newline

si noti che nell’ultima riga 1+1=2 ma sottraendo il modulo n=2 una volta otteniamo 0 e quindi il risultato.

La seconda e la terza riga dimostrano che la somma è commutativa come ci si aspetta ma anche che P è l’elemento neutro perché lascia invariato D. Rimane da stabilire chi è l’elemento opposto di D e la risposta è: D! Infatti l’ultima riga mostra che sommando D a sé stesso si ottiene l’elemento neutro P.

Quello che viene detto è che presi ad esempio due numeri, uno pari ed uno dispari e sommandoli si ottiene un numero dispari, mentre sommando due numeri dispari si ottiene un numero pari; infine sommando due numeri pari si ottiene un numero pari.

Moduli maggiori di 2

Dall’esempio precedente dovrebbe scaturire un’irrefrenabile curiosità per moduli maggiori di 2; non a tutti a dire il vero scatta questa curiosità.

Con modulo 3 possiamo costruire la seguente tabella:

\def\arraystretch{1.5} \begin{array}{c:c:c:c} \pmb{+} & \pmb{[0]} & \pmb{[1]} & \pmb{[2]}\\ \hdashline \pmb{[0]} & [0] & [1] & [2]\\ \hdashline \pmb{[1]} &[1] & [2] & [0] \\ \hdashline \pmb{[2]} & [2] & [0] & [1]\\ \end{array}

all’incrocio si trova il risultato della somma con il valore già ridotto.

I valori sono simmetrici rispetto alla diagonale che va da in alto a sinistra ad in basso a destra perché la somma è commutativa.

La classe [0] rappresenta i multipli di 3, le altre classi i numeri che divisi per 3 danno resto 1 o 2.

La tabella dice quindi:

la somma di due multipli di 3 è un multiplo di 3.
La somma di un multiplo di 3 ed un numero che diviso per 3 da resto 1 è un numero che diviso per 3 da resto 1
La somma di un multiplo di 3 ed un numero che diviso per 3 da resto 2 è un numero che diviso per 3 da resto 2
La somma di due numeri che divisi per 3 danno resto 1 è un numero che diviso per 3 dà resto 2
La somma di un numero che diviso per 3 dà resto 1 ed un numero che diviso per 3 dà resto 2 è un multiplo di 3
La somma di due numeri che divisi per 3 danno resto 2 è un numero che diviso per 3 dà resto 1.

Diciamo che non ha lo stesso fascino dei pari e dispari di prima.

Per moduli maggiori di 3 la cosa diventa anche peggiore ma vedendola in modo diverso non è così male.

Partiamo dalla classe [0] e sommiamo la classe [1], poi al risultato sommiamo ancora la classe [1] e così via. La somma cresce fino alla classe [n-1] a cui sommando [1] otteniamo [n]=[0] e si ricomincia ripetendo la stessa successione di classi.

Gli elementi quindi si ripetono periodicamente ed è interessante vederli attorno ad una circonferenza come i numeri di un orologio.

Prendiamo il modulo 12. Sul quadrante dell’orologio vediamo il numero 12 scritto in alto e poi, in senso orario, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 e 12.

Sostituiamo il 12 con lo 0 e vediamo che otteniamo gli stessi elementi delle classi di modulo 12 con i resti che vanno da 0 a 11. Cosa succede se sommiamo 4 a 10 ? otteniamo 14 che ridotto fornisce 2. In effetti se alle ore 4 aggiungiamo 10 ore otteniamo le ore 2 perché arrivati a 12 ricominciamo a contare.

Vista in questo modo l’aritmetica delle classi è quella di un orologio con n ore distinte, così è un po’ meglio da vedere e da capire. Per esempio, prendiamo il modulo 5 e disegniamo l’orologio corrispondente come in figura:

proviamo a sommare [2] con [4], segnati in figura con le lancette azzurre, il risultato è [6] che coincide con la classe [1] indicata dalla lancetta rossa, basta sottrarre il modulo 5 da 6 una volta per ottenere il resto 1.

Tutto ciò è carino ma, non molto eccitante. Insomma, la matematica dell’orologio non vale lo sforzo fatto. L’unica cosa che possiamo salvare è che si tratta di un esempio di gruppo finito, ispiratore di tutta la teoria dei gruppi ma ancora sembra l’ufficio complicazioni affari semplici di fantozziana memoria.

Proviamo a moltiplicare le classi ? Dai, vediamo cosa succede.

Moltiplichiamo le classi

Rifacciamoci la stessa domanda di prima ma con la moltiplicazione invece della addizione, dati due numeri g, h di cui sono noti i resti r e s: cosa possiamo dire del resto del loro prodotto ?

Prendiamo due elementi di classi qualsiasi e moltiplichiamoli tra loro e cerchiamo di capire in quale classe vanno a finire:

g,h \in \Z \newline g=nq+r \quad h=np+s \newline gh=(nq+r)(np+s)=n(nqp+qs+pr) +rs \newline

Come nella classe somma scopriamo che anche il prodotto finisce nella classe del prodotto dei resti rs. Quindi possiamo scrivere:

[r][s]:=[rs]

Il prodotto tra classi che vogliamo definire a sinistra è definito tramite l’espressione di destra.

Segue immediatamente dalle proprietà dei numeri naturali che il prodotto è associativo e commutativo.

Un’altra cosa che vale è la proprietà distributiva, basta provare:

[r]([s]+[t])=[r][s+t]=[r(s+t)]=[rs+rt] \newline \space [r][s]+[r][t]=[rs]+ [rt]=[rs+rt]

poiché gli ultimi membri sono uguali lo sono anche i primi e quindi vale la proprietà distributiva; si può raccogliere a fattore comune.

Se, come è normale supporre, n>1 allora abbiamo sia la classe [0] che la classe [1], vediamo come si comporta il prodotto:

[r][0]=[r\cdot 0]=[0] \newline \space [r][1]=[r\cdot 1]=[r]

Quindi la classe [1] si comporta come elemento neutro del prodotto mentre la classe [0] come elemento assorbente.

Prendiamo ora l’opposto di [1] che come abbiamo visto è [n-1] e moltiplichiamolo per un qualsiasi elemento:

\space [r][n-1]=[r]([n]+[-1])=[r][-1]=[-r]

Il prodotto è consistente con il concetto di opposto e ci permette di dire che basta cambiare di segno.

Rimangono gli inversi, questione delicata. Pensare di considerare l’inverso di [a] come:

[\frac{1}{a}]

è privo di senso, la classe è costruita sugli interi non sulle frazioni.

Notiamo che in generale la classe [0] non ha inverso, il prodotto con qualsiasi cosa dà ancora [0] quindi non può dare [1].

Invece la classe [1] ha come inverso se stesso, sempre.

Proviamo a costruire le tabelle di moltiplicazione con modulo 2 e 3:

\def\arraystretch{1.5} \begin{array}{c:c:c} \pmb{\cdot} & \pmb{[0]} & \pmb{[1]} \\ \hdashline \pmb{[0]} & [0] & [0] \\ \hdashline \pmb{[1]} & [0] & [1] \\ \end{array} \quad \def\arraystretch{1.5} \begin{array}{c:c:c:c} \pmb{\cdot} & \pmb{[0]} & \pmb{[1]} & \pmb{[2]}\\ \hdashline \pmb{[0]} & [0] & [0] & [0]\\ \hdashline \pmb{[1]} & [0] & [1] & [2] \\ \hdashline \pmb{[2]} & [0] & [2] & [1]\\ \end{array} \newline

La tabella di moltiplicazione di modulo 2 è semplice, la classe [0] non ha inverso, come normale che sia mentre la classe [1] ha come inverso sé stessa: la situazione è banale; Pari per Pari fa Pari, Pari per Dispari fa Pari e Dispari per Dispari fa Dispari.

Vediamo invece la tabella di moltiplicazione di modulo 3. La sua costruzione è facile, basta moltiplicare i resti, solo 2×2=4 richiede una spiegazione, bisogna togliere il modulo, basta una sola volta, per ottenere un resto minore del modulo 4-3=1.

Ora osserviamola e notiamo che anche [2] ha un inverso, sé stesso. Il prodotto con sé stesso dà l’elemento neutro [1]. Possiamo pensare che la stessa cosa valga per moduli più grandi ?

Proviamo a costruire la tabella di modulo 4 e 5:

\def\arraystretch{1.5} \begin{array}{c:c:c:c:c} \pmb{\cdot} & \pmb{[0]} & \pmb{[1]} & \pmb{[2]} & \pmb{[3]}\\ \hdashline \pmb{[0]} & [0] & [0] & [0] & [0]\\ \hdashline \pmb{[1]} & [0] & [1] & [2] & [3] \\ \hdashline \pmb{[2]} & [0] & [2] & [0] & [2]\\ \hdashline \pmb{[3]} & [0] & [3] & [2] &[1]\\ \end{array} \quad \def\arraystretch{1.5} \begin{array}{c:c:c:c:c:c} \pmb{\cdot} & \pmb{[0]} & \pmb{[1]} & \pmb{[2]} & \pmb{[3]} & \pmb{[4]} \\ \hdashline \pmb{[0]} & [0] & [0] & [0] & [0] & [0]\\ \hdashline \pmb{[1]} & [0] & [1] & [2] & [3] & [4]\\ \hdashline \pmb{[2]} & [0] &[2] & [4] & [1] & [3]\\ \hdashline \pmb{[3]} & [0] & [3] & [1] & [4] & [2]\\ \hdashline \pmb{[4]} & [0] & [4] & [3] & [2] & [1]\\ \end{array} \newline

Per la tabella di moltiplicazione del modulo 4 vediamo che la classe [2] non ha inverso, i prodotti con tutte le altre classi danno solo [0] oppure [2] mai [1].

La tabella di moltiplicazione del modulo 5 invece fornisce un inverso per ogni classe eccetto [0]. L’inverso di [3] è [2] e viceversa, l’inverso di [2] è [3].

Quindi ci sono casi in cui l’inverso esiste ed altri in cui l’inverso non esiste. È un utile esercizio andare avanti a costruire tabelle di moltiplicazione, io non lo faccio perché lo feci a suo tempo. La cosa interessante è che non è necessario ricorrere alle frazioni per avere un inverso.

In generale possiamo dire due cose certe:

[0][x]=[0] \newline \space [1][1]=[1]

La classe [0] moltiplicata per qualsiasi cosa dà [0] e quindi non ammette inverso.
La classe[1] è l’inverso di sé stessa.

Possiamo anche fare questa osservazione, prese due classi non nulle se il prodotto è nullo allora entrambe non ammettono inverso, vediamo:

\space [r], [s] \ne [0] \newline \space [r][s]=[0] \newline \text{se esiste l'inverso di [r], chiamiamolo } [r]^{-1} \newline \space [r]^{-1}[r][s]=[r]^{-1}[0] \newline \space [1][s]=[0] \newline \space [s]=[0] \newline \text{contro l'ipotesi che [s] non sia [0] } \newline \text{lo stesso per l'inverso di [s] moltiplicando a destra}

Ad esempio in modulo 4 dalla tabella di moltiplicazione si vede che [2][2]=[0] e quindi [2] non ha inverso, non server verificare tutta la riga.

Possiamo dire tranquillamente che non tutti i moduli permettono di costruire classi con inverso con il prodotto definito. Qual’è il criterio per cui il modulo n ammette la costruzione di un gruppo moltiplicativo ? Basta un criterio su n per verificarlo ?

La risposta è gelosamente custodita nel seguente teorema che nei libri viene spesso frastagliato in lemmi e teoremini vari, a me non piace. Ora lo enuncio e poi lo discuto e nella discussione vedremo tutti i passi della dimostrazione:

Teorema: le classi di resto modulo n formano un gruppo moltiplicativo solo se n è un numero primo.

Cominciamo nel mostrare che è necessario che n sia primo. Supponiamo che n non sia primo e sia quindi nella forma:

n=pq \newline 1< p, q < n

p e q appartengono a delle classi diverse da 0 altrimenti sarebbero divisibile per n. Possiamo scrivere questo fatto con le due notazioni:

[p][q]=[pq]=[n]=[0] \newline pq \equiv n \rArr pq \equiv 0

in entrambe le notazioni l’ultimo passaggio mostra che il prodotto appartiene alla classe [0], il che è un fatto ovvio. Si vede bene che il prodotto delle classi non nulle è la classe [0] e quindi sia [p] che [q] non hanno inverso.

È utile anche osservare che un elemento a che appartiene alla classe [0] è un elemento non divisibile per n, normalmente questo fatto viene detto come a è coprimo di n, nel linguaggio delle classi si dice che a non appartiene alla classe [0].

Questa prima parte della dimostrazione del teorema è quasi un’osservazione; andiamo avanti.

Scriviamo tutte le classi di resto escluso la classe [0], prendiamo una classe qualsiasi di queste, quindi non nulla, chiamiamola [a] ( a è coprimo con n se [a] non è la classe [0]) e scriviamo tutti i possibili prodotti:

[1], \space [2], \space \dots,[n-1]\newline \space [1][a], \space [2][a], \space \dots, [n-1][a]

sia la prima che la seconda riga sono di n-1 prodotti, la domanda fondamentale è: sono tutti diversi ?

I prodotti ottenuti potrebbero coincidere con gli elementi della prima riga oppure essere un sottoinsieme o ancora potrebbero essere [0]. Proviamo a dare una risposta precisa.

Se fosse un sottoinsieme allora il prodotto di due classi distinte non nulle [r] e [s] con la classe [a] non nulla dovrebbero coincidere cioè dovrebbe valere:

[r][a]=[s][a]

sommando l’opposto ad esempio del membro di destra e sfruttando la proprietà distributiva, o se preferite portando a sinistra e raccogliendo a fattore comune, si ottiene:

\space [r][a]+[-s][a]=[0] \newline \space ([r]+[-s])[a]=[0] \newline \space [r-s][a]=[0] \newline (r-s)a \equiv 0

l’ultima riga è la notazione con il simbolo di congruenza. Comunque si scriva la cosa significa che il prodotto di sinistra è divisibile per il modulo n e dà resto 0.

Se il prodotto di due classi è la classe nulla allora entrambi non possono avere inverso, oppure una o entrambe sono la classe [0]. Per ipotesi [a] è diversa dalla classe [0] ed anche [r], [s] ed essendo diverse anche [r-s]. quindi entrambe non hanno inverso, questo implica che è necessario avere prodotti distinti per avere gli inversi ma non dice quando questo avviene.

Elaboriamo ancora l’ultima equazione, facciamo il prodotto e sostituiamo la classe [0] con la classe [n] che è lo stesso:

\space [(r-s)a]=[n] \newline \space (r-s)a=nq \quad q \in \Z

Qui il ragionamento si fa fine e sfrutta il fatto che n è primo. Il prodotto (r-s)a è divisibile per n ma non i singoli termini del prodotto, questo vale per qualsiasi n. Se n è primo non può dividere il prodotto (r-s)a altrimenti sarebbe un numero composto cioè non primo; quindi l’equazione è impossibile e quindi i prodotti sono tutti diversi.

Indaghiamo la possibilità che il prodotto possa essere la classe [0]. anche questo non è possibile vediamo come scrivere:

\space [r][a]=[0] \newline \space [ra]=[0] \newline ra \equiv 0

Come si vede possiamo riportare il problema al caso precedente con s=0. I passaggi sono gli stessi e portano alla conclusione che, essendo il modulo primo, il prodotto non può essere nullo.

Allora i prodotti che abbiamo scritto, cioè una riga della tabella di moltiplicazione escluso lo [0], sono tutti diversi e sono n-1. Per controllo si possono guardare le tabelle di moltiplicazione che abbiamo scritto come esempi.

Possiamo concludere quindi che fissata [a] e facendo variare [r] tra tutti i possibili valori non nulli otteniamo ancora tutti i possibili valori non nulli a patto che il modulo sia un primo. Tra questi c’è anche [1] e quindi possiamo dire che esiste sempre l’inverso.

Abbiamo concluso la dimostrazione del teorema.

Una piccola conseguenza

Il teorema di prima, meglio, la dimostrazione del teorema ci porta ad una piccola conseguenza.

Moltiplichiamo tra loro tutti i prodotti costruiti con [a] (a è coprimo con n, la classe [0] è esclusa), questi sono tutte le classi tranne la classe [0], allora possiamo scrivere l’identità:

[1][a][2][a] \dots[n-1][a]=[1][2]\dots [n-1]\newline

sviluppiamo i prodotti a destra e a sinistra:

[1a\cdot 2a\dots (n-1)a]=[1\cdot2\dots(n-1)] \newline (n-1)!=1\cdot 2\dots (n-1) \newline \space [a^{n-1}(n-1)!]=[(n-1)!] \newline \space [a^{n-1}][(n-1)!]=[(n-1)!] \newline

L’ultima riga cosa significa ? Sembra che la classe della potenza di a si comporti come l’elemento [1]. Possiamo vederlo meglio mettendo i termini dalla stessa parte ed usando la proprietà distributiva raccogliendo a fattore comune la classe con il fattoriale

\space [a^{n-1}-1][(n-1)!]=[0]

Il prodotto delle due classi è la classe nulla, ma n è primo e quindi tutti gli elementi hanno inverso tranne lo [0] allora una o entrambe devono essere la classe nulla:

\space [a^{n-1}-1]=[0] \newline \space [(n-1)!]=[0]

La seconda non è possibile perché il fattoriale non è divisibile per il modulo n. Infatti essendo primo deve dividere almeno uno dei termini del prodotto ma ognuno è minore del modulo e quindi non è possibile. Possiamo utilizzare anche il linguaggio delle classi:

[1][2]\dots [n-1]=[0]

tutti gli elementi a sinistra non sono la classe nulla ed il loro prodotto non può essere la classe nulla.

Segue che deve valere la prima relazione che viene scritta nelle seguenti forme:

\space [a^{n-1}-1]=[0] \newline a^{n-1}-1 \equiv 0 \newline a^{n-1} \equiv 1 \newline \text{n primo e a coprimo con n}

noto come piccolo teorema di Fermat; ve l’avevo detto che la conseguenza era piccola vero ?

Il piccolo teorema di Fermat

A Gauss era noto il risultato di Fermat, con questa formalizzazione viene come una conseguenza piccola del teorema che impone al modulo di essere primo affinché esista il gruppo moltiplicativo ma il teorema è famoso per molti motivi.

Il primo è che permette di costruire un test di NON primalità, anche se in molti testi viene presentato come test di primalità. Prendiamo un numero n, ed un numero a (non divisibile per n: coprimo), calcoliamo la potenza n-1 di a e dividiamola per n. Se il resto è diverso da 1 siamo sicuri che n non è primo.

Se invece il resto è 1 possiamo concludere soltanto che potrebbe essere primo ma non è detto. Infatti esistono controesempi di numeri non primi che soddisfano la congruenza e vengono chiamati pseudoprimi, poca fantasia ma il nome è comunque efficace.

Su questo teorema si basa anche la crittografia RSA ma in questo post non c’è spazio per questo.

Concludendo

La classi di resto modulo n permettono di generalizzare concetti semplici come pari e dispari, permettono di spiegare l’aritmetica dell’orologio e di orologi anche più grandi, permettono anche di dire che non sempre 2+2 fa 4, infatti modulo 3 fa 1. Le classi permettono di costruire esempi di gruppi finiti.

Il bello viene però considerando il prodotto di classi. Non sempre si ottiene un gruppo moltiplicativo, dobbiamo imporre al modulo di essere un numero primo: cosa inaspettata. È qui che le classi di resto modulo n diventano importanti. La prima conseguenza è il piccolo teorema di Fermat. Ne seguono altri ma noi ci fermiamo qui.

È ora di andare a nanna. Sogni d’oro a tutti.

Bibliografia

Consulta la pagina a questo link

– / 5

Grazie per aver votato!