Aritmetica modulare - Giulia`s math class

ARITMETICA MODULARE
• Scegliamo un numero m che chiameremo MODULO
• Identifichiamo ogni altro numero con il suo resto nella divisione
per m
• Tutti i numeri col medesimo resto si trovano insieme nella classe di
resto che è etichettata con un numero compreso tra 0 (zero) e m − 1
(il precedente di m)
ESEMPIO Usiamo il modulo m = 12 (come nell’orologio analogico).
Le classi di resto sono 12:
la classe 0 (tutti i multipli di 12, per esempio 12,36,60),
la classe 1 (1 + un multiplo di 12, per esempio 13,25,73),
la classe 2 (2 + un multiplo di 12, per esempio 15,26,50)
...
...
la classe 11 (11 + un multiplo di 12, per esempio 11,35,59,143).
Infatti 35 = 12 · 2 + 11 come 59 = 12 · 4 + 11
Per scrivere che 35 è nella classe di resto 11 nell’aritmetica modulo 12
scriviamo cosı̀:
35 ≡ 11 (12)
e leggiamo cosı̀:
35 è congruo a 11 modulo 12
oppure leggiamo cosı̀:
35 è nella classe di resto 11 modulo 12
ESERCIZIO Trova le classi di resto di 72, 45, 38, 37, 21, 9, 64 modulo 12.
• Le operazioni di addizione e moltiplicazione si possono svolgere direttamente con le classi di resto degli addendi (o dei fattori).
ESEMPIO Usiamo ancora il modulo m = 12.
Quanto fa 49 + 27 modulo 12?
So che 49 ≡ 1 (12) e che 27 ≡ 3 (12) allora 49 + 27 ≡ 1 + 3 ≡ 4 (12)
Infatti 49 + 27 = 76 = 12 · 6 + 4
Quanto fa 35 · 14 modulo 12?
So che 35 ≡ 11 (12) e che 14 ≡ 2 (12)
allora 35 · 14 ≡ 11 · 2 ≡ 22 ≡ 10 (12)
Infatti 35 · 14 = 490 = 12 · 40 + 10.
UN ALTRO ESEMPIO
Quanto fa 34 · 18 modulo 12? Completa tu!
So che 34 ≡ . . .
(12) e che 18 ≡ . . .
(12)
allora 34 · 18 ≡ . . . . . . . . . . . . . . . . . . . . . . . . . . . (12)
Quanto vale il prodotto? Ti sembra strano o normale?
Discutiamone insieme.
In questa aritmetica modulo 12, abbiamo trovato due numeri (nessuno dei
quali è zero - o classe di resto zero) il cui prodotto è zero.
Questo accade anche nell’aritmetica standard a cui siamo abituati?
Perché è possibile che accada nell’aritmetica modulo 12?
Accade solo con questa coppia di numeri?
Ne possiamo trovare altri?
Come sono legati al valore del modulo (nel nostro caso a 12)?
Prima di trarre delle conclusioni, analizziamo qualche altra aritmetica modulare, con altri valori per il modulo.
Costruiamo le tabelle della moltiplicazione per i moduli m = 2, m = 5,
m = 6.
m=6
m=5
× 0 1 2 3 4 5
× 0 1 2 3 4
m=2
0 0 0 0 0 0 0
0 0 0 0 0 0
× 0 1
1 0 1 2 3 4 5
1 0 1 2 3 4
0 0 0
2 0 2 4 0 2 4
2 0 2 4 1 3
1 0 1
3 0 3 0 4 0 3
3 0 3 1 4 2
4 0 4 2 0 4 2
4 0 4 3 2 1
5 0 5 4 3 2 1
In ogni tabella ci sono una riga (e una colonna) con soltanto cifre 0 perché
sono il prodotto per 0 (e il prodotto è commutativo come nell’aritmetica
standard).
Ma ci sono anche prodotti che valgono zero (si dice che sono prodotti nulli )
quando nessuno dei fattori è zero: ora indaga sui motivi per cui questo
accade...
Per riflettere su questi argomenti devi aver presente i concetti di numeri
primi, numeri composti, numeri primi tra loro.
Completa le osservazioni che seguono.
Nella tabella della moltiplicazione modulo 5 trovi una coppia di numeri non
nulli il cui prodotto sia zero?
Noti qualche altro dettaglio nei risultati delle moltiplicazioni, in ogni riga?
Nella tabella della moltiplicazione modulo 6 trovi almeno una coppia di
numeri non nulli il cui prodotto sia zero?
Scrivi qui tutte le coppie di fattori:
Perché pensi che ciò accada? Cosa hanno in comune i fattori con il modulo?
Riesci a immaginare quali coppie potrebbero avere la stessa proprietà
per esempio nell’aritmetica modulo 20?
E nell’aritmetica modulo 7?
Osserviamo ancora la tabella modulo 6:
5 · 2 ≡ 5 · 8 (6) ed è vero che 2 ≡ 8 (6)
3 · 2 ≡ 3 · 4 (6) ma non è vero che 2 ≡ 4 (6)
Da cosa potrebbe dipendere?
CRITERI DI DIVISIBILITÀ
Utilizzeremo l’artimetica modulare per ricavare alcuni criteri di divisibilità,
cioè dei metodi che consentano di verificare rapidamente se un numero n è
divisibile per un certo numero d.
Ci serviamo del nostro sistema di numerazione che è decimale e posizionale:
ogni numero è infatti scritto a partire da potenze di 10 e una cifra cambia
valore a seconda della posizione in cui è scritta.
Cosı̀ 678 = 6 × 102 + 7 × 101 + 8 × 100 cioè
678 = 6 · 102 + 7 · 10 + 8
• Quando posso dire che un numero è divisibile per 10?...se la sua
classe di resto è 0.
Facciamoci aiutare dalla notazione posizionale dei nostri numeri:
678 = 6 · 102 + 7 · 10 + 8 ≡ 8 (10)
quindi...
Un numero è divisibile per 10 se e solo se la sua cifra delle unità
lo è.
• Quando posso dire che un numero è divisibile per 2?
Usiamo lo stesso stratagemma:
678 = 6 · 102 + 7 · 10 + 8 ≡ 8 ≡ 0 (2): 678 è divisibile per 2
9635 = 9·103+6·102+3·10+5 ≡ 5 ≡ 1 (2): 9635 non è divisibile per 2
perché 10 è multiplo di 2 e lo stesso vale per tutte le sue potenze,
quindi modulo 2 tutte le cifre che non sono unità sono nulle e la classe
di resto del numero è la classe della sua cifra delle unità. Un numero
è divisibile per 2 se e solo se la sua cifra delle unità lo è, cioè se
essa è pari.
• Puoi provare da solo a trovare il criterio di divisibilità per 5?
• Quando posso dire che un numero è divisibile per 9?
Partiamo con una osservazione:
9 ≡ 0 (9) quindi 10 ≡ 1 (9)
99 = 9 · 11 ≡ 0 (9) quindi 102 = 100 ≡ 1 (9)
999 = 9 · 111 ≡ 0 (9) quindi 103 = 1000 ≡ 1 (9)
9999 = 9 · 1111 ≡ 0 (9) quindi 104 = 1000 ≡ 1 (9)
etc
Adesso proviamo a calcolare la classe di resto di 4716 modulo 9:
4716 = 4 · 103 + 7 · 102 + 1 · 10 + 6 ≡
≡4·1+7·1+1·1+5≡
≡ 4 + 7 + 1 + 6 ≡ 18 ≡ 0 (9)
Un numero è divisibile per 9 se e solo se la somma delle sue cifre è
divisibile per 9.
Prova con 65685 e 747.