Algebra delle classi di resto 1

Algebra delle classi di resto 1

Dalle classi di resto al teorema cinese e ai sistemi di congruenze lineari

di Leonardo Calconi

Che cos’è una classe di resto?

È l’insieme di quei numeri interi che danno lo stesso resto se divisi per uno stesso intero.

{..., -7, -5, -3, 1, 3, 5, 7,...} formano una classe di resto [1] perché divisi per 2 danno lo stesso resto 1.

L’argomento è intrigante: utilizzare classi di resto anziché numeri nelle operazioni.

Le applicazioni pratiche sono di grande interesse: basti pensare che attualmente (e almeno fin quando i computer quantistici non saranno realtà), l’esistenza delle transazioni commerciali e bancarie via Internet è resa possibile grazie alle cifrature basate sull’algebra delle classi di resto.

Ho iniziato con alcune premesse sulle definizioni fondamentali, e perché rimanessero brevi e compatte ne ho tralasciato le dimostrazioni che non sono funzionali agli scopi di questo lavoro.

Ho proseguito dalla definizione di classe di resto fino ai sistemi di congruenze lineari, cercando di dimostrare tutto ed inserendo un buon numero di esempi di calcolo pratico.

Ho tralasciato la matematica ricreativa, argomenti molto popolari quali la prova del nove e i criteri di divisibilità, ed altri interessanti come la RSA sui quali è stato scritto molto e molto meglio di quanto potrei fare io.

Indice

• 1 Premesse pagg. 2-3
• 1.1 Relazione
• 1.2 Relazione di equivalenza
• 1.3 Relazione di uguaglianza
• 1.4 Classe di equivalenza
• 1.5 Partizione
• 1.6 Combinazione lineare
• 1.7 Identità di Bezout
• 1.8 Algoritmo di Euclide e MCD
• 1.9 Equazione diofantea
• 2 Classi di resto pagg. 4-9
• 2.1 Relazione di congruenza modulo n
• 2.2 Proprietà delle relazioni di congruenza
• 2.3 Classe di resto
• 2.4 Anello delle classi di resto
• 2.5 Dominio d’integrità delle classi di resto
• 2.6 Campo delle classi di resto ed inversi
• 2.7 Calcolo degli inversi nell’anello delle classi di resto
• 2.7.1 Teorema di Lagrange
• 2.7.2 Corollario del Teorema di Lagrange
• 2.7.3 Teorema di Eulero
• 2.7.4 Piccolo Teorema di Fermat
• 2.8 Calcolo degli inversi nel campo delle classi di resto
• 2.9 Inversi banali
• 3 Congruenze lineari pagg. 10-13
• 3.1 Equazione diofantea
• 3.2 Definizione di congruenza lineare
• 3.3 Compatibilità, soluzioni fondamentali e classi di congruenza
• 3.4 Forma delle soluzioni
• 3.5 Soluzioni non congruenti e congruenti; calcolo
• 3.6 Riduzione del modulo
• 4 Sistemi di congruenze lineari pagg. 14-18
• 4.1 Teorema cinese del resto
• 4.1.1 Compatibilità
• 4.1.2 Soluzioni
• 4.2 Sistemi di congruenze lineari ad una incognita

Leonardo Calconi – Algebra delle classi di resto 1

1 Premesse

1.1 Relazione

Descritta in modo informale una relazione è una legge che associa un elemento di un insieme ad un elemento di un altro insieme, oppure che associa uno ad uno gli elementi di uno stesso insieme.

→

Descritta in modo formale una relazione r è un’applicazione r : A B, ovvero un sottoinsieme del prodotto cartesiano A x B. Se A = B = l’applicazione è r : ed è definita in stesso.

→

1.2 Relazione di equivalenza

È una relazione r definita nell’insieme A per la quale valgono le proprietà riflessiva, simmetrica e transitiva:

• ∈ b, a,b A se
• a r • a r a ⇒
• a r b b r a
• a r b, b r c a r c

► Esempi

= similitudine, A = insieme dei triangoli nel piano

r

r = parallelismo, A = insieme dei piani nello spazio

► Contro-esempi

r = normalità, A = insieme dei piani nello spazio → 1 e 3 non sono verificate

r = essere multiplo di, A = → 2 non è verificata

1.3 Relazione di uguaglianza

È una relazione di equivalenza cui viene applicata la proprietà restrittiva antisimmetrica:

⇔

• a r b, b r a a = b

► Esempio

= dividere

r

A =

Come è evidente, questo e qualunque altro esempio si voglia portare è tautologico.

Si può discutere sul fatto che la relazione di uguaglianza sia un caso particolare delle relazione di equivalenza oppure che quest’ultima sia una generalizzazione della relazione di uguaglianza.

1.4 Classe di equivalenza modulo r

Tutti gli elementi di A per i quali vale r rispetto ad a

∈ A | b r a}

[a] = {b

► Esempio ≤

r = coordinate q

A = insieme dei punti dello spazio

[a] = sfera di raggio q.

Naturalmente le classi di equivalenza modulo r possono essere più d’una, come mostrato nel paragrafo seguente.

1.5 Partizione

È l’insieme [A] delle parti di A che verifica le proprietà:

• [A] = A
• ∩
• A = 0
• ∩ ≠ ⇔
• A A 0 A = A

m n

m n m n

Quindi una partizione esaurisce l’insieme al quale si riferisce.

Leonardo Calconi – Algebra delle classi di resto 2

► Esempio

r = dare resto m nella divisione per n intero

A = ∪ ∪ ∪ ∪

[A] = [a ] [a ] [a ] ... [a ]

0 1 2 n-1

1.6 Combinazione lineare ( )

+ ⇒ +

bx cy

In è definita tale una scrittura come . Per essa se .

a | b , a | c a | ax by

1.7 Identità di Bezout ( )

= ⇒ = +

d a , b d ha kb

se per h, k opportuni.

È una scrittura del MCD. In ( ) ( )

∈ −

= + +

La coppia di valori (h, k) non è unica in quanto per ogni i si ha .

d a h ib b k ia

( ) ( )

= = · − · = + · − + ·

► Esempio: (77, 99) 11 77 4 99 3 77 4 567 99 99 3 567 77

( ) =

a | c , b | c , a , b d ab | cd

allora .

In base all’identità risulta che se

1.8 Algoritmo di Euclide e MCD

∈ >

Per a , b e, senza inficiare la validità del procedimento con , ecco come calcolare il MCD

a b

e una coppia di valori per l’identità di Bezout col metodo delle divisioni successive:

( ) = = · − ·

: :

► Esempio 758, 242 2 758 53 242 166

= − · = − · ⇒

4 18 14 1

2 14 4 3,

= · +

758 242 3 32

= + ( )

a bq = r = − − · = · − · = − · ⇒

14 32 18 1

2 14 18 14 3 14 4 18 3,

= · +

1 1 242 32 7 18

= + ( )

b r q r = − · − · = · − · = − · ⇒

18 242 32 7

2 32 18 4 18 3 32 4 18 7,

= · +

1 2 2 32 18 1 14

= + ( )

r r q r = · − − · · = · − · = − · ⇒

32 75 8 2 42 3

2 32 4 242 32 7 7 32 53 242 7,

= · +

1 2 3 3 18 14 1 4 ( )

= +

r r q r = − · · − · ⇒

2 758 242 3 53 242 7

2

= · +

− − 14 4 3

n n n n

2 1 ( )

= + ·

r r q 1 −

53 166

= · + 2 4 2

2 758

= · +

4 2 2 0

−

n n n

1 ( ) = = · − ·

► : :

Esempio 726, 275 11 726 11 275 29

= · + 176

726 275 2 ( ) − · + · · − ·

= − · = − − · ⇒ ⇒

77 99 3 7 7 3 77 4 9

9 3

11 77 22 3 77 99 77 3

= · + 99

275 176 1 ( ) · − ·

== − · − · ⇒ · − · − · =

11 176 99 4 99 3 176 4 99 4 99 3 176 4 99 7

= · + 77

176 99 1 ( ) · − ·

= · − − · ⇒

11 176 4 275 176 7 176 11 275 7

= · + 22

99 77 1 ( ) − ·

= − · · − · ⇒ · − · − · ⇒

11 72

6 275 2 11 275 7 726 11 275 22 275 7 11.726 29 2

7

5

11

= · +

77 22 3 ( )

−

11 29

+ ·

= ·

1

1 726 2

7

5

= · +

22 11 2 0 +

canonica

Notare come l’identità di Bezout sia stata scritta e in forma e in forma

ha kb

−

non canonica, forma che ritroveremo nell’equazione diofantea.

ha kb

1.9 Equazione diofantea, a coefficienti interi

In generale è un’equazione di grado in incognite della quale si cercano

g k

soluzioni intere

. 2 2 2

+ =

x y z

Per esempio, l’equazione (di Pitagora!) è un’equazione di Diofanto...

Un tipo particolare di equazione diofantea che interessa questo lavoro è quella lineare in due incognite, ovvero l’identità di Bezout:

+ =

ax ny b

►

La ricerca di una coppia di valori per l’identità di Bezout equivale alla ricerca di una soluzione per l’equazione diofantea corrispondente.

L’argomento è di importanza fondamentale e sarà sviluppato nel capitolo 3.■

Leonardo Calconi – Algebra delle classi di resto 3

2 Classi di resto

2.1 Relazione di congruenza modulo n

∈

Se si definisce “di congruenza modulo ” una relazione su tale che:

n

n −

a b

( )

≡ ⇔ − = ⇒ = ∈

a b mod n a b nq , q , q

► n

ovvero tale che e divisi per danno lo stesso resto

a b n r

( ) ( )

= =

mod mod

a n b n r

►

2.2 Proprietà delle relazioni di congruenza

In linea generale le proprietà seguenti non sono invertibili.

( ) ( )

+ ≡ + ≡

Ad esempio, per la 2, se non è necessariamente vero che .

mod mod

a c b c n a b n

( ) ( )

≡ ≡

Ancora, per la 10, se non è necessariamente vero che .

mod mod

ac bc n a b n

( )

≡ mod

a b n

Se ( )

c c

≡

a b mod n

1. ( )
2. + ≡ + mod
3. a c b c n
4. ( )
5. ≡
6. 3. mod
7. ac bc n

( ) ( )

≡ ≡

Se mod, mod

a b n c d n

( )

+ ≡ + mod

a c b d n

4. ( )

≡

5. mod

ac bd n

( ) ,

≡

Se mod |

a b n d n

( )

≡ mod

a b d

6. ( ) ( )

,

≡ ≡

Se mod mod

a b n a b m

[ ]

( )

≡

7. mod ,

a b n m

è primo

Se n ( )

( ) ( )

n

+ ≡ +

n n

8. a b a b mod n

( ) ( )

,

≡ = prima proprietà di cancellazione del prodotto

Se ac bc mod n d c , n

( )

≡

9. a b mod n / d

( ) ( )

≡ = seconda proprietà di cancellazione del prodotto

Se ac bc mod n , c , n 1

( )

≡

10. a b mod n

2.3 Classe di resto

La relazione di congruenza ci permette di definire una classe di resto modulo come insieme

[r] n

degli interi che danno lo stesso resto se divisi per , ovvero che

r n

( ) =

► b mod n r [ ]

{ ( ) }

∈ = =

Pertanto avremo che b , n : b mod n r r

Tale relazione è una relazione di equivalenza che gode quindi delle tre proprietà:

( )

≡ riflessiva

1. a a mod n

( )

≡ simmetrica

2. b a mod n

Leonardo Calconi – Algebra delle classi di resto 4

( ) ( ) ( )

≡ ≡ ⇒ ≡ transitiva

3. a b mod n, b c mod n a c mod n

determina la partizione di in classi di resto che lo

Una relazione di congruenza modulo n n

esauriscono. La compilazione delle classi di resto è elementare partendo dalla classe o dalla colonna dei primi elementi. ►

► Con modulo con modulo

Esempio n = 3 Esempio n = 5

[0] = [..., -9, -6, -3, 0, 3, 6, 9, ...] [0] = [..., -15, -10, -5, 0, 5, 10, 15, ...]

[1] = [..., -8, -5, -2, 1, 4, 7, 10, ...] [1] = [..., -14, -9, -4, 1, 6, 11, 16, ...]

[2] = [..., -7, -4, -1, 2, 5, 8, 11, ...] [2] = [..., -13, -8, -3, 2, 7, 12, 17, ...]

► [3] = [..., -12, -7, -2, 3, 8, 13, 18, ...]

Con modulo

Esempio n = 4 [4] = [..., -11, -6, -1, 4, 9, 14, 19, ...]

[0] = [..., -12, -8, -4, 0, 4, 8, 12, ...]

[1] = [..., -11, -7, -3, 1, 5, 9, 13, ...]

[2] = [..., -10, -6, -2, 2, 6, 10, 14, ...]

[3] = [..., -9, -5, -1, 3, 7, 11, 15, ...]

L’insieme quoziente delle classi di resto, [0] [n-1] modulo n, gode di diverse proprietà.

n

2.4 Anello delle classi di resto

Le proprietà di sono quelle di un anello commutativo con unità:

• Chiusura rispetto all’addizione e alla moltiplicazione
• Esistenza dell’elemento neutro rispetto all’addizione e alla moltiplicazione