Aritmetica modulare: introduzione e qualche esempio

Aritmetica modulare, un ostacolo non sempre facile da superare ma molto interessante da affrontare. Era circa un mese che mi proponevo di scrivere un articolo sull’aritmetica modulare, ma essendo un argomento abbastanza ostico e non semplice da condividere, ho sempre rimandato.

aritmetica modulare

Per evitare di ripetermi anche questa settimana, ho deciso di iniziare dalle cose più semplici. Questo articolo sarà quindi un’introduzione con le principali proprietà, esempi e spiegazioni dei concetti base. Di sicuro mi sarà poi più facile approfondire l’argomento, la parte più difficile è iniziare dopotutto!

Iniziamo!

L’aritmetica modulare viene anche spesso detta aritmetica dell’orologio . Prova a pensare a come conti quando hai a che fare con l’orologio…non noti alcuna differenza con l’usuale metodo di contare?

Beh, effettivamente quando si parla di orari, si conta in aritmetica modulo 12 e 24. Infatti se fossero le 9 della sera e un tuo amico di dicesse “guarda che domani mattina partiamo presto, mettiti la sveglia tra 7 ore!”. A che ora la metteresti? Beh, semplice, alle 4 del mattino del giorno seguente.

Ci hai fatto caso però che 9+7 fa 16? Beh, inconsciamente stai contando in modulo 12.

Vediamo ora di mettere un po’ d’ordine, introducendo qualche formalismo in più.

Si tratta di un sistema di aritmetica degli interi, nel quale i numeri “si avvolgono su se stessi” ogni volta che raggiungono i multipli di un determinato numero n, detto modulo. L’aritmetica modulare e la notazione usuale delle congruenze vennero formalmente introdotte da Carl Friedrich Gauss nel suo trattato Disquisitiones Arithmeticae, pubblicato nel 1801.

Sostanzialmente, preso un m intero non nullo, si dice che A e B sono congruenti modulo m, se il resto delle divisioni di A, B per m è lo stesso. In formule, detta ‘%’ l’operazione indicante il resto della divisione, A%m=B%m.

Facciamo un esempio per riordinare le idee.

Diciamo m=5, in tal caso è semplice verificare che 10,20,25,165 sono congruenti in modulo 5, ma anche 6,166,76,81 sono tra essi congruenti. Infatti il primo gruppo, se diviso per 5, da resto 0. Mentre il secondo gruppo se diviso per 5, da resto 1. Sono quindi congruenti in modulo 5.

Non è difficile verificare che se congruente a in modulo m, allora a-b è multiplo di m.

Infatti diciamo a  = r*m + q1, b = s*m + q2. Allora abbiamo che

a-b = m * (r-s) + (q1-q2) . Ma a è congruente a b, quindi essendo a%m=q1=b%m=q2, concludiamo che a-b=m*(r-s), ossia a-b è multiplo di m! 🙂

Inoltre potrebbe esserti utile che la relazione di congruenza è una relazione di equivalenza, ossia gode della proprietà riflessiva, simmetrica e transitiva. Qui sotto ti descrivo in una riga ciascuna, le 3 proprietà. Se vuoi qualcosa di più, contattami o fai una ricerca su Google 🙂

  1. Riflessiva: a congruente ad a
  2. Simmetrica: se a congruente a b, allora b congruente ad a
  3. Transitiva: se a congruente a b e b congruente a c, allora a congruente a c

Bene, ora che sai le proprietà fondamentali di questa particolare aritmetica, è importante scoprire (o rinfrescare) come si comportano le operazioni che utilizziamo comunemente su questa tipologia di numeri.

Proviamo ad arrivarci con un esempio, scriverò solo al suo termine la definizione formale delle operazioni (niente di complicato, non preoccuparti).

Prendiamo m=5 per semplificarci i conti. Ora vediamo quanto fa 7 + 9 in modulo 5, sia svolgendolo direttamente, si operando sulle classi di resto (in aritmetica modulare, per classe di resto si intende la classe di equivalenza a cui il numero appartiene. Una classe di resto è fatta da tutti i numeri interi che restituiscono lo stesso resto se divisi per m, nel caso del modulo m ovviamente).

Banalmente, 7 + 9 = 16, che modulo 5 fa 1. Quindi seguendo questo primo procedimento risulta che 7 + 9 (mod 5) = 1 (mod 5).

Puoi anche facilmente notare come 7 (mod 5) = 2 e 9 (mod 5) = 4. E ‘fatalità’ la somma delle classi di resto alle quali i due addendi appartengono, è 6 ovvero 1 in modulo 5.

Sembrerebbe quindi che la classe di equivalenza della somma, sia la somma delle classi di equivalenza. Il che è vero ed è anche dimostrabile, chiaramente.

Vediamo ora se si può fare un discorso analogo anche con il prodotto. Penso che tu abbia già intuito che anche il prodotto si comporta bene con le classi di resto.

Prendiamo infatti lo stesso esempio di prima: m=5, a=7, b=9.

a*b = 63 = 3 (mod 5).

Mentre a = 7 = 2 (mod 5), b = 9 = 4 (mod 5). 4*2=8 = 3 (mod 5).

Quindi, come puoi vedere, anche qui la classe di resto del prodotto è il prodotto delle classi di resto.

Niente di complicato, come ti avevo preannunciato.

Se hai già delle buone basi su strutture algebriche, come i gruppi, penso ti possa interessare anche sapere che dato n numero intero non nullo, l’insieme (Z/nZ, +) e (Z/nZ\{0},*) sono dei gruppi, con elementi neutri 0 e 1 (mod n).

Nel campo dell’aritmetica modulare ci sono molti teoremi interessanti e risultati degni di nota, tuttavia ho deciso di lasciare questo un articolo di base. Non andrò quindi oltre nei dettagli, il prossimo articolo su questo argomento sarà invece un approfondimento.

L’articolo finisce qui, per dubbi, domande o suggerimenti lascia un commento qui sotto o contattami alla mail list@mathone.it 😉

 

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *