Aritmetica modulare

Veronica Gavagna

Aritmetica modulare o Aritmetica dell’orologio

Da http://proooof.blogspot.it/2010/04/alice-bob-e-eva-lorologio.html

Alice, Bob e Eva — L'orologio “Che ore saranno tra 314 ore?”. “Eh? Boh, devo fare il conto, non so”. “Fai il conto, allora”. “Uhm, 314 ore, ci sono 24 ore in un giorno, 314 diviso 24 fa 13.08(3)”. “E quindi?”. “E quindi 314 ore sono un po' più di 13 giorni”. “Vabbé, ma se vuoi sapere che ore saranno con precisione?”. “Uhm, allora, rimane un resto di zero virgola zero otto tre periodico…”. “Che non è propriamente un resto”. “Eh?”. “Eh, no. Non è il resto della divisione che hai fatto. Hai presente la regola per la divisione che hai imparato alle elementari?”. “Uh, quella! Da quanto tempo non ne faccio una. Eccola qua:”. •

Oh, bene. Quindi vedi che 314 diviso 24 ti dà come quoziente 13 e come resto 2. Quello che ti interessa, ai fini della risposta alla mia domanda, è proprio il resto”. “Ah, ho capito: 314 ore corrispondono a 13 giorni e 2 ore, quindi per sapere che ore saranno devo guardare l'orologio adesso e aggiungere 2 ore. Facile”. “Benissimo. Il calcolo che hai fatto potrebbe essere scritto anche in questo modo: 314 = 13·24 + 2”. “Vero”. “I Veri Matematici lo scrivono anche così: 314 ≡ 2 mod 24”. “Eh?”. “Significa che 314 e 2 danno lo stesso resto nella divisione per 24; il resto è naturalmente 2, che è minore di 24. Si legge in questo modo: 314 è congruente (o congruo) a 2 modulo 24”. “Manca però il 13, il quoziente della divisione”.

“Quello non ci interessa molto. Quando siamo interessati di più ai resti che ai quozienti, utilizziamo questo tipo di scrittura. Ed entriamo nel cosiddetto campo dell'aritmetica modulare”. “Che non è altro che un modo pomposo per definire l'aritmetica dell'orologio, a quanto vedo”. “Bè, sì, l'aritmetica dell'orologio è l'aritmetica modulo 24, ma naturalmente possiamo scegliere qualunque numero come base per i nostri moduli”. “E questo è interessante?”. “Certo”. “Voglio dire, serve a qualcosa?”. “Stranamente, sì. Non che ai Veri Matematici questo fatto interessi molto, però l'aritmetica modulare ha una effettiva applicazione pratica. Praticamente quotidiana”.

Esempi di aritmetica modulare

Che giorno della settimana sarà tra 31 giorni?

Aritmetica modulo 7

Che giorno dell’anno sarà tra 750 giorni?

Aritmetica modulo 365 (più o meno)

Con l’aritmetica modulare possiamo anche

spiegare i criteri di divisibilità e capire

come funziona (quando funziona…) la

«prova del 9»

Un esempio di aritmetica modulo 4 orologio con 4 ore

E’ verificata la

Proprietà commutativa?

Esiste un elemento

neutro rispetto all’

addizione?Esistono gli?

inversi di 1, 2, 3,

rispetto all’addizione?

Le congruenze Gauss, Disquisitiones arithmeticae (1801)

Def.1 Due interi a e b si dicono congruenti modulo m quando la loro differenza è divisibile per m

𝒂 ≡ 𝒃 mod m

314 ≡ 2 mod 4 perché 314-2=312 è divisibile per 4

31 ≡ 3 mod 7 perché 31-3=28 è divisibile per 7

750 ≡ 20 mod 365 perché 750-20=730 è divisibile per 365

26 ≡ 16 mod 5 perché 10 è divisibile per 5

16 ≡ -9 mod 5 perché 16-(-9)=25 è divisibile per 5

3 ≢ 11 mod 7 perché 3-11=-8 non è divisibile per 7

Una definizione alternativa

Due interi a e b si dicono congruenti

modulo m quando, divisi per m, hanno lo

stesso resto.

Infatti, se

a= mq1+r

b= mq2+r

Posso scrivere a-b=mq1+r –mq2-r= m(q1-q2)

cioè a-b è divisibile per m.

Esempi

Stabilire se sono congruenze:

12 ≡ 24 mod 12

12 ≡ 39 mod 9

- 7 ≡ 15 mod 11

- 7 ≡ 15 mod 3

- 7 ≡ 15 mod 2

15 ≡ 7 mod ?

15 ≡ 0 mod ?

SI

SI

SI

NO

SI

Divisibilità e congruenza

Osserviamo che

15≡0 mod 3 e anche 15≡0 mod 5

35 ≡ 0 mod 7; 6 ≡ 0 mod 2

Possiamo concludere che a è divisibile per m se e solo se a ≡0 mod m (Proprietà P0)

Possiamo allora scrivere che, se n è un numero pari, allora n ≡ 0 mod 2?

Sì, tutti i numeri pari sono divisibili per 2, cioè sono congrui a zero modulo 2.

Proprietà della congruenza modulo m

• E’ una relazione riflessiva?

a ≡ a mod m

• E’ una relazione simmetrica?

se a ≡b mod m allora b ≡a mod m

• E’ una relazione transitiva?

se a ≡b mod m e b ≡c mod m allora a ≡ c mod m

La congruenza è una relazione di equivalenza

Operazioni con le congruenze (tutte senza dimostrazione)

(P1) Congruenze secondo lo stesso modulo possono essere sommate o sottratte membro a membro.

Se a ≡ b mod m e c ≡ d mod m allora

a+c ≡ b+d mod m

a-c ≡ b-d mod m

5 ≡ 32 mod 9 e 11 ≡ -7 mod 9 diventano

16 ≡ 25 mod 9

-6 ≡ 39 mod 9 Il teorema vale per un numero qualsiasi di congruenze.

Operazioni con le congruenze

(P2) Una congruenza può essere moltiplicata per un intero qualsiasi. Se

a ≡ b mod m

è anche vero che, per ogni numero intero k,

ka ≡ kb mod m

Es. 3 ≡ 7 mod 4

Se moltiplico entrambi i membri per 5 ottengo

15 ≡ 35 mod 4; se moltiplico per -3 ottengo

- 9 ≡ -21 mod 4.

Operazioni con le conguenze

(P3) Due congruenze secondo lo stesso modulo, possono essere moltiplicate ordinatamente.

a ≡ b mod m

c ≡ d mod m

Allora

a x c ≡ b x d mod m

3 ≡ 14 mod 11

9 ≡ -2 mod 11

27 ≡ -28 mod 11

Una conseguenza Se ho n congruenze del tipo

a ≡ b mod m

a ≡ b mod m

……. n volte

a ≡ b mod m

(P5) Moltiplicando ordinatamente i primi membri e i secondi membri ottengo

𝒂𝒏 ≡ 𝒃𝒏 𝒎𝒐𝒅 𝒎

Da 3 ≡ 5 mod 2 segue ad esempio che

33 ≡ 53 mod 2, cioè 27 ≡ 125 mod 2

Criteri di divisibilità

Sia N un numero rappresentato in base dieci dalle cifre

𝑎𝑛𝑎𝑛−1𝑎𝑛−2 … 𝑎2𝑎1𝑎0

dove ogni cifra 𝑎𝑘 che compare, varia tra 0 e 9 (es. N=34601)

Se scrivo il numero in notazione polinomiale, ho 𝑁 = 𝑎𝑛10𝑛 + 𝑎𝑛−110𝑛−1 + … + 𝑎110 + 𝑎0

34601 = 3 × 104 + 4 × 103 + 6 × 102 + 0 × 10 + 1 × 100

Per sapere se il numero N è divisibile per 2, per 3, per 4, per 5 … mi basta sapere se è rispettivamente

congruo a zero mod 2, mod 3, mod 4, mod 5… (per la proprietà P0).

Studiare la divisibilità di un numero significa studiare la congruenza secondo un dato modulo: per far questo si usano le proprietà P0-P4 descritte in precedenza.

Divisibilità per 5

Osserviamo prima che

10 ≡ 0 mod 5

dunque

10𝑛 ≡ 0 mod 5 (P5) e anche 𝑎𝑛10𝑛 ≡ 0 mod 5 (P2)

10𝑛−1 ≡ 0 mod 5 (P5) e anche 𝑎𝑛−110𝑛−1 ≡ 0 mod 5 (P2)

...

101 ≡ 0 mod 5 (P5) e anche 𝑎1101 ≡ 0 mod 5 (P2)

100 ≢ 0 mod 5 NOTA BENE!!!

Divisibilità per 5

Studiamo allora la congruenza mod 5 del numero

𝑁 = 𝑎𝑛10𝑛 + 𝑎𝑛−110𝑛−1 + … + 𝑎110 + 𝑎0

Abbiamo visto che tutti gli addendi, tranne l’ultimo, sono congrui a zero modulo 5 (perché sono multipli di dieci o di potenze di dieci) quindi, per la P1, possiamo dire che N è divisibile per 5 (cioè congruo a zero modulo 5) se e solo se

𝑎𝑛10𝑛 + 𝑎𝑛−110𝑛−1 + … + 𝑎110 + 𝑎0 ≡ 0 mod 5

Cioè se e solo se

𝑎0 ≡ 0 mod 5

E quali cifre sono congrue a zero modulo 5, ovvero quali cifre sono divisibili per 5???

Solo il 5 e lo 0!!!

Possiamo allora esprimere il seguente

Criterio di divisibilità per 5

Un numero è divisibile per 5 se e solo se

la cifra delle unità è 0 oppure 5.

Divisibilità per 2

Rifate lo stesso ragionamento sostituendo la congruenza modulo 2 alla congruenza modulo 5.

Che criterio si ottiene?

Criterio di divisibilità per 2

Un numero è divisibile per 2 se e solo se

la cifra delle unità è pari