Università della Liberetà 2007-’08
alcune considerazioni
m.bassi
1
Generalmente ci serviamo dell’orologio o della sveglia molte volte al
giorno. I nostri orologi sono macchine per misurare il tempo e,
qualsiasi strumento di misura è di “natura” matematica.
Contando con i numeri che rappresentano le ore, spesso si ottengono
risultati insoliti: sono le 7 e aggiungiamo 8 ore …….
11
0
1
10
2
9
3
7+8=3
4
8
7
5
Si legge “7 più 8 uguale a 3 (modulo 12) “
6
Questo tipo di aritmetica si chiama aritmetica modulare
o anche sistema di numerazione finito
2
Un’ altro sistema numerico finito si può costruire con i giorni della
settimana: 0 domenica, 1 lunedì, 2 martedì,……, 6 sabato.
alcune domande:
1. Se il 4 marzo era di domenica, che giorno era il 24 marzo?
2. Per trovare che giorno sarà il 4 marzo dell’anno successivo si
potrebbe ragionare così…
3. Si può anche andare all’indietro e chiedersi: che giorno era il 4
marzo del 1907 ?
IL PROBLEMA SI PUÒ RISOLVERE CONTANDO O CON L’ARITMETICA
MODULO 7
Allo stesso modo si possono risolvere problemi del tipo: che ora sarà
tra 1675 ore?
Spiegazione parziale
Se numeriamo le 24 ore del giorno da 0 a 23 e se, ora sono le 18,tra
1675 ore saranno (1675+18) mod 24, cioè le 13
3
Consideriamo l’insieme dei numeri interi Z e la relazione
detta di congruenza modulo n (con n > 0), così definita:
Due numeri a e b sono equivalenti modulo n se e solo
se (a - b) è multiplo di n.
Esempio se n = 5 , 12 e 7 sono equivalenti mod.5 se e solo se
(12 – 7) è multiplo di 5
infatti
12 – 7 = 5 e 5 è multiplo di se stesso
Con la relazione di equivalenza si può costruire l’insieme
Zn delle classi di equivalenza, dette anche classi di resto
modulo n
NOTA a è multiplo di b se e solo se esiste un numero intero k tale
che a = b • k
4
esempio
classi di resto mod 5
[0]
[0] ={0, 5, 10, 15, 20, 25, 30 ……}
[1]
[1] ={1, 6, 11, 16, 21, 26, 31 ……..}
[2]
[2] ={2, 7, 12, 17, 22, 27, 32 ……..}
[3]
[4]
[3] ={3, 8, 13, 18, 23, 28, 33 ……..}
[4] ={4, 9, 14, 19, 24, 29, 34 …….}
OSS. E’ interessante verificare che le ordinarie
operazioni di addizione e moltiplicazione che sono
definite in Z danno luogo a operazioni analoghe in Zn
5
CLASSI di RESTO MODULO 5
Tavola dell’addizione
+
[0]
[1]
[2]
[3]
[4]
[0]
[0]
[1]
[2]
[3]
[4]
[1]
[1]
[2]
[3]
[4]
[0]
[2]
[2]
[3]
[4]
[0]
[1]
[3]
[3]
[4]
[0]
[1]
[2]
[4]
[4]
[0]
[1]
[2]
[3]
esercizio:
[2]+ [4]=[2+4]=
=[5+1]=[1]
la classe [2] rappresenta tutti gli elementi del tipo 2+5h, gli
elementi della classe [4] sono del tipo 4+5k,
la loro somma è 2+5h+4+5k = 2+4+5(h+k) = 6+5(h+k) = 1+5+5(h+k) =
= 1+5 (h+k+1): questo elemento appartiene alla classe [1].
6
CLASSI di RESTO MODULO 5
- L’operazione + è interna
- Vale la proprietà
associativa
Tavola dell’addizione
+
[0]
[1]
[2]
[3]
[4]
- Esiste l’elemento neutro
[0]
[0]
[1]
[2]
[3]
[4]
[0]
[1]
[1]
[2]
[3]
[4]
[0]
[2]
[2]
[3]
[4]
[0]
[1]
[3]
[3]
[4]
[0]
[1]
[2]
[4]
[4]
[0]
[1]
[2]
[3]
- Esiste , per ogni
elemento il simmetrico
(opposto)
- L’insieme Z5 è chiuso
rispetto alla somma
[a]+ [b] =[a+b]
Nota
[ a ] è simmetrico di [ b ] se e solo se [ a ] + [ b ] = [ b ] + [ a ] = [ 0 ]
7
CLASSI di RESTO MODULO 5
Tavola della moltiplicazione
- L’operazione ∙ è
interna
∙
[0]
[1]
[2]
[3]
[4]
- Vale la proprietà
associativa
[0]
[0]
[0]
[0]
[0]
[0]
-La classe [0] annulla
qualunque prodotto
[1]
[0]
[1]
[2]
[3]
[4]
[2]
[0]
[2]
[4]
[1]
[3]
[3]
[0]
[3]
[1]
[4]
[2]
[4]
[0]
[4]
[3]
[2]
[1]
- Esiste l’elemento
neutro [1]
- Esiste , per ogni
elemento, diverso da
[0] il simmetrico (o
1; 2
reciproco) 1
es. [ 2 ] • x = [ 3 ];
3; 4
4
x = [3] ∙ [2]simmetico ; x = [3] ∙ [3];
x = [4]
8
CLASSI di RESTO MODULO 6
Qui molte proprietà
non sono valide:
- Non è vero che ogni
elemento ha il simmetrico:
per i numeri 2, 3, 4 non
esistono
- Ci sono elementi diversi
da zero che moltiplicati
tra loro danno 0
Tavola della moltiplicazione
∙
[0] [1] [2] [3] [4] [5]
[0] [0] [0] [0] [0] [0] [0]
[1] [0] [1] [2] [3] [4] [5]
[2] [0] [2] [4] [0] [2] [4]
[3] [0] [3] [0] [3] [0] [3]
[4] [0] [4] [2] [0] [4] [2]
[5] [0] [5] [4] [3] [2] [1]
- In alcune righe compare
più volte uno stesso
elemento
N on vale la legge di annullamento del prodotto
9
Alcune EQUIVALENZE sono di notevole importanza
(a + b) mod n = a mod n + b mod n
ciò vuol dire che il
resto di una somma è uguale alla somma dei resti
(a • b) mod n = a mod n • b mod n
ciò vuol dire che il
resto di un prodotto è uguale al prodotto dei resti
Se a e b sono uguali,
(a • a) mod n = a mod n • a mod n = r • r = r2
con r resto della divisione di a per n
NOTA: questa proprietà è utilizzata fondamentalmente nell’ambito
della crittografia a chiave pubblica (RSA) con numeri primi. Infatti
questa proprietà permette di determinare i resti delle divisioni tra
numeri con un “ grande” numero di cifre
10
qualche esempio
• 12² mod 11 = 144 mod 11 = 1 = ( 12 mod 11 )²= 1•1 = 1
• 329 mod 7 = 1
infatti si ottiene:
32 mod 7 = 4 ;
322 mod 7 = ( 32 mod 7)2 = (4•4) mod 7 = 2
324 mod 7 = (322 mod 7)2 = (2•2) mod 7 = 4
328 mod 7 = (324 mod 7)2 = (4•4) mod 7 = 2
329 mod 7 = (328 •32) mod 7 = (2•4) mod 7 = 1
Il metodo è ricorsivo e facilmente implementabile
11
LA PROVA DEL NOVE
Supponiamo di aver moltiplicato due numeri a e b, e di
aver ottenuto come risultato c.
Rifacendo il calcolo, potremmo ottenere risultati uguali o
diversi:
se sono diversi siamo sicuri che almeno uno dei due è
errato,
se sono uguali non abbiamo la certezza che il risultato sia
corretto perché potremmo aver fatto lo stesso errore in
tutti due i calcoli.
Lo stesso avviene con la prova del nove: se i conti
“non tornano” siamo sicuri di aver sbagliato la prova
o la moltiplicazione, se “tornano”, avremo la
conferma dell’esattezza del risultato, ma mai la
sicurezza
12
LA PROVA DEL NOVE
La prova del nove è molto più veloce che non rifare la
moltiplicazione e quindi è preferibile
La prova del nove ( o dell’ 11, o ... ) si basa sul fatto che
se a ∙ b = c allora
a mod p ∙ b mod p = c mod p Es. 564 * 4318 = 2435352
a mod p
c mod p
a mod p ∙ b mod p
c mod p = 6
7
(6 7) mod 9 = 6
•
b mod p
6
13
Si potrebbe fare anche la prova del 2, ricordando che a mod 2 è
uguale a 1 se a è dispari e a 0 se a è pari
Se almeno uno dei due numeri da moltiplicare è pari il risultato deve
essere pari, se ambedue sono dispari il risultato deve essere dispari
Perché allora non si usa la prova del 2 ?
Ricordiamo che se la prova non torna il risultato è
sbagliato, ma se la prova torna, potrebbe funzionare per
caso.
E perché non si fa con 347? Ci sarebbero 347 casi possibili (0……346)
e l’eventualità che la prova torni per caso è piuttosto remota.
14
Se volessimo usare un altro numero al posto del 9, ad es. 7,
dovremmo conoscere il modo di trovare il resto mod 7
Il metodo di Pascal per il calcolo dei resti mod 7
(1650)
Il metodo proposto da Pascal utilizza le proprietà delle classi resto
il numero 5342 è divisibile per 7 ? Il numero 5342 può essere
scritto in forma polinomiale :
5 • 103 + 3 • 102 + 4 • 101 + 2 • 100
Pascal trascrive il polinomio in una tabella a due righe
5
103
3
4
2
102 101 100
5
3
4
2
6
2
3
1
resti mod 7 dei termini della
seconda riga
Moltiplichiamo 5•6+3•2+4•3+2•1 = 50; 50 mod 7 = 1 e anche
5342 diviso 7 dà resto 1 (principio di sostituzione)
15
Nel descrivere il metodo di Pascal abbiamo incontrato una
sequenza di numeri (…4 6 2 3 1), data dai successivi resti mod 7
delle potenze decrescenti di 10 ….la sequenza-resti diventa
periodica e può esser utilizzata ogni volta che occorre
In conclusione per vedere se un numero n è divisibile per 7
-si scrivono su una riga le cifre di n
-si scrivono le sequenze-resti mod 7 sulla seconda riga
-si moltiplicano i termini corrispondenti della prima e seconda riga
-si sommano i prodotti ottenuti e si calcola il resto mod 7
-se il resto mod 7 è zero, allora n è divisibile per 7
Il ragionamento di Pascal è applicabile a qualunque altro
criterio di divisibilità
16
PROBLEMI
1. Risolvi l’equazione 4x = 3 nell’insieme delle classi di resto modulo 6
2. Andrea, Bruno, Carlo, Dino e Enrico stanno facendo la conta e la
somma delle dita è 22. a chi tocca, se la conta comincia da Dino?
3. Sulla lavagna un alunno ha eseguito una moltiplicazione: Fa’ la prova
del nove e verifica se ci sono errori
324 x
47 =
2258
1306 •
15318
4. Durante un esercizio sull’aritmetica
delle classi resto, un alunno ha
calcolato 5 + 4 = 2. In quale modulo è
stata fatta l’addizione?
5. Quanto fa 8 : 4 nell’insieme delle
classi resto modulo 12?
17
6.Il gioco dei fiammiferi
Il gioco consiste nel disporre su un tavolo un numero
a piacere di fiammiferi. Dopo aver sorteggiato chi
deve fare la prima mossa, si dà inizio al gioco, che
consiste nel prelevare a turo dal tavolo un numero di
fiammiferi compreso tra uno e tre. Vince chi riesce a
costringere l’avversario a prendere l’ultimo
fiammifero. Esiste una strategia vincente per chi fa
la prima mossa?
e… per finire
La prova del 9 è abbastanza facile, ma anche la prova dell’ 11 può
essere applicata senza troppi problemi
Basta osservare che: 10 = - 1 mod 11; 100 = 10 ∙ 10 = 1 mod 11
via
e così
PROVA
18
Risoluzione dei P R O B L E M I
1. Risolvi l’equazione 4x = 3 nell’insieme delle classi di resto modulo 6
4•x=3
x = 3 • 4simmetrico
se scorriamo la tavola moltiplicativa mod.6 ,
non riusciamo a trovare il simmetrico o inverso di 4 pertanto
l’equazione non ha soluzione (equazione impossibile in Z6)
2. Andrea, Bruno, Carlo, Dino e Enrico stanno facendo la conta e la
somma delle dita è 22. a chi tocca, se la conta comincia da Dino?
Dato che i ragazzi sono cinque, calcoliamo il resto
22 mod 5 = 2 . Il secondo ragazzo dopo Dino è Andrea
19
3. Sulla lavagna un alunno ha eseguito una moltiplicazione: Fa’ la
prova del nove e verifica se ci sono errori
324 x
2258
1306 •
15318
324 mod 9 = 0
47 mod 9 = 2
0•2=0
anche 15318 mod 9 = 0
0
2
0
0
47 =
La prova del nove dà esito positivo, ma la moltiplicazione è
ugualmente errata. Infatti 324 • 47 = 15228
Nota non sempre la prova del nove riesce a trovare errori
20
4. Durante un esercizio sull’aritmetica delle classi resto, un
alunno ha calcolato 5 + 4 = 2. In quale modulo è stata fatta
l’addizione?
Dato che 5 + 4 = 9 nell’ aritmetica decimale, il risultato 2 si può
ottenere solo togliendo 7.
5+4=2+7
5 + 4 = 2 (mod 7)
l’alunno sta usando le classi di resto modulo 7
5. Quanto fa 8 : 4 nell’insieme delle classi resto modulo 12?
La riga del 4 nella tabella moltiplicativa delle classi resto mod. 12 è :
0 4 8 0 4 8 0 4 8 0 4 8
L’8 compare ben 4 volte, in corrispondenza delle colonne 2, 5, 8 e 11,
che rappresentano risposte valide ala domanda posta
In altro modo: trova un numero x tale che 4 •x = 8
soluzioni: 2, 5, 8, 11
21
Nell’equazione di ‘primo grado’ considerata, abbiamo trovato
soluzioni diverse (2, 5, 8, 11) ;
se gli elementi - classi di resti mod. 12 - ammettono il simmetrico
rispetto la moltiplicazione, allora l’equazione ha un’ unica soluzione
;
5 • x = 8;
x=8•5
7 • x = 10;
x = 10 • 7 simmetrico ;
x = 10 • 7;
x = 10 (mod.12)
11 • x = 3;
x = 3 • 11 simmetrico ;
x = 3 • 11;
x = 9 (mod.12)
6•x=8
non ha soluzioni nell’insieme classi di resto mod.12
simmetrico
x=8•5;
x = 4 (mod.12)
In generale
Sia k è un intero primo con n. Comunque si assegni un
intero h, l’equazione in x
K • x = h (mod.12)
ammette soluzioni e queste costituiscono un classe mod. n
22
6.
Il gioco dei fiammiferi
Si calcola il resto mod. 4 del numero dei fiammiferi (è come se ci
fossero sul tavolo solo gli r fiammiferi del resto. Alla prima mossa,
basta togliere da r tanti fiammiferi, in modo da lasciarne uno solo
all’avversario.
Da questo momento, qualunque numero di fiammiferi prenderà B, A ne
prenderà quanti mancano per arrivare a 4 (se B ne prende 1, A ne
prenderà 3; se B ne prende 2 A ne prenderà 2, … .
Essendo 4 un elemento neutro (nelle classi resto mod.4), la situazione
non cambia: sul tavolo ci sarà sempre virtualmente sempre un solo
fiammifero (quello che rimarrà a B)
Nel caso che il resto mod. 4 del numero iniziale di fiammiferi sia 1, A
sarebbe destinato a perdere, ma A può ancora sperare che B non
conosca le regole e quindi prima o poi commetta un errore lasciando
sul tavolo un numero di fiammiferi (n mod 4) ≠ 1
La stessa situazione si ha se A gioca per secondo
Nota A fa la prima mossa, B è l’avversario
23
Le classi resto dal punto di vista
dell’algebra moderna
Prendiamo l’insieme delle classi resto modulo k (numero primo),
dotato di due operazioni +, • ;
osserviamo che :
L’addizione è un’operazione
interna
La moltiplicazione è
un’operazione interna
È associativa
È associativa
Esiste l’elemento neutro [0]
Esiste l’elemento neutro [1]
0gni elemento ha il suo
elemento inverso (o
simmetrico)
Ogni elemento, tranne 0, ha
il suo elemento inverso (o
simmetrico)
L’insieme è un GRUPPO
L’insieme è un MONOIDE
commutativo
e inoltre …
24
… la moltiplicazione è distributiva rispetto l’addizione cioè:
x • (y + z) = x • y + x • z
La presenza di tutte queste proprietà conferisce
all’insieme la struttura di ANELLO
Diversa è la situazione se k non è primo
Osserviamo che non vale più la legge di annullamento del prodotto,
per la quale un prodotto è nullo se lo è almeno uno dei due termini. Ci
sono cioè divisori dello zero
es. nelle classi resto mod. 6,
[2] • [3] = [0] oppure [0] : [2] = [3] ;
una semplice equazione di primo grado …
[4] • x = [2] ha due soluzioni: [2] e [5]
[3] • x = [5] non ha soluzioni
IMPORTANTE
L’insieme Zk(+,•) con k, numero primo, ha la
stessa struttura algebrica di Q (+,•)
25
N = {0, 1,2,3,4,5, ... }
insieme dei numeri naturali
Z = {0, +1, -1, +2, -2, +3 ... }
insieme dei numeri interi relativi
Q = {classi di frazioni equivalenti} insieme dei numeri razionali
I : numeri decimali non
periodici (numeri che non
possono essere
scritti come frazioni)
I
N
R=Q+I
R : l’insieme dei
Z
Q
reali si divide in
due sottinsiemi
disgiunti, quello
dei razionali Q
e quello degli
irrazionali I
26
CLASSI di RESTO MODULO 5
+
[0]
[1]
[2]
[3]
[4]
[0]
[0]
[1]
[2]
[3]
[4]
Tavola della
[1]
[1]
[2]
[3]
[4]
[0]
addizione
[2]
[2]
[3]
[4]
[0]
[1]
[3]
[3]
[4]
[0]
[1]
[2]
[4]
[4]
[0]
[1]
[2]
[3]
27
CLASSI di RESTO MODULO 5
∙
[0]
[1]
[2]
[3]
[4]
[0]
[0]
[0]
[0]
[0]
[0]
[1]
[0]
[1]
[2]
[3]
[4]
[2]
[0]
[2]
[4]
[1]
[3]
[3]
[0]
[3]
[1]
[4]
[2]
[4]
[0]
[4]
[3]
[2]
[1]
Tavola della
moltiplicazione
28
CLASSI di RESTO MODULO 6
+
[0] [1] [2] [3] [4] [5]
[0]
[0]
[1]
[2
[3]
[4]
[5]
[1]
[1]
[2]
[3]
[4]
[5]
[6]
[2]
[2]
[3]
[4]
[5]
[0]
[1]
[3]
[3]
[4]
[5]
[0]
[1]
[2]
[4]
[4]
[5]
[0]
[1]
[2]
[3]
[5]
[5]
[0]
[1]
[2]
[3]
[4]
Tavola della
addizione
29
CLASSI di RESTO MODULO 6
∙
[0] [1] [2] [3] [4] [5]
[0]
[0]
[0]
[0]
[0]
[0]
[0]
[1]
[0]
[1]
[2]
[3]
[4]
[5]
[2]
[0]
[2]
[4]
[0]
[2]
[4]
[3]
[0]
[3]
[0]
[3]
[0]
[3]
[4]
[0]
[4]
[2]
[0]
[4]
[2]
[5]
[0]
[5]
[4]
[3]
[2]
[1]
Tavola della
moltiplicazione
30
CLASSI di RESTO MODULO 12
+
0
1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
3
4
5
6
7
8
9
10
11
1
1
2
3
4
5
6
7
8
9
10
11
0
2
2
3
4
5
6
7
8
9
10
11
0
1
3
3
4
5
6
7
8
9
10
11
0
1
2
4
4
5
6
7
8
9
10
11
0
1
2
3
5
5
6
7
8
9
10
11
0
1
2
3
4
6
6
7
8
9
10
11
0
1
2
3
4
5
7
7
8
9
10
11
0
1
2
3
4
5
6
8
8
9
10
11
0
1
2
3
4
5
6
7
9
9
10
11
0
1
2
3
4
5
6
7
8
10
10
11
0
1
2
3
4
5
6
7
8
9
11
11
0
1
2
3
4
5
6
7
8
9
10
Tavola della addizione
31
CLASSI di RESTO MODULO 12
•
0
1
2
3
4
5
6
7
8
9
10
11
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
8
9
10
11
2
0
2
4
6
8
10
0
2
4
6
8
10
3
0
3
6
9
0
3
6
11
0
3
6
9
4
0
4
8
0
4
8
0
4
8
0
4
8
5
0
5
10
3
8
1
6
11
4
9
2
7
6
0
6
0
6
0
6
0
6
0
6
0
6
7
0
7
2
9
4
11
6
1
8
3
11
5
8
0
8
4
0
8
4
0
8
4
0
8
4
9
0
9
6
3
0
9
6
3
0
9
6
3
10
0
10
8
6
4
2
0
10
8
6
4
2
11
0
11
10
9
8
7
6
5
4
3
2
1
Tavola della moltiplicazione
32
tratte liberamente da…..
Maraschini – Palma
multi FORMAT
moduli per la formazione matematica nella Scuola Superiore
e altro … … …
33