Lezione 8
Prerequisiti: L'insieme dei numeri interi. Relazioni di equivalenza, insiemi quozienti. Lezioni 5-7.
La congruenza modulo n.
Gli anelli
n.
Sia n un numero intero positivo.
Definizione 8.1 Siano a b, . Diremo che a è congruo a b modulo n se n divide a b . In tal caso scriveremo a b (mod ).n
Nota Ciò definisce una relazione binaria su , detta congruenza modulo n.
Proposizione 8.2 La congruenza modulo n è una relazione di equivalenza.
Dimostrazione: Per ogni a, n divide a a 0, quindi a a (mod ).n Ciò prova che la congruenza modulo n è riflessiva. Siano ora a b, tali che a b (mod ).n Allora n divide a b , e quindi, divide anche il suo opposto b a (vedi Corollario 6.8). Dunque b a (mod ).n Ciò prova che la congruenza modulo n è simmetrica. Infine, siano a b c, , tali che a b (mod )n e
(mod ).
b c n Allora n divide a b e b c , e quindi, in base alla Proposizione 6.9 (a), divide anche la loro somma a b b c a c .Pertanto a c (mod ).n Ciò prova che la congruenza modulo n è transitiva.
Nota Per ogni a,la classe di equivalenza di a rispetto alla congruenza modulo n si chiama classe di congruenza di a modulo n (o classe di resto di a modulo n), e si indica con
a . Si ha, n evidentemente: [ ]a n
a kn k | L'insieme quoziente di
. rispetto alla congruenza modulo n si denota con il simbolo . nEsempio 8.3 Siccome 1 divide ogni numero intero, per ogni a b, si ha a b (mod 1). Quindi la congruenza modulo 1 dà luogo ad un'unica classe di congruenza, che coincide con tutto . Essa è la classe di congruenza di ogni numero intero, in particolare di 0. Quindi 1
[0] .1Consideriamo ora la congruenza modulo 2. Siano a b, . Allora a b (mod 2)vale se e solo se a b è pari, e ciò vale se e solo se a b, sono entrambi pari, oppure entrambi dispari. Quindi le classi di congruenza modulo 2 sono esattamente 2: una è l'insieme dei numeri pari, l'altra l'insieme dei numeri dispari. La prima è la classe di congruenza di 0, l'altra la classe di congruenza di 1. Quindi
2 [0] ,[1] .2 2
In generale si ha la seguente
Proposizione 8.4 (Cardinalità di ) Per ogni intero positivo n, n ha n elementi e, precisamente, n
[0] ,[1] ,...,[ 1] .
n n n n n
Dimostrazione: Per definizione di insieme quoziente, n
[ ]a an
.Poniamo
[0] ,[1] ,...,[n n 1] .n
S n Proviamo che n S. Naturalmente, n S. Proviamo l'altra inclusione. Sia a. Sia r il resto della divisione euclidea di a per n. Allora, detto q il quoziente della stessa divisione euclidea, si ha a nq r , e quindi n divide a r ,cioè a r (mod ).n Dunque [ ]a n [ ]r n Ciò prova che S. n S.
Per provare che (cioè S) ha n elementi, occorre provare che le classi [0] ,[1] ,...,[ 1]n n n n n sono a due a due distinte. Ora, siano i j,
0,1,...,n tali che [ ]1
i n [ ] .j n Poiché i n 0 i, e 0 i n,i è il resto della divisione euclidea di i per n. D'altra parte, per ipotesi, n divide i j quindi si ha , i nq per qualche j q. Poiché 0 j n, segue che anche j è il resto della divisione di i per n.Per l'unicità del resto segue così che i j.
Nota Gli elementi 0,1,...,n1 si dicono i rappresentanti canonici della congruenza modulo n.
Se a a0, ,...,1 an1 sono tali che n
[ ] ,[ ] ,...,[a0 n a1 n an1] ,n
si dice che
a a0, ,...,1 an1
è un sistema completo di rappresentanti per la congruenza modulo n. Ciò avviene se e solo se i numeri0, ,...,1 n 1
a a a sono a due a due non congrui modulo n.
Esempio 8.5 Si ha 3
[0] ,[1] ,[2] .3 3 3
Un sistema completo di rappresentanti per la congruenza modulo 3 è
3, 4,5 , o anche
339,3001,12362 .
Studiamo ora il comportamento della congruenza modulo n rispetto alle operazioni aritmetiche.
Proposizione 8.6 (Compatibilità della congruenza rispetto alla somma e al prodotto) Siano , ', , '
a a b b tali che a a ' (mod )n e b b ' (mod )n . Allora (i) a b a b ' ' (mod )n ;
(ii) ab a b ' ' (mod )n .
Dimostrazione: Per ipotesi n divide a a ' e divide b b '.Quindi n divide anche la loro somma ' ' ( ) ( ' '),
a a b b a b a b cioè a b a b ' ' (mod ).n Ciò prova (i). D'altra parte, n divide anche b a a( ') e a b b'( ') in virtù della Proposizione 6.9 (c), e quindi divide anche la loro somma
( ') '( ') ' ' ' ' ' '.
b a a a b b ba ba a b a b ab a b Pertanto ab a b ' ' (mod ).n Ciò prova (ii).
Nota Le proprietà (i) e (ii) della Proposizione 8.6 si possono riassumere dicendo che la congruenza modulo n è compatibile rispetto alla somma e al prodotto.
Queste proprietà consentono di dotare l'insieme di una struttura di anello. Definiamo su di esso n le seguenti operazioni:
- una somma, ponendo, per ogni a b, , [ ]a n [ ]b n [a b]n; - un prodotto, ponendo, per ogni a b, , [ ] [ ]a n b n [a b] .n
Queste definizioni sono ben poste, ossia la classe di congruenza a secondo membro non dipende dalla scelta dei rappresentanti a e b nelle classi di congruenza a primo membro: infatti, in base alla Proposizione 8.6, se [ ]a n [ ']a n e [ ]b n [ '] ,b n allora [a b ]n [ 'a b ']n e [a b ]n [ ' '] .a b n
Si verifica facilmente che, rispetto a queste operazioni, è un anello commutativo unitario. n L'elemento zero è [0]n, l'elemento uno è [1]n. Inoltre, per ogni a, l'opposto di [ ]a è n [n a ]n [ a] .n
Proposizione 8.7 (Elementi invertibili in ) Sia n a. Allora [ ]a n è invertibile se e solo se n a e n sono coprimi.
Dimostrazione: L'elemento [ ]a n ammette un inverso [ ]n u n se e solo se esiste n u tale che [ ] [ ]a un n [ ]au n [1]n, ossia tale che n divide au1. Ciò equivale alla seguente condizione:
esistono u v, tali che nv au 1, cioè tali che au nv 1.In base alla Proposizione 6.22, ciò avviene se e solo se a e n sono coprimi.
Esempio 8.8 Determiniamo il gruppo delle unità di per alcuni valori di n. n n U(n)
2
[1] 23
[1] ,[2] 3 3
4
[1] ,[3] 4 4
5
[1] ,[2] ,[3] ,[4] 5 5 5 5
6
[1] ,[5] 6 6
7
[1] ,[2] ,[3] ,[4] ,[5] ,[6] 7 7 7 7 7 7
8
[1] ,[3] ,[5] ,[7] 8 8 8 8
Risulta, in particolare, che sono campi. Gli anelli 2, 3, 5, 7 che sono campi si possono n
facilmente caratterizzare.
Proposizione 8.9 (Gli anelli p) Sia n un intero maggiore di 1. Sono equivalenti le seguenti condizioni.
(i) n è primo;
(ii) è un campo; n (iii) è integro. n
Dimostrazione: (i)(ii) Sia n primo. Allora n non divide nessuno dei numeri 1, 2,...,n1, e quindi, in base all'Esercizio 7.11, n è coprimo con ciascuno di essi. Pertanto, in virtù della Proposizione 8.7, U(n)
[1] ,...,[n n1]n
n \ [0] .
n Ciò prova che (che ha più di un n elemento) è un campo.(ii)(iii)Ovvio, poiché ogni campo è un dominio di integrità (vedi Corollario 5.18).
(iii)(i)Supponiamo che n non sia primo e proviamo che allora non è integro. Poiché n non è n irriducibile (vedi Lemma 7.3), esistono a b, non invertibili tali che n ab . Possiamo supporre
che essi siano positivi. Allora a1 e, di conseguenza, b n . Invertendo i ruoli di a e b, si deduce quindi che a e b verificano entrambe le disuguaglianze, cioè a b,
1, 2,...,n1 .
Ma allora [ ] ,[ ]a n b sono diversi da [0] ,n n mentre [ ] [ ]a bn n [ ]n n [0]n. Risulta così violata la legge di annullamento del prodotto, il che prova che non è integro. n Esempio 8.10 Gli anelli e 4 non sono integri. Si hanno, infatti, le seguenti violazioni della 6
legge di annullamento del prodotto:
4 4 4
6 6 6
[2] [2] [0]
[2] [3] [0]
Dunque, in , 4 [2] è un divisore dello zero, e, in 4 , 6 [2] e 6 [3] sono divisori dello zero. 6 Il prossimo esercizio precisa il significato della Proposizione 8.9.
Esercizio 8.11* Sia a non divisibile per n. Allora [ ]a n è un elemento regolare se e solo se n è invertibile.
Abbiamo quindi, tra gli anelli , infiniti esempi di campi e di anelli non integri. Abbiamo, inoltre, n esempi che illustrano la seconda parte dell'Osservazione 5.29, secondo cui un sottoanello di un anello unitario può avere un elemento uno diverso da quello dell'anello.
Esercizio 8.12 Si provi che B
[0] ,[3]6 6
è un sottoanello di , e che 6 [3] è il suo elemento 6uno.
Svolgimento: Utilizziamo la seconda caratterizzazione dei sottoanelli (Corollario 5.25). Anzitutto si ha: [0]6[0]6 [0] , [0]6 6[3]6 [3] , [3]6 6[0]6 [3] , [3]6 6[3]6 [0]6 e tutti questi elementi appartengono a B. Quindi la prima condizione della caratterizzazione è soddisfatta. Per quanto riguarda la seconda, basta osservare che [0] [0]6 6 [0] , [0] [3]6 6 6 [3] [0]6 6 [0] , [3] [3]6 6 6 [3] .6 Dal calcolo del secondo e del terzo prodotto risulta che [3] è l'elemento neutro della moltiplicazione di 6 B.
Il sottoanello B di è dunque dotato di un elemento uno proprio, diverso da 6 [1] . 6
La proprietà di sottoanello di B si può provare anche in maniera più concisa ed elegante. Si consideri, a tal fine, l'applicazione f :6 definita da 6 [ ]a 6[3 ]a 6 per ogni a. Si può facilmente provare che f è un omomorfismo di anelli, la cui immagine è B. Questo è allora un sottoanello di in base al 6 Corollario 5.40. Inoltre f induce per corestrizione un epimorfismo di anelli f ' :6 B.Allora dalla Proposizione 5.42 segue che f([1] ) [3]6 6è l'elemento uno di B.
Esercizio 8.13* Provare i seguenti criteri di divisibilità, basati sulla rappresentazione decimale di un numero intero positivo.
Sia n un intero positivo,
0
10 ,
N i
i i
n a
ove, per ogni indice i, a è un intero tale che 0i ai 9.Allora
(a) 3 divide n se e solo se 3 divide
0 N ;
i i
a
(b) 9 divide n se e solo se 9 divide
0
;
N i i
a
(c) 11 divide n se e solo se 11 divide
0
( 1) ;
N i
i i
a
(d) 5 divide n se e solo se a0
0,5 ;(e) per ogni intero r tale che 1 r N, 2r divide n se e solo se 2r divide 1
0 r 10 .
i i i
a
