Algebra delle classi di resto 1

I

campo arriviamo agevolmente a parlare di inversi.

Per dimostrare ciò è necessario provare l’esistenza dell’elemento neutro moltiplicativo (l’unità) e

l’esistenza degli inversi per tutti gli elementi di .

I

Ecco una bella dimostrazione di I.N. Herstein.

Principio dei cassetti.

Se oggetti devono essere distribuiti in cassetti e il numero degli oggetti è maggiore di quello

n m

dei cassetti, allora uno o più cassetti conterranno due o più oggetti. Chiaramente, se ogni

n = m

cassetto contiene esattamente un oggetto.

Prova dell’esistenza dell’elemento neutro. ≠

Se è finito avrà un certo numero di elementi x x ,..., x e se è uno di questi, anche gli

I a 0

1, 2 n

x a x a x a

, , ...,

elementi appartengono ad e sono in numero di .

I n

1 2 n

Se essi sono tutti distinti, per il principio dei cassetti sono tutti gli elementi di .

I

Ma essi sono tutti distinti. ( )

= ≠ − =

Se infatti fosse x a x a per i j allora sarebbe , ed essendo dominio

I

x x a 0

i j i j

( ) ≠

− = ⇒ =

d’integrità dovrebbe necessariamente essere contro l’ipotesi i j .

x x 0 x x

i j i j

x a , x a ,..., x a

Allora sono tutti gli elementi di che possono essere scritti in tale maniera.

I

n

1 2 = =

Quindi stesso può essere scritto in modo analogo, ovvero .

a a x a ax

i i

0 0

( ) ( )

= = = = =

Ora, se è un elemento di sarà .

I

y x a yx x a x x ax x a y

i i i i i i i

0 0 0

=

x 1

Ma questa è proprio la scrittura secondo la quale è l’elemento neutro moltiplicativo di .

I

i 0

Prova dell’esistenza degli inversi.

Semplicemente, possiamo scrivere l’elemento neutro come multiplo di come abbiamo fatto in

a

=

precedenza, , il che dimostra che è l’inverso di e viceversa. E poichè è un elemento

b a a

ba

1

qualsiasi di tutti i suoi elementi hanno l’inverso e quindi è un campo.

I I

Leonardo Calconi – Algebra delle classi di resto 6

2.6 Campo delle classi di resto e inversi

Se il modulo è un numero primo, ogni elemento diverso da zero ammette l’inverso ed un anello

n

commutativo con unità con questa proprietà è un campo.

[ ] ][ ]

[ [ ]

[ ] ( ) ( )

∈ = ∈ = ≡

Dato se esiste ovvero è .

a a n a a a aa n

, 1 : 1 1 mod

i i

n n i

− = ⇒ − =

aa kn aa kn

1 1

Ciò significa che , e quest’ultima è un’equazione diofantea che, data

i

i

l’ipotesi, ammette soluzioni in , delle quali una è senz’altro .

a k

,

n i

[ ] ( ) = ≠

L’inverso di non esiste in quanto .

n n

0 0, 1

L’esistenza degli inversi conferma l’assenza di divisori dello zero.

[ ] [ ] [ ][ ]

≠ =

a b a b

, 0 0

Infatti, dati se fosse vero che potremmo scrivere

[ ][ ][ ] [ ][ ] [ ] [ ][ ] [ ] [ ]

= ⇒ = ⇒ = il che va contro l’ipotesi.

a a b a b a b

0 0 0

i i i

Concludiamo sottolineando che se la primalità di garantisce l’esistenza degli inversi di tutti gli

n

elementi della classe di resti, non è vero che se non è primo tali inversi non esistono del tutto.

n

Se non è un campo essi esisteranno solo per quegli elementi dell’anello che non sono divisori

n

dello zero.

Ma come si calcola un inverso ?

2.7 Calcolo degli inversi nell’anello delle classi di resto modulo n

n

Se il modulo della classe di resti non è primo, possiamo calcolare gli inversi solo di quegli

n ( ) ( )

⇔

≡ =

elementi che con sono primi:

n aa n a n

1 mod , 1

i

( ) ( ) ( )

≡ = + ⇒ =

Se allora esiste un intero per cui . Di qui

k

aa n aa kn a n a n

1 mod 1 , | 1 , 1

i i

( ) = + = ∈

a n aa ny a y

, 1 1, ,

Del resto se si può scrivere l’identità di Bezout e da questa la

i i

( )

≡

congruenza per la quale è l’inverso di

a a.

aa n

1 mod i

i

Quindi in generale possiamo ridurre il problema del calcolo di un inverso alla ricerca della

soluzione dell’equazione diofantea

a y

,

i

+ =

aa ny 1

i

ottenuta scrivendo l’identità di Bezout .

Come visto nelle Premesse, tale soluzione può essere ricavata con l’algoritmo di Euclide per

divisioni successive, ottenendo una coppia di valori che non è unica e appartenendo tutte le delle

a i

coppie di valori alla classe di resto inversa che è pertanto univocamente determinata.

( )

≡

in

► Esempio: : 117 5 mod16

16

Con l’algoritmo di Euclide troviamo immediatamente la coppia

( )

= = −

a y

13, 95

i 0 0

come soluzione della diofantea

+ = ⇒ ⋅ − ⋅ =

a y

117 16 1 117 13 16 95 1

i ( )

⇒ ⋅ ≡

Quindi 13 è l’inverso di 117 117 13 1 mod16

Ma anche (29,-212) è soluzione così come sono soluzioni tutte le coppie

= + = − − ∈

a k y k k

13 16 , 95 117 ,

ik k [ ] [ ] [ ] [ ] [ ]

∈ ⇒ ⋅ =

, questo è l’elemento inverso di

e poichè tutte le a 13 5 5 13 1

ik

Leonardo Calconi – Algebra delle classi di resto 7

primo, è il piccolo teorema di Fermat per

Un metodo di calcolo elegante, benchè valido solo per n

arrivare al quale occorre una catena di teoremi T:

T. di Lagrange → Corollario del T. di Lagrange → T. di Eulero → Piccolo T. di Fermat

2.7.1 Teorema di Lagrange

G’ G (G’)| (G).

Se è un sottogruppo di di ordine finito, allora

G G’ G

≠

Dati di ordine finito e il suo sottogruppo di ordine con elementi , per un

n m z , z ,...,z

1 2 m

G G’ G’ G

∈ ∉

elemento , possiamo sicuramente costruire almeno due laterali destri di in :

a a

1 1

z e, z e,...,z e = z , z ,...,z

1 2 m 1 2 m

z a , z a ,...,z a

1 1 2 1 m 1 G (G) (G’)

Tutti gli elementi dei due laterali sono distinti e se essi esauriscono allora ed il

= 2

teorema è dimostrato. G

Se così non è possiamo iterare il procedimento sino ad che non sia esaurito (è un gruppo di

ordine finito) il che avverrà per il suo -esimo elemento .

k a k

(G) (G’) (G’)| (G).

A questo punto si ha che k e quindi

=

2.7.2 Corollario del teorema di Lagrange

G G | (G).

∈

Se è di ordine finito e allora ( )

a a G’ G

La dimostrazione è immediata considerando un sottogruppo ciclico di generato da il cui

a

(G’)| (G) | (G).

ordine è ( ). Pertanto poichè segue che ( )

a a

2.7.3 Teorema di Eulero ( )

( ) ϕ ≡

= ( n )

a n

, 1

Se allora è a 1 mod n ( )

ϕ è una funzione moltiplicativa che esprime il numero di

Ricordiamo che la funzione di Eulero n

interi minori di e con esso relativamente primi.

n è primo con allora appartiene al gruppo moltiplicativo che ha

Per il teorema di Lagrange se a n Z

n

( ) ( )

ϕ ϕ

ordine . Per il corollario del teorema di Lagrange l'ordine di è allora un divisore di e

a

n n

( ) ( )

( ) ϕ

≡ ⇒ ≡

a ( n )

quindi a 1 mod n a 1 mod n .

2.7.4 Piccolo teorema di Fermat

Se è primo si ha un caso particolare del teorema di Eulero per cui:

n = p

( )

p ≡

a a p

mod

( ) =

a p

, 1 si ha

e se ( )

−

p 1 ≡

a p

1 mod

Si dimostra per induzione.

Come quasi sempre in questo tipo di dimostrazione, per il primo elemento, , il risultato è

a = 0

ovvio. Allora supposto vero per , dobbiamo dimostrare che è vero anche per l’elemento successivo

a ( ) ( ) ( )

p p p p

+ ≡ + ≡

. Notando che per la proprietà 8 e che , si avrà

a + 1 a a p p

1 1 mod 1 1 mod

( ) ( )( )

p

+ ≡ +

che cvd.

a a p

1 1 mod

Questo teorema di Fermat è detto Piccolo non perchè di scarsa importanza, ma per distinguerlo dal

popolarissimo Ultimo che è il Grande.

Leonardo Calconi – Algebra delle classi di resto 8

2.8 Calcolo degli inversi nel campo delle classi di resto modulo p

p

Il piccolo teorema di Fermat ci permette di calcolare gli inversi con primo e ( ) = 1:

p a, p

( )

:

• ≡

a aa p

1 mod

i i

[ ] [ ][ ] [ ]

:

• ∈ .

a a a 1

i i ( )

− − −

p 1 p 2 p 2

= ⇒ ≡ dove

Infatti possiamo scrivere a aa aa 1 mod p

−

p 2

• è l’inverso di mod. p

a

a a

= i [ ] [ ]

 

−

p 2

• = è l’inverso di mod. .

p

a a a

  i

( ) ( ) ( )

≡ ⇒ ≡ ⇒ ≡

3

► 7 2 mod 5 7 3 mod 5 8 3 mod 5

Esempio: ( )

= = ⇒ = ⇒ ⋅ ≡

3

Quindi a 7, a 7 a 8 7 8 1 mod 5

i

i

[ ] [ ] [ ] [ ] [ ] [ ]

⋅ =

∈ = = ⇒

3

7 , 8 3 , a 2, a 3 2 3 1

i

come risulta dalla tabella seguente

[ ] [ ] -12 -7 2 7 12 17 22

=

a 2

[ ] [ ] -13 -8 3 8 13 18 23

=

a 3

i

[ ][ ] [ ] -156 -56 6 56 156 306 506

∈

a a 1

i ( ) ( ) ( )

15

≡ ⇒ ≡ ⇒ ≡

► Esempio: 21 4 mod17 21 13 mod17 13 13 mod17

( )

=

= = ⇒ ⇒ ⋅ ≡

15

a 21, a 21 a 13 21 13 1 mod17

Quindi i

i

[ ] [ ] [ ] [ ] [ ] [ ]

⋅ =

∈ = = ⇒

15

21 ,13 13 , a 4, a 13 4 13 1

i

Come si vede, nei due esempi il Teorema di Eulero conferma gli inversi trovati.

Ci sono dei dubbi ? G G’ G

∈

a , b

In ogni caso ricordiamo che dato un gruppo ed un suo sottogruppo , se allora

G’ G’. G

−

1

⇔

≡ ∈

(mod ) Nel secondo esempio se è il gruppo delle classi di resto modulo 17 e

a b ab ( )

G’ − −

1 1

≡ ⇔ ∈

il sottogruppo classe di resto [1], sarà esattamente .

aa a a

1 mod17 [ ][ ] [1]

Il fatto che possiamo calcolare gli inversi per tutti gli elementi diversi da zero dell’insieme

classi di resto modulo prova che tale insieme è un campo