Blog divulgativo sulla matematica applicata

Biscotti, orologi e militari: l'artimetica modulare

Introduzione e i sette nani

Era probabilmente un giorno di ottobre quando uno dei miei professori universitari entrò in aula e disse: "C'era una volta Biancaneve che voleva preparare i biscotti per i sette nani. Però voleva prepararne un numero minimo tale che se li avesse divisi tra due nani, ne sarebbe rimasto uno, se l'avesse divisi tra 3 nani ne sarebbe rimasto uno ancora, se tra 4,5 o 6 la stessa cosa ma...se l'avesse divisi tra tutti e 7 i nani non ne sarebbe avanzato nessuno". Ovviamente questo problema generò molta ilarità e facce corrucciate, sia per la apparente idiozia della storiella che per la richiesta assurda. Era una delle prime lezioni del mio primo anno di matematica ed ero rimasto stupito.

cross-site-scripting

Dato che non ci interessa molto (per il momento almeno) non parleremo della sindrome ossessivo-compulsiva di Biancaneve, ma ci concentreremo sull'aspetto matematico della questione. Quello che il professore di cui prima ci sta chiedendo è di trovare un numero intero positivo, ovvero un numero nell'insieme 0,1,2,..., tale che se lo divido per 2 ottengo resto 1, se lo divido per 3 ottengo ancora resto 1, se lo divido per 4,5 o 6, ottengo sempre resto 1, ma..se lo divido per 7, il resto della divisione è 0.

Sembra solo una questione di conti e tutto sommato lo è, ma la matematica che sta dietro a questa simpatica (e un po' strampalata) storia è veramente affascinante ed è chiamata Aritmetica Modulare. La cosa veramente bella è che tutti (e dico davvero tutti) possono capirla e conoscerla...ma anzi! Vi dirò di più! Tutti già la conoscono!! E la risposta è nell'orologio!!!

L'orologio terrestre

Tutti sanno cos'è un orologio. E tutti hanno imparato, sin da piccoli, a contare le ore. Quindi è chiaro che se ora sono le 9 del mattino e ti dico di vederci tra due ore, tu capirai immediatamente che ci vedremo alle 11. Questo è giusto, e il motivo è che 9+2=11. Ma se ti dicessi che ci vediamoorologio1 tra 4 ore, tu capiresti che ci vedremo all'1 del pomeriggio. Eppure 9+4=13 non 1. Questo può sembrare sciocco ma in realtà racchiude tutto il concetto della artimetica modulare.

Quello che stiamo facendo in sostanza è ridurre il nostro insieme di numeri! Non stiamo eliminando numeri, stiamo solamente dicendo che alcuni numeri sono "uguali" tra loro. Nell'esempio fatto prima, 13 e 1 "coincidono" e per convincerci di ciò basta osservare le lancette dell'orologio! Quando sono le 13 la lancetta delle ore punterà all'1. Questa relazione che stiamo introducendo la chiameremo congruenza.

Facciamo altri esempi: sono le 4, a che ora punterà la lancetta tra 10 ore? La risposta è: alle 2. Se invece fossero le 8, tra 7 ore? La lancetta punterà alle 3. Ma se fossero le 5, tra 1000000 ore, dove punteranno le lancette???

Qui abbiamo un bel problema...questa domanda esce fuori dalla nostra intuizione. Come facciamo ora? Nessun problema!!! La matematica arriva in soccorso!!!

Se ci fate caso, negli esempi precedenti, abbiamo identificato la coppia 14 e 2 e la coppia 15 e 3. Se guardate attentamente, la divisione tra 14 e 12 dà resto 2 e la divisione tra 15 e 12 dà resto 3. Ed è questa la risposta, fare la divisione per 12 e guardare il resto! Infatti, se sull'orologio partite dalla posizione delle 12 (l'ora 0) e volete sapere dopo n ore dove si trova la vostra lancetta, vi basta dividere per 12 e guardare il resto, quella sarà la risposta!

Quindi, tornando all'esempio, se sono le 5, tra 1000000 ore, dove punta la lancetta?? Se dividiamo 1000005 per 12, otterremo come resto 9, infatti 1000005=9 + 12 * 83333. Quindi le lancette segneranno le 9.

Direte voi, "va bene ma quindi che ce famo?"

L'orologio di Biancaneve

Bene, adesso immaginate che esistano orologi con un numero di ore a piacere! Sia $n$ questo numero. In questo strano mondo con gli orologi a $n$ ore fare i conti è diverso ma la sostanza non cambia.

Se parto da quando l'orologio segna n (cioè l'ora 0), e voglio capire dopo $x$ ore dove punta la lancetta, so già cosa devo fare. Dovrò dividere per n e vedere il resto, tale e quale al caso di prima, in cui avevo n=12. Magnifico no?

Vediamo di scrivere le cose in matematichese e di dare qualche nome agli oggetti che abbiamo descritto. Due numeri a e b si dicono congrui modulo n se danno lo stesso resto quando li dividiamo per n. Indicheremo nel modo seguente: a \cong b \; (\text{mod} n)
Quindi, a livello intuitivo, due numeri sono congrui se partendo dall'ora 0 sull'orologio, la lancetta segnerà la stessa ora.

Questa matematica è utilissima in moltissimi casi. Nella matematica pura in primis può essere usata per capire meglio i famosi criteri di divisibilità che noi tutti abbiamo studiato alle medie ma che nessuno ci diceva mai perchè funzionavano! In più ha una famosa generalizzazione che va sotto il nome di "Teorema cinese dei resti". Inoltre in teoria dei numeri, può essere usata per trovare i numeri primi! In più ha notevoli applicazioni in crittografia; ad esempio il sistema crittografico più utilizzato al mondo (detto RSA) si basa proprio su questi concetti elementari!

Non parlero di questo ora di tutte queste cose ma lo farò sicuramente in futuro. Per ora concentriamoci su Biancaneve!

Militari cinesi

Ora che abbiamo questo nuovo formalismo possiamo riformulare il problema di Biancaneve. Lei vuole quindi un numero m tale che sia congruo a 1 modulo 2,3,4,5 e 6 e che sia congruo a 0 modulo 7. Più facile no? Ma per ora non abbiamo ancora risolto niente! Iniziamo il cammino che ci porterà a risolverlo..ma per farlo dobbiamo tornare indietro..molto molto indietro!

Moltissimo tempo fa, prima ma molto prima della nascita di Cristo, i cinesi prosperavano nella loro terra e, strano a credersi, già conoscevano l'artimetica modulare. La cosa interessante è che la usavano per contare! Ad esempio, prendiamo un gruppo di soldati. Non immaginate che siano una decina o una ventina, pensate ad un enorme campo pieno di militari. Quanti modi abbiamo per contarli? Ci conviene davvero andare lì in mezzo e contarli uno ad uno? Non c'è un modo più intelligente?? In effetti c'è!

Il procedimento "più intelligente" è questo: decido all'inizio un po' di numeri, diciamo $p$ numeri, che chiamo n_1, n_2, \cdots, n_p. Chiamo alle truppe di dividersi in gruppi di n_1 persone e chiedo ai rimanenti (il resto) di venire da me. Conto il resto, mettiamo a_1, e mi scrivo che il numero x dei soldati è congruo a a_1 modulo n_1. Faccio lo stesso per tutti gli altri numeri scelti, scrivendomi sempre il resto. Alla fine otterrò un sistema del tipo:  x \cong a_1 \; (\text{mod} n_1)
x \cong a_2 \; (\text{mod} n_2)
\cdots
x \cong a_p \; (\text{mod} n_p)

Essenzialmente è la stessa cosa che fa Biancaneve! Ora però, come fa questo ad aiutarci? Ci aiuta perchè, anzichè contare tutti i soldati, ci basta fare un po' di conti ed è fatta. Vediamo un esempio piccolo (del tipo una decina di soldati!): supponiamo che i numeri che abbiamo scelto siano 2 e 3 e supponiamo che il numeri x di soldati diviso 2 da resto 1 e diviso 3 da resto 2. Quindi x \cong 1 \; (\text{mod} 2)
x \cong 2 \; (\text{mod} 3)

Dalla prima delle due otteniamo che x = 2N + 1, dove N è un intero sconosciuto. Questo è vero perchè se divido x per 2 ho resto 1 e tutti i numeri con questa proprietà sono di questo tipo. Sostituiamo questa x nella seconda e abbiamo 2N+1 \cong 2 \; \text{mod} 3, ovvero 2N \cong 1. Ora moltiplichiamo entrambi i membri per 2 ed otteniamo 4N \cong 2, e sapendo che 4 è congruo a 1 modulo 3, abbiamo che N è congruo a 2 modulo 3. Quindi N = 3M + 2 per un certo M. Ora torniamo alla nostra x e sostituiamo N. Quello che otteniamo è x = 6M + 5. Sapendo che x è positivo, M è un intero maggiore o uguale a 0. Perciò x è un intero che appartiene all'insieme composto da 5, 11, 17, ... ovvero all'insieme dei numeri congrui a 5 modulo 6.

Ovviamente questa procedura non ci darà mai un numero preciso ma un insieme di numeri (che sono tutti congrui modulo un certo altro numero). Tuttavia, sapendo, almeno indicativamente, il numero delle cose che dobbiamo contare, possiamo ottenere un risultato preciso. Se per esempio vi avessi detto che il numero x del caso precedente è un numero compreso tra 23 e 30, voi avreste subito capito che il numero in questione è 25. Così infatti, presumo, facessero i cinesi. Loro avevano una stima del numero dei soldati e con questo metodo ne calcolavano il numero ESATTO.

In realtà l'ho resa più facile di quello che in verità è, nel senso che ho omesso alcuni dettagli che il lettore curioso può andare a cercare da solo. Per esempio cercando il Teorema cinese del resto, anche su Wikipedia!
Tornando comunque alla questione di Biancaneve, si trova che Biancaneve deve fare un numero di biscotti che sia congruo a 301 modulo 420. Sicchè vogliamo il numero più piccolo possibile e sicchè Biancaneve vorrebbe soddisfare le sue manie in modo meno costoso possibile, la risposta è 301. E se non ci credete...fate pure le divisioni!

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

2 commenti

  1. sara's Gravatar sara
    aprile 19, 2015    

    complimenti!!!

  2. aprile 22, 2015    

    Ah i tempi in cui eravamo giovani! Bella introduzione ;-)

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination