sei sul sito di Giovanni Fraterno

1) Aritmetica modulare: equivalenza sulla somma, sul prodotto e sul quadrato
L'aritmetica modulare studia gli usuali resti delle divisioni aritmetiche. Diremo così che: è Q il quoziente della divisione fra il dividendo X e il divisore m, mentre è R il resto. Siccome nell'aritmetica modulare il quoziente è irrilevante, in luogo della usuale notazione inpiegata per la divisione, si preferisce questa notazione: X(mod m)=R, e si dice: "X modulo m è uguale a R".

Vediamo qualche esempio:
- 10(mod 4)=2
- 21(mod 45)=21
- 74(mod 7)=4
- 57(mod 57)=0
- 37(mod 36)=1 .

Con riferimento alla notazione: X(mod m)=R, valgono le seguenti proprietà:

- è sempre R < m

- tutti i possibili resti sono una quantità pari ad m e con valori compresi fra 0 ed m-1

- se X < m allora X(mod m)=X

- X(mod X)=0 ovvero m(mod m)=0

- X(mod (X-1))=1 ovvero (m+1)(mod m)=1

- X(mod 1)=0

- 0(mod m)=0.

Di notevole interesse sono le seguenti equivalenze:

- (X+Y)(mod m)=X(mod m)+Y(mod m), e cioè: il resto di una somma è pari alla somma dei resti

- (X Y)(mod m)=X(mod m) Y(mod m), e cioè: il resto di un prodotto è pari al prodotto dei resti.

Essendo resti, se uno dei due membri di un'equivalenza è maggiore o uguale a m, vuol dire che non è un resto, per cui occorre ancora dividerlo per m.

Vediamo qualche esempio:

- 17(mod 5)=2=(10+7)(mod 5)=10(mod 5)+7(mod 5)=0+2=2

- 17(mod 5)=2=(9+8)(mod 5)=9(mod 5)+8(mod 5)=4+3=7=
7(mod 5)=2

- 24(mod 5)=4=(6*4)(mod 5)=6(mod 5) 4(mod 5)=1*4=4

- 24(mod 5)=4=(8*3)(mod 5)=8(mod 5) 3(mod 5)=3*3=9=
9(mod 5)=4 .

L'equivalenza sul prodotto, conduce alla notevole equivalenza sul quadrato: il resto di un quadrato è pari al quadrato del resto. E' infatti:

Questa proprietà sul resto di un quadrato, è di importanza fondamentale nell'ambito della crittografia a chiave pubblica con numeri primi. Come vedremo sarà grazie ad essa che sarà possibile determinare resti di divisioni fra numeri con un incalcolabile numero di cifre.

Vediamo qualche esempio:
-
-



utenti in questo momento connessi alla rete di siti web di Giovanni Fraterno: