Prima di definire il "Calcolatore ad Orologio" di Gauss, è necessario richiamare alcuni concetti di Algebra che ci saranno utili e senza i quali, a mio avviso, non è possibile dare una risposta esauriente. Cercherò comunque di non essere pesante per quanto riguarda l’utilizzo della simbologia matematica:
DEFINIZIONI PRELIMINARI
1. partizione di un insieme:
dato un insieme A si definisce partizione una collezione di sottoinsiemi Ai di A tali che:
a. l’unione di tutti i sottoinsiemi Ai è pari ad A;
b. dati due sottoinsiemi Ai e Aj distinti, questi sono disgiunti (non hanno elementi in comune)
2. prodotto cartesiano:
dati due insiemi A e B si definisce prodotto cartesiano A x B l’insieme delle coppie ordinate (x,y), con x che appartiene ad A ed y che appartiene a B. Formalmente si scrive:
Esempio:
A = { a , b , c } , B = { 1 , 2 } segue che A x B = { (a,1) , (a,2) , (b,1), (b,2), (c,1), (c,2) }
3. relazione tra due insiemi (relazione binaria):
dati due insiemi A e B non vuoti (che possono anche essere coincidenti), si definisce relazione R tra gli elementi di A e gli elementi di B, ogni sottoinsieme del prodotto cartesiano A x B.
Esempio:
dati A = { a , b , c } , B = { 1 , 2 } , una possibile relazione tra questi due insiemi, potrebbe essere la seguente:
R = { (a , 1) , (a , 2) , (b,2) }
Quindi la notazione "a R b" sta a significare (a,b) appartenente ad R
4. relazione di equivalenza:
Data una relazione R in A (quindi un sottoinsieme del prodotto cartesiano A x A), si definisce relazione di equivalenza se soddisfa le seguenti proprietà:
4.1 proprietà riflessiva:
"ogni elemento a appartenente ad A è in relazione con se stesso ( a R a)"
4.2. proprietà simmetrica:
"dati due elementi a e b appartenenti ad A, se a è in relazione con b, allora b è in relazione con a"
( a R b → b R a )
4.3. proprietà transitiva:
"dati tre elementi a,b,c appartenenti ad A, se a è in relazione con b e b è in relazione con c, allora a è in relazione con c"
(a R b , b R c → a R c )
Esempio:
Supponiamo di avere il seguente insieme:
A = { 1, 2, 3, 4}
e la relazione:
R = { (1,1) , (2,2) , (3,3) , (4,4) , (1,2) , (2,1) , (4,3) , (3,4) , (2,3) , (3,2) , (1,3), (3,1) , (4,2) , (2,4) }
si può verificare che è una relazione di equivalenza; infatti valgono le proprietà: riflessiva, simmetrica e transitiva.
5. classi di equivalenza:
Supponiamo di avere un insieme A e una relazione di equivalenza R ed un elemento a appartenente ad A; si definisce classe di equivalenza [a] il sottoinsieme di A degli elementi equivalenti ad a
[a] = { x appartantente ad A tale che x R a }
Si può dimostrare che l’insieme delle classi di equivalenza costituisce una partizione per A. Infatti:
5.1. ogni elemento di A appartiene ad una classe di equivalenza (essendo almeno in relazione con se stesso, come si verifica dalla relazione R di equivalenza)
5.2. date due classi di equivalenza [a] e [b] qualsiasi, queste sono disgiunte.
dim.
supponiamo per assurdo che esistano due classi di equivalenza [a] e [b] che non siano disgiunte, allora esisterà un elemento x appartenente ad [a] e appartenente a [b]; questo significa che è in relazione con tutti gli elementi di [a] e con tutti gli elementi di [b] allora, per la proprietà transitiva, tutti gli elementi di [a] sono in relazione con tutti gli elementi di [b], da cui segue, dalla definizione di classe di equivalenza, che [a] = [b].
6. insieme quoziente
Dato un insieme A e una relazione di equivalenza R, si definisce insieme quoziente A~ l’insieme delle classi di equivalenza. Praticamente abbiamo partizionato l’insieme di partenza A, lo abbiamo "diviso" in classi di equivalenza.
E’ importante notare che, le definizioni che sono state date, servono per aiutarci a capire la definizione successiva: la definizione di prodotto cartesiano ci serve per comprendere la definizione di relazione, e quest’ultima ci serve per comprendere la relazione di equivalenza.
Arrivati a questo punto possiamo dare la definizione di congruenza modulo n.
RELAZIONE DI CONGRUENZA MODULO N
7. congruenza modulo n:
dati tre numeri interi x, y, n, diremo che x ed y sono congruenti modulo n se vale la seguente:
x – y = hn con h numero intero.
Detto in un altro modo: "x ed y sono congruenti modulo n se e solo se la loro differenza è un multiplo di n".
Si può verificare che la congruenza modulo n è una relazione di equivalenza nell’insieme dei numeri interi Z. Infatti:
a. vale la proprietà riflessiva:
per ogni elemento x appartenente a Z, abbiamo: x – x = 0 ponendo h = 0
b. vale la proprietà simmetrica:
se x è congruente ad y modulo n, allora y è congruente ad x modulo n
x – y = hn → y – x = (-h)n
c. vale la proprietà transitiva:
se x è congruente ad y modulo n, ed y è congruente a z modulo n, allora x è congruente a z modulo n
x – y = hn
y – z = kn
(x – y) – (y – z) = (h-k)n
x – z = (h-k)n
Bene, abbiamo appurato che la relazione di congruenza modulo n è una relazione di equivalenza. Consideriamo un esempio per capire meglio:
Esempio:
Vogliamo considerare la relazione di congruenza modulo 4 su Z:
x – y = 4h
Vediamo adesso le classi di equivalenza (classi di congruenza) legate a questa relazione:
[0] = { x appartenente ad A tale che x = 4h + 0 } = { 0 , ± 4 , ± 8 , ± 12 , ± 16 , … }
[1] = { x appartenente ad A tale che x = 4h + 1 } = { ± 1 , ± 5 , ± 9 , ± 13 , … }
[2] = { x appartenente ad A tale che x = 4h + 2 } = { ± 2 , ± 6 , ± 10 , ± 14 , … }
[3] = { x appartenente ad A tale che x = 4h + 3 } = { ± 3 , ± 7 , ± 11 , ± 15 , … }
[4] = {x appartenente ad A tale che x = 4h + 4} = { 0 , ± 4 , ± 8 , ± 12 , ± 16 , … } = [0]
Quindi l’insieme formato da {[0] , [1] , [2] , [3] } e che chiameremo Z4 è una partizione di Z secondo la relazione di congruenza modulo 3.
In generele possiamo dire che, data una relazione di congruenza modulo n, l’insieme quoziente delle classi di congruenza, è così definito:
Zn = { [0]n , [1]n , [2]n , … , [n-1]n}
Possiamo vedere le classi di congruenza come l’insieme dei numeri interi che, divisi per 4, hanno rispettivamente resto: 0, 1, 2, 3. Infatti la relazione di congruenza può essere scritta in questo modo:
x = nh + y
in cui si può notare che, fissato y, ottengo tutti i numeri congruenti ad y (ricordiamo che la relazione di congruenza modulo n è fissata una volta fissato n) facendo variare h in Z.
Vediamo alcune proprietà della relazione di congruenza modulo n:
8. stabilità rispetto all’operazione di addizione:
Se x è congruente ad y modulo n ( x = nh + y), allora anche (x + c) sarà congruente modulo n con (y + c) con c numero intero.
Dim.
Essendo x = nh + y segue che: x + c = nh + y + c da cui è dimostrato quanto detto.
Se sommiamo quindi una costante intera c a due numeri x ed y in relazione di congruenza modulo n, i nuovi numeri (x + c) ed (y + c) continuano ad essere in relazione di congruenza modulo n.
9. stabilità rispetto all’operazione di moltiplicazione:
Se x è congruente ad y modulo n ( x = nh + y), allora anche (x *c) sarà congruente modulo n con (y*c) con c numero intero.
Dim.
Essendo x = nh + y segue che: x *c = nh*c + y*c da cui è dimostrato quanto detto.
Se moltiplichiamo una costante intera c a due numeri x ed y in relazione di congruenza modulo n, i nuovi numeri (x*c) ed (y*c) continuano ad essere in relazione di congruenza modulo n.
10. stabilità rispetto all’elevamento a potenza
Se x è congruente ad y modulo n ( x = nh + y), allora anche xm sarà congruente modulo n con ym con m numero intero.
Dim.
Per la dimostrazione utilizzeremo il principio di induzione: supponiamo che sia xm-1 congruente modulo n con ym-1, dalla 7. sappiamo che anche i seguenti xm-1*x = xm e ym-1*x sono congruenti (abbiamo moltiplicato entrambi i valori per x). Adesso ripetiamo lo stesso procedimento moltiplicando x ed y per ym-1 otteniamo che i seguenti numeri x*ym-1 e ym continuano ad essere congruenti.
Per cui abbiamo:
xm congruente modulo n con ym-1*x
x*ym-1 congruente modulo n con ym
Possiamo quindi affermare, per la proprietà transitiva della relazione di congruenza, che xm e ym sono congruenti modulo n.
OPERAZIONI DI SOMMA E DI PRODOTTO
A questo punto, definiamo le operazioni di somma e di prodotto e di moltiplicazioni tra le classi di congruenza:
11. somma tra classi di congruenza
Date due classi di congruenza [x]m e [y]m si definisce somma tra le due classi la seguente:
[x]m + [y]m = [x + y]m
12. prodotto tra classi di congruenza
Date due classi di congruenza [x]m e [y]m si definisce prodotto tra le due classi la seguente:
[x]m * [y]m = [x * y]m
Arrivati a questo punto possiamo fare un riepilogo, infatti dovrebbero essere chiari i seguenti concetti:
- partizione di un insieme;
- prodotto cartesiano;
- relazione tra due insiemi;
- relazione di equivalenza;
- classi di equivalenza;
- insieme quoziente data una relazione di equivalenza.
Tramite queste definizioni abbiamo potuto comprendere i seguenti concetti:
- relazione di congruenza modulo n;
- classi di congruenza;
- insieme quoziente Zn data una relazione di congruenza;
- somma tra classi di congruenza;
- prodotto tra classi di congruenza;
- proprietà della relazione di congruenza.
Adesso iniziamo ad effettuare dei calcoli mediante l’utilizzo delle nozioni appena apprese; in particolare: ci doteremo della struttura algebrica seguente:
- una relazione di congruenza modulo n;
- l’insieme delle classi di congruenza Zn = { [0]n , [1]n , [2]n , … , [n-1]n} ;
- le operazioni somma + e prodotto * definite tra classi di congruenza come ai punti 11. e 12.;
Prendiamo, ad esempio, la relazione di congruenza modulo 12, quindi due elementi x ed y saranno in relazione tra di loro se e solo se:
x – y = 12h
da cui, l’insieme delle classi di congruenza sarà così formato:
Z12 = { [0]12 , [1]12 , [2]12 , [3]12 , [4]12 , [5]12 , [6]12 , [7]12 , [8]12,[9]12 ,[10]12 , [11]12} ;
E’ opportuno ricordare che la classe [1]12 raccoglie tutti gli elementi che danno resto 1 se divisi per 12, così come la classe [5]12 raccoglie tutti gli elementi che danno resto 5 se divisi per 12, e così via.
Adesso proviamo ad effettuare delle somme:
[1]12 + [3]12 = [ 4 ]12
[1]12 + [9]12 = [ 10 ]12,
[1]12 + [10]12 = [ 11 ]12
Adesso viene la parte interessante:
[1]12 + [11]12 = [ 0 ]12
11 + 1 = 0, come mai questo risultato? Semplice: stiamo sommando tra loro le classi di congruenza modulo 12, il risultato di 1 + 11 sarebbe 12, ma la classe di congruenza a cui appartiene 12 è formata dagli elementi che hanno lo stesso resto se vengono divisi per 12, ora: 12/12 = 1 con resto 0, quindi [1]12 + [11]12 = [ 0 ]12
Consideriamo le operazioni seguenti:
[4]12 + [5]12 = [ 9 ]12
[4]12 + [10]12 = [ 2 ]12,
[7]12 + [11]12 = [ 6 ]12
[11]12 + [11]12 = [ 10 ]12
Praticamente abbiamo un "calcolatore" diverso dal solito calcolatore algebrico…sembra funzionare come l’orologio! Infatti se alle ore 7 sommiamo 11 ore, avremo la lancetta sulle ore 6; analogamente se alle ore 10 sommiamo 4 ore, avremo la lancetta sulle ore 2.
Ai tempi di Gauss purtroppo non c’erano gli orologi con quadrante a cristalli liquidi! Però possiamo rimediare subito! Considerando la relazione di congruenza modulo 24!
Z24 = { [0]24 , [1]24 , [2]24 , [3]24 , [4]24 , [5]24 , [6]24 , [7]24 , [8]24 , [9]24 , … ,[22]24 , [23]24}
E consideriamo le seguenti somme:
[14]24 + [16]24 = [6 ]24
[14]24 + [10]24 = [ 0 ]24
[17]24 + [11]24 = [ 13 ]24
[11]24 + [11]24 = [ 12 ]24
Infatti, se sommiamo 16 ore alle ore 14, otteniamo le ore 6; analogamente se sommiamo 10 ore alle ore 14, otteniamo la "mezzanotte", e quindi le ore 00!
Ora, a parte questa parentesi scherzosa per capire il perché del nome di "calcolatore ad orologio", è evidente che l’Illustrissimo Gauss non ha creato questa teoria per divertirsi a contare come un orologio! Basti pensare che la Teoria Modulare è alla base dei più moderni algoritmi di Crittografia.
Per scoprire una tra le varie particolarità di questa teoria scoperta da Gauss, prendiamo in considerazione l’insieme quoziente che segue:
Z12 = { [0]12 , [1]12 , [2]12 , [3]12 , [4]12 , [5]12 , [6]12 , [7]12 , [8]12,[9]12 ,[10]12 , [11]12}
(ricordiamoci che abbiamo definito anche l’operazione di moltiplicazione tra classi di congruenza)
Supponiamo che Gauss avesse voluto calcolare 8 * 8, mediante questa teoria il calcolatore ad orologio avrebbe fornito 4: il resto della divisione di 64 per 12. Se avesse voluto continuare nel calcolo 8 * 8 * 8, non era necessario calcolare 64 * 8 = 512 e poi dividere , bastava calcolare 4 * 8 = 8 (ricordiamo che stiamo moltiplicando classi di congruenza, quindi 8 * 4 = 32 → [8]12) per sapere che 512 diviso 12 da come resto 8.
Qual è l’utilità di questo "calcolatore"? Semplice: avrebbe potuto procedere calcolando 84 prendendo l’ultimo risultato ottenuto e moltiplicandolo ancora per 8, ottenendo:
[8]12 * [8]12 = [4]12
Quindi il resto di 84 diviso 12 è 4.
Si potrebbe procedere per potenze molto elevate con la stessa tecnica.