CAPITOLO 4

Aritmetica Modulare

 

4.1 Gli interi modulo n     4.2  Funzione di Eulero e piccolo teorema di Fermat     4.3  Congruenze lineari     4.4  Esercizi

4.1  Gli interi modulo n

Sia n un intero e consideriamo la relazione Â_n in Z cosí definita:

aÂn b     Û    a-b = hn,     per qualche intero   h Î Z.

La relazione Â_n risulta d'equivalenza e si chiama congruenza modulo n. Per indicare che a é nella relazione Â_n con b si scrive anche

DEFINIZIONE 1 L'insieme quoziente Z/Â_n si denota con Z_n, o con Z/nZ, e si chiama insieme degli interi modulo n. La classe d'equivalenza di un elemento a Î Z rispetto ad Â_n si denota con [a]_Ân o piú semplicemente con [a], se non vi é luogo ad equivoci. ¨

Poiché risulta

· n = 0  Þ  Â₀   é la relazione di uguaglianza in Z;

· n = 1  Þ  aÂ₁b  , per ogni a,b Î Z   Þ  [a]_Â1 = [b]_Â1 = Z   , per ogni a,b Î Z ;

· Â_n = Â_-n ;

nel seguito supporremo sempre n > 1. Per la congruenza modulo n valgono le seguenti proprietá e osservazioni:

· [0] = { hn   :   h Î Z } (questo è l'insieme dei multipli di n e si denota anche con nZ).

· a ¹ 0   Þ  [a] = { a+hn   :   h Î Z } (questo insieme si denota anche con a+nZ).

· 0 £ a < n    Þ    n-a º -a(mod n).

· r = resto della divisione tra a ed n   Þ   a º r(mod n).

· Il numero delle classi di congruenza modulo n é esattamente n e risulta

Zn = { [0], [1], ... ,[n-1]} .

OSSERVAZIONE 2 In forza dell'ultima proprietá abbiamo che, per ogni intero a, il piú piccolo intero non negativo appartenente ad [a]_Ân é il resto della divisione di a per n. In altre parole, le classi d'equivalenza modulo n sono in corrispondenza biunivoca con i possibili resti della divisione per n e, quindi, possono identificarsi con questi. Per tale motivo esse si chiamano anche classi dei resti modulo n e nel seguito, se non vi é luogo ad equivoci, saranno denotate semplicemente con 0,1,... ,n-1, omettendo le parentesi quadre. Piú in generale, con abuso di notazione, spesso scriveremo a in luogo di [a], per ogni intero a.
In molti testi il resto r della divisione di a per n é denotato col simbolo a  mod  n  . In questo caso le scritture b   = a  mod  n e b º   a  mod  n hanno significato diverso: la prima dice che é b = r, la seconda che b-a é un multiplo di n. ¨

Altre due importanti proprietá, che si consiglia di dimostrare per esencizio, sono:

· x,x¢ Î [a],  y,y¢ Î [b]   Þ   [x+y] = [x¢+y¢].

· x,x¢ Î [a],  y,y¢ Î [b]   Þ   [xy] = [x¢y¢].

Queste assicurano che in Z_n le seguenti operazioni di addizione e moltiplicazione risultano ben definite ¹ :

[a]+[b] = [a+b]     ,     [a][b] = [ab].

Le operazioni di addizione e moltiplicazione in Z_n verificano le seguenti proprietá fondamentali:

· ([a]+[b])+[c] = [a]+([b]+[c]),

· [a]+[0] = [0]+[a] = [a],

· [a]+[-a] = [0],

· [a]+[b] = [b]+[a],

· ([a][b])[c] = [a]([b][c]),

· [a][1] = [1][a] = [a],

· [a][b] = [b][a],

· ([a]+[b])[c] = [a][c]+[b][c],

OSSERVAZIONE 3 Il fatto che valgono le sopraelencate proprietá si esprime dicendo che Z_n, rispetto alle operazioni di addizione e moltiplicazione, é un anello commutativo unitario nel quale lo zero é [0] e l'unitá é [1]. Lo studio di questo anello si chiama aritmetica modulo n, o aritmetica modulare. ¨

Riportiamo come esempi le tabelline delle operazioni (tabelle di Cayley) di Z₂,Z₃,Z₄,Z₅.

TABELLE DI CAYLEY DI Z₂

TABELLE DI CAYLEY DI Z₃

OSSERVAZIONE 4 L'aritmetica modulo 2 si presta a svariate applicazioni perché é riproducibile mediante i due possibili stati di alcuni sistemi fisici per i quali il passaggio da uno stato all'altro é regolato dall'addizione o dalla moltiplicazione in Z₂. Ad esempio, se ad un circuito elettrico facciamo corrispondere 0 quando é aperto e 1 quando é chiuso, le operazioni definite su Z₂ possono realizzarsi usando i circuiti descritti nella figura 4.1 . ¨

Figura 4.1

ESERCIZIO 5 Sia

n = rm10m+rm-110m-1+¼+r2102+r110+r0.

Provare che risulta n º r_m+r_m-1+¼+r₂+r₁+r₀ (mod 9).

SOLUZIONE.   · 10^m-1 = 999¼9 (m volte 9) = 9·10^m-1+9·10^m-2+¼+9·10²+9·10+9 Þ 10^m-1 º 0(mod 9).

· n-(r_m+r_m-1+¼+r₂+r₁+r₀) = (r_m10^m+¼+r₁10+r₀)-(r_m+¼+r₁+r₀) = (10^m-1)r_m+¼+(10²-1)r₂+(10-1)r₁ º 0(mod 9). _¨

ESERCIZIO 6 Dimostrare i seguenti criteri di divisibilitá:

· un intero é divisibile per 2 se, e solo se, la sua ultima cifra decimale é pari;

· un intero é divisibile per 3 se, e solo se, la somma delle sue cifre decimali é divisibile per 3;

· un intero é divisibile per 4 se, e solo se, l'intero corrispondente alle sue ultime due cifre decimali é divisibile per 4;

· un intero é divisibile per 5 se, e solo se, la sua ultima cifra decimale é divisibile per 5;

· un intero é divisibile per 9 se, e solo se, la somma delle sue cifre decimali é divisibile per 9;

· un intero é divisibile per 2^h se, e solo se, l'intero corrispondente alle sue ultime h cifre decimali é divisibile per 2^h.

ESERCIZIO 7 Provare che un intero é divisibile per 11 se, e solo se, la somma a segni alterni delle cifre nella sua rappresentazione decimale é divisibile per 11 (si tenga presente che 10 º -1 (mod 11)).

ESERCIZIO 8 Trovare il resto della divisione per 9 di un intero del tipo 83^6a.

SOLUZIONE.   Si tratta di trovare l'unico intero r compreso fra 0 e 9 tale che

836a º r (mod 9).

Poiché é

83 º 2 (mod 9),

risulta

836a º 26a (mod 9).

D'altra parte, essendo

26a = (26)a       e      26 º 1 (mod 9),

abbiamo

26a º 1 (mod 9).

Ne segue che

836a º 1a º 1 (mod 9) ,

cosí il resto cercato é 1. ¨

4.2  Funzione di Eulero e piccolo teorema di Fermat

Diverse proprietá di un intero n > 1 dipendono, oltre che dalla sua fattorizzazione in primi, anche dal numero di interi compresi fra 1 ed n e coprimi con n. É questa la motivazione per la seguente definizione.

DEFINIZIONE 1 Per un intero n > 1 si denota con F(n) il numero degli interi positivi minori di n e coprimi con esso. La funzione F si chiama funzione di Eulero. ¨

ESERCIZIO 2 Provare che F(n) = n-1 se, e solo se, n é primo.

PROPOSIZIONE 3 Per ogni primo positivo p e per ogni intero h > 0, risulta

F(ph) = ph-ph-1  .

(4.1)

DIMOSTRAZIONE.   Gli interi positivi minori di p^h che non sono coprimi con p^h sono tutti e soli quelli del tipo mp, con 1 £ m £ p^h-1, e da ció segue l'asserto. ¨

PROPOSIZIONE 4 Se p e q sono primi positivi distinti, risulta

F(phqk) = F(ph) F( qk) = phqk æ ç è 1- 1/p ö ÷ ø æ ç è 1- 1/q ö ÷ ø ,

per ogni h,k Î N.

DIMOSTRAZIONE.   É lasciata per esercizio al Lettore. ¨

COROLLARIO 5 Se a,b sono due interi positivi coprimi, risulta

F(a,b) = F(a) F( b) .

PROPOSIZIONE 6 Sia n > 1 un intero e siano p₁,p₂,... ,p_h i primi positivi che dividono n. Allora risulta

F(n) = n æ ç è 1- 1/p1 ö ÷ ø æ ç è 1- 1/p2 ö ÷ ø ¼ æ ç è 1- 1/ph ö ÷ ø .

(4.2)

DIMOSTRAZIONE.   É un immediato corollario delle due precedenti proposizioni. ¨

Denotiamo, ora, con Z^*_n l'insieme degli elementi non nulli di Z_n.

DEFINIZIONE 7 Un elemento a Î Z^*_n si dice invertibile se esiste un elemento b Î Z^*_n tale che ab = 1. In questo caso b si chiama inverso di a e si denota con a^-1. L'insieme degli elementi invertibili di Z_n si denota con U(n). ¨

TEOREMA 8 Un elemento a Î Z^*_n é invertibile se, e solo se, a ed n sono coprimi in Z.

DIMOSTRAZIONE.   Si ha:

· ax = 1 in Z_n   Þ   ax º 1(mod n)   Þ   ax-1 = hn, per qualche h Î Z   Þ   ax-hn = 1   Þ   MCD(a,n) = 1.

· MCD(a,n) = 1   Þ   ha+kn = 1, per qualche h,k Î Z   Þ   ha-1 = -kn   Þ   ha º 1(mod n)   Þ   ha = 1 in Z_n. ¨

COROLLARIO 9 Il numero degli elementi invertibili di Z^*_n é uguale a F(n).

COROLLARIO 10 Gli elementi di Z^*_n sono tutti invertibili se, e solo se, n é un primo. In tal caso Z_n é un campo.

OSSERVAZIONE 11 Se a ed n sono coprimi, il calcolo di a^-1 in Z_n puó effettuarsi andando a trovare una soluzione (b,h) in Z dell'equazione

ax+ny = 1  .

Per (b,h)  , infatti, risulta ab = 1-nh  ; cioé b = a^-1 in Z_n . Facciamo presente che esistono algoritmi efficienti per risolvere la precedente equazione. ¨

OSSERVAZIONE 12 In Z_n puó accadere che il prodotto di due elementi diversi da zero sia uguale a zero, cioé che non valga la legge di annullamento del prodotto. Per esempio, in Z₆ risulta [2][3] = [0] ed é [2] ¹ [0] e [3] ¹ [0]. ¨

ESERCIZIO 13 Provare che in Z_n vale la legge di annullamento del prodotto se, e solo se, l'intero n é primo.

DEFINIZIONE 14 Un elemento a Î Z^*_n si dice divisore dello zero se esiste un elemento b ¹ 0 tale che ab = 0. ¨

PROPOSIZIONE 15 Un elemento a Î Z^*_n é divisore dello zero se, e solo se, a ed n non sono coprimi.

DIMOSTRAZIONE.   Se a ed n non sono coprimi, per d = MCD(a,n), abbiamo 1 < d £ n, cosí b = n/d é minore di n e risulta ab = 0 in Z_n. Se ab = 0, con 0 < a,b < n, allora n non divide a, non divide b e divide ab; ne segue che MCD(a,n) ¹ 1. ¨

ESERCIZIO 16 Provare che il prodotto di due elementi di U(n) é un elemento di U(n).

TEOREMA 17 (teorema di Fermat-Eulero) Siano a,n due interi positivi coprimi con n > 1. Allora risulta

aF(n) º 1(mod n).

(4.3)

DIMOSTRAZIONE.   Cominciamo con l'osservare che, se y Î U(n) e poniamo

yU(n) = { yx    :    x Î U(n)},

risulta yU(n) = U(n). Posto, allora, k = F(n), sia

U(n) = { x1,x2,... ,xk }

e poniamo y = x₁x₂¼x_k . Poiché a Î U(n) e aU(n) = U(n), in Z_n abbiamo

y = x1x2¼xk = (ax1)(ax2)¼(axk) = aky.

Essendo y invertibile in U(n), possiamo moltiplicare l'ultima uguaglianza per y^-1 e otteniamo che

1 = ak

in Z_n, come volevamo dimostrare. ¨

OSSERVAZIONE 18 Il teorema di Fermat-Eulero, asserendo che

aaF(n)-1 = aF(n) º 1(mod n)

quando l'intero a é coprimo con n, puó anche riformularsi dicendo che in Z_n, se un elemento b é invertibile, risulta b^-1 = b^F(n)-1  . Questa osservazione chiarisce che il calcolo dell'inverso di b in Z_n attraverso la (4.3) richiede la conoscenza di F(n) e, quindi, della fattorizzzione in primi di n. ¨

TEOREMA 19 (piccolo teorema di Fermat) Sia p un primo positivo. Allora risulta

ap º a (mod p),     per   ogni  intero  positivo  a  ;

(4.4)

o, equivalentemente,

ap-1 º 1 (mod p),     per   ogni  intero  positivo  a  non  divisibile  per  p  .

(4.5)

DIMOSTRAZIONE.   Se p non divide a, abbiamo F(p) = p-1 e quindi a^p-1 = a^F(p). Ne segue, per il teorema di Fermat-Eulero, che a^p-1 º 1(mod p) e quindi a^p º a(mod p). Se p divide a, la (4.4) é banale. ¨

COROLLARIO 20 Se p é un primo positivo e b un elemento non nullo di Z_p, risulta

b-1 = bp-2  ;

(4.6)

o, equivalentemente,

ap-1 º 1 (mod p),     per   ogni  intero  positivo  a < p .

(4.7)

OSSERVAZIONE 21 Il piccolo teorema di Fermat, per ogni intero positivo a < m, dá una condizione necessaria (che nell'antica Cina, per a = 2, si riteneva fosse anche sufficiente) affinché un intero positivo m > 1 sia primo:

m   primo  Þ  m | (am-a)  .

Purtroppo queste condizioni non sono sufficienti e i primi due controesempi, per a = 2, sono m = 341 = 11·31 (diciottesimo secolo) e m = 561 = 3·11·17 . Gli interi m > 1 che verificano il "test cinese" per un fissato a, cioé tali che m | (a^m-a) , prendono il nome di pseudoprimi in base a. Piú in generale si ha che il piccolo teorema di Fermat non é invertibile e, quindi, non puó essere utilizzato come test di primalitá. Esistono, infatti, interi non primi m > 1, divisibili per a^m-a, per ogni intero positivo a < m. Questi sono noti come numeri di Carmichael e i primi due esempi sono 561 e 1729 = 7·13·19. ¨

4.3  Congruenze lineari

Se a,b,m sono interi con m > 1, l'equazione in x

ax º b (mod m)

(4.8)

prende il nome di equazione congruenziale lineare, o congruenza lineare, e una sua soluzione é, per definizione, un intero [`x] tale che a[`x] º b (mod m). Osserviamo che l'essere [`x] una soluzione della (4.8) equivale all'esistenza di un intero n tale che a[`x]-b = nm, cioé a[`x]-mn = b. Allora la prop. equivale alla seguente proposizione.

PROPOSIZIONE 1 La congruenza lineare (4.8) ha soluzioni se, e solo se, MCD(a,m) divide b.

PROPOSIZIONE 2 Nell'ipotesi che l'equazione (4.8) abbia una soluzione c, poniamo d = MCD(a,m) e m = dm₁. Allora le soluzioni della (4.8) sono tutte e sole quelle del tipo

DIMOSTRAZIONE.   É  lasciata per esercizio al Lettore. ¨

PROPOSIZIONE 3 Nell'ipotesi che l'equazione (4.8) sia risolubile, poniamo d = MCD(a,m), m = dm₁ e sia c una sua soluzione. Allora, le soluzioni della (4.8) a due a due incongrue modulo m sono esattamente d e precisamente:

c  ,  c+m1  ,  c+2m1  ,  ...  ,  c+(d-1)m1 .

(4.10)

DIMOSTRAZIONE.   E' chiaro che le soluzioni (4.10) sono a due a due incongrue modulo m. Sia, dunque, c+nm₁ una soluzione della (4.8) e sia n = dq+r, con q,r quoziente e resto della divisione di n per d. Allora é 0 £ r < d,

c+nm1 = c+(dq+r)m1 = c+dqm1 + rm1 = c+ qm + rm1 º c+rm1 (mod m)

e l'asserto é completamente provato. ¨

TEOREMA 4 (teorema di cinese del resto) Siano m₁,m₂ interi maggiori di 1 tali che MCD(m₁,m₂) = 1. Allora il sistema di congruenze lineari

ì í î x º b1(mod m1) x º b2(mod m2)

(4.11)

ammette soluzioni, che risultano a due a due congruenti modulo m₁m₂. Piú precisamente, se c é una soluzione del sistema, le sue soluzioni sono tutti e soli gli interi del tipo c+nm₁m₂, con n Î Z.

DIMOSTRAZIONE.   Gli interi m₁ e m₂, in forza del teorema 8 , sono invertibili rispettivamente in Z_m2 e Z_m1. Esistono, quindi, due interi c₁ e c₂ tali che c₁m₂ º 1 (mod m₁) e c₂m₁ º 1 (mod m₂). Allora, l'intero

c = b1c1m2+b2c2m1

é una soluzione del sistema (4.11), avendosi

c = b1c1m2+b2c2m1 º b1c1m2(mod m1) º b1(mod m1)

e

c = b1c1m2+b2c2m1 º b2c2m1(mod m2) º b2(mod m2)  .

Ora, se c é una fissata soluzione del sistema (4.11), si ha subito che sono soluzioni anche gli interi del tipo c+nm₁m₂, con n Î Z. Inoltre, se [`c] é un'ulteriore soluzione, si ha che [`c]-c é divisibile per m₁m₂, essendo m₁ e m₂ coprimi, e quindi [`c] = c+nm₁m₂, per un opportuno intero n. L'asserto é cosí completamente provato. ¨ Del precedente teorema si prova facilmente la seguente generalizzazione.

TEOREMA 5 Siano m₁,m₂,... ,m_t interi maggiori di 1 e a due a due coprimi. Allora il sistema di congruenze lineari

ì ï ï í ï ï î x º b1(mod m1) x º b2(mod m2) ¼ x º bt(mod mt)

(4.12)

ammette soluzioni, che risultano a due a due congruenti modulo m₁m₂¼m_t. Piú precisamente, se c é una soluzione del sistema, le sue soluzioni sono tutti e soli gli interi del tipo

c+nm1m2¼mt  ,  con  n Î Z.

4.4  Esercizi

1    Provare che il quadrato di ogni intero é congruente a 0 o ad 1 modulo 4.

2    Provare che, per ogni intero n, risulta n³ º n (mod 6.)

3    Provare che, per ogni intero dispari n, risulta n² º 1 (mod 8).

4    Provare che la relazione su Z definita da

m   Â  n       Û      m2 º n2 (mod 6)

é d'equivalenza.

5    Provare che valgono le seguenti relazioni, senza eseguire direttamente le moltiplicazioni in esse indicate.

21457337 ·191213 º 1 (mod 10)   ,    32578·23989 º 17 (mod 25) .

6    Stabilire se le seguenti equazioni ammettono soluzioni intere e, in caso positivo, determinare l'insieme delle soluzioni:

18x+105y = 5 , 504x+672y = 18 , 760x+135y = 5 , 1732x+864y = 48 .

7    Risolvere, se é possibile, le seguenti congruenze lineari:

9x º 6(mod 12) , 6x º 5(mod 4) , 12x º 15 (mod 39)  , 6x º 5(mod 7) , 24x º 21(mod 9) , 3x º 1 (mod 14)  .

8    Dire se i seguenti sistemi di congruenze lineari

ì í î x º 7 (mod 9) x º 3 (mod 5)  ,       ì í î x º 5 (mod 10) x º 7 (mod 11)

ammettono soluzioni e, in caso positivo, determinarle.

9    Provare che l'equazione x²+y² = 3 non ha soluzioni in Z₄.

10    Elencare gli elementi invertibili di Z₄, Z₅, Z₆, Z₇, Z₈.

11    Trovare gli inversi di 2 in Z₁₁, 7 in Z₁₅ e Z₁₆, 5 in Z₁₃.

12    Provare che, per ogni intero n > 2, esistono almeno due elementi invertibili in Z_n che verificano l'equazione x² = 1. Quanti ne esistono esattamente nel caso n sia primo?

13    Provare che in Z₈ esistono tre elementi invertibili che verificano l'equazione x² = 1.

14    Trovare un collegamento tra l'orologio e l'aritmetica modulo 12.

Note:

¹ Questo significa che le due operazioni non dipendono dai rappresentanti delle classi scelte ma soltanto da queste ultime.

File translated from T_EX by T_TH, version 2.51.
On 3 Mar 2002, 18:04.