Fidarsi è bene ma… l’artimetica modulare è meglio

In un «attacco d’arte matematica», proprio ieri ho scritto un po’ di getto l’articolo «Modulo sette – come si comportano le potenze di dieci» che, vi confesso, al momento è uno dei miei preferiti di tutto il blog (anche per il fatto che in quanto a lunghezza, è uno dei rari post a meritare di essere chiamato «articolo»).

Oggi, con questo nuovo post, mi accingo a rimediare a quell’orribile «fidatevi», buttato lì fra un’affermazione indimostrata e l’altra, che autogiustifico soltanto con la necessità di non finire infrattata in un frattale di pensieri divergenti, precisazioni necessarie e chi più ne ha più ne metta (e noi ben sappiamo che la mente fine ne può sempre trovare di nuovi: la catena non avrà mai soltanto un numero finito di passi).

Riprendo quindi le proprietà delle quattro operazioni aritmetiche rispetto al quoziente modulo un numero, e questa volta finisco quello che ho cominciato. Riprendo con l’addizione, mi perdonerete i copia-incolla e le ripetizioni dall’articolo di ieri.

L’aritmetica modulare: un’esperienza di tutti i giorni

C’è chi la chiama l’«aritmetica dell’orologio», ma è anche l’«aritmetica della settimana», quella dell’anno, quella del goniometro… a parte la retta euclidea, c’è qualche cosa che non sia ciclico, nell’universo?

Di che cosa si tratti, l’abbiamo definito ieri in questo articolo. Vediamo ora come si comporta l’aritmetica modulare rispetto alle quattro operazioni aritmetiche ordinarie.

Addizione

Abbiamo già visto nell’articolo pluricitato che il resto modulo n della somma a + b è dato dalla somma dei resti degli addendi a e b (salvo ulteriore passaggio al quoziente modulo n).

Sottrazione

Partiamo dalla teoria: chiamiamo a il minuendo e b il sottraendo della nostra operazione. Potremo scrivere:

a = c ⋅ n + r(a)

b = d ⋅ n + r(b)

ora, ammesso che possiamo operare la sottrazione a – b (e la risposta naturalmente varia, a seconda dell’ambiente numerico utilizzato), avremo:

a – b = c ⋅ n + r(a) – (d ⋅ n + r(b)) = c ⋅ n + r(a) – d ⋅ n  – r(b) = c ⋅ n  – d ⋅ n + r(a) – r(b) = 

= (c – d) ⋅ n + r(a) – r(b)

In definitiva, anche per quanto riguarda la sottrazione, il modulo della differenza è uguale alla differenza dei moduli.

Con qualche piccola complicazione, però.

Consideriamo ad esempio l’apparentemente banale sottrazione 18 – 6 e passiamo ai resti modulo 7.

Avremo r(18) = 4 e r(6) = 6. Che dire di r(18 – 6)?

Se operiamo la sottrazione prima di calcolare il resto modulo 7, otteniamo facilmente la risposta: r (12) = 5.

… quindi devo dedurne che, nell’aritmetica modulo sette, 4 – 6 = 5? Ebbene sì!

Proprio grazie alle proprietà dell’aritmetica modulare, dove ciò che conta sono i resti e non i multipli interi del modulo, ogni qual volta abbiamo una sottrazione «impossibile», ovvero con il sottraendo maggiore del minuendo, possiamo aumentare il minuendo di una quantità pari al modulo o a un multiplo del modulo sufficientemente grande da permetterci di contenere il sottraendo.

In questo caso è sufficiente aggiungere 7 al primo termine della sottrazione. Otteniamo

11 – 6 = 5

e questa volta il risultato ha ben poco di aleatorio!

Moltiplicazione

Come spesso ci dimentichiamo (perlomeno da quando ci hanno addomesticato al concetto di campo numerico, dove addizione e moltiplicazione sono due mondi paralleli), in realtà la moltiplicazione non è che una scrittura abbreviata dell’addizione, nel caso particolare in cui tutti gli addendi siano uguali fra di loro.

Quindi in definitiva la moltiplicazione non è che un caso particolare di addizione. Ci aspettiamo quindi che le stesse proprietà che valgono per l’addizione continuino a valere per questa nuova operazione. Verifichiamolo con tanto di dito nella piaga degli esempi numerici!

Partiamo da un esempio: voglio calcolare il resto modulo 7 (tanto per cambiare) del numero 27 che considero come prodotto 9 ⋅ 3.

Avrò

27 ≡ 6 (mod 7)

D’altra parte so che 9 ≡ 2 (mod 7) e 3 ≡ 3 (mod 7). Quindi la mia proprietà in questo caso è verificata: il resto del prodotto corrisponde al prodotto dei resti.

Vediamo cosa succede a livello strutturale:

Come sempre scrivo

a = c ⋅ n + r(a)

b = d ⋅ n + r(b)

Passiamo al prodotto. Ottengo

a ⋅ b = (c ⋅ n + r(a))(d ⋅ n + r(b)) = c ⋅ n ⋅ d ⋅ n + r(a)⋅ d ⋅ n + r(b)⋅ c ⋅ n + r(a)⋅ r(b) =

= (c ⋅ n ⋅ d + r(a)⋅ d + r(b)⋅ c) ⋅ n + r(a)⋅ r(b)

Abbiamo quindi verificato algebricamente che il resto del prodotto è uguale al prodotto dei resti.

Divisione

Anche nel caso della divisione potremmo appellarci alla sua stretta parentela con la sottrazione (basti pensare a quante sottrazioni successive comporti una divisione in colonna).

Vediamo comunque l’esempio della divisione intera con resto. Partiamo da un case study con numeri veri.

Butto lì due numeri a caso (utilizzando, tanto per non essere monotematica, il modulo 7):

1172 : 348 = 3 con resto 128 (provate con le sottrazioni successive!).

Passiamo alle classi di resto modulo 7. Avremo:

1172 ≡ 3 (mod 7)

348 ≡ 5 (mod 7)

128 ≡ 2 (mod 7)

Scrivendo la nostra divisione nella forma

1172 = 3 ⋅ 348 + 128

quello che possiamo verificare è che passando ai resti modulo 7 vale ancora l’espressione corrispondente:

3 ≡ 3 ⋅ 5 + 2 (il tutto modulo 7)

infatti 3 ⋅ 5 + 2 = 17 ha resto 3 nella divisione per 7.

In formule, vediamo perchè funziona tutto ciò.

Se stiamo dividendo a : b, potremo scrivere

a = k ⋅ b + R

e come di consueto avremo

a = c ⋅ n + r(a)

b = d ⋅ n + r(b)

ma anche

R = Z ⋅ n + r(R)   [il resto del resto, pittoresco!!]

Mettendo insieme tutti gli ingredienti e mescolando bene, otteniamo

c ⋅ n + r(a) = k ⋅ (d ⋅ n + r(b)) + Z ⋅ n + r(R)

e buttando via tutti i termini multipli di n, restiamo con la formula

r(a) = k ⋅ r(b) + r(R) 

Ecco quindi verificato che la relazione tra dividendo, divisore e resto rimane invariata passando ai moduli. Rettificando una versione precedente di questo stesso articolo, ci tengo a precisare che anche il fattore k in rosso nella formula, se pure abbia il suo significato di «invariante» nei passaggi fin qui illustrati, naturalmente può essere sostituito dal suo valore modulo n, se pure in un passaggio successivo, riapplicando i resti modulo n all’ultima uguaglianza scritta qui sopra.

Poichè r(a), r(b) e r(R) sono già resti modulo n, non subiranno più altre variazioni e otterremo quindi la semplificazione finale

r(a) = r(k) ⋅ r(b) + r(R) 

#equimifermo #aritmeticamodulare #moduloèbello

 

 

 

 

 

Annunci

3 commenti

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

w

Connessione a %s...