Che cosa significa il simbolo $\equiv$?

Si legge «è congruo a». $17 \equiv 5 \pmod{12}$ dice che 17 e 5 danno lo stesso resto nella divisione per 12 (entrambi danno 5). È più debole di $=$: numeri congrui possono essere numeri diversi che cadono nella stessa posizione del quadrante.

Perché posso ridurre prima i numeri?

Scrivi $a = pn + r$ e $b = qn + s$. Allora $a + b = (p + q)n + (r + s)$ e $a \times b = (pqn + ps + qr)n + rs$. Le parti con $n$ sono multipli di $n$ e non lasciano resto, quindi solo $r + s$ e $r \times s$ decidono il risultato.

Dove si usa l'aritmetica modulare fuori dalla scuola?

Nelle cifre di controllo (codici a barre, ISBN, l'IBAN di un conto bancario, che si verifica modulo 97), in informatica (tabelle hash, generatori di numeri casuali) e in crittografia: il metodo RSA che protegge l'home banking calcola con numeri enormi modulo il prodotto di due numeri primi.

Risorse per insegnanti

Aritmetica modulare

Impara l'aritmetica dell'orologio: resti, a mod n, congruenza modulo n e come usarli per i giorni della settimana, le cifre di controllo e l'ultima cifra di potenze enormi.

Avanzato25 minLezione

Condividi in Classroom

Scheda da stampare

Definizione

L'aritmetica modulare è il calcolo con i resti. Fissi un numero intero

n \geq 2

, il modulo, e di un numero tieni solo il suo resto nella divisione per

n

a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1

Per esempio,

17 \bmod 5 = 2

perché

17 = 3 \times 5 + 2

Due numeri sono congrui modulo n quando danno lo stesso resto. È come dire che

n

divide la loro differenza:

a \equiv b \pmod{n} \iff n \text{ divide } a - b

Quindi

38 \equiv 14 \pmod{12}

, perché

38 - 14 = 24 = 2 \times 12

(entrambi danno resto

2

Un orologio funziona esattamente così: dopo 12 ore la lancetta torna al punto di partenza, quindi le 15 e le 3 sono la stessa posizione,

15 \equiv 3 \pmod{12}

. In somme, differenze e prodotti puoi sostituire prima ogni numero con il suo resto e ridurre il risultato ancora una volta alla fine.

Prova subito

Quanto fa

23 \bmod 5

Esempi svolti

Calcola

47 \bmod 6

Trova il più grande multiplo di 6 che non supera 47

6 \times 7 = 42

, mentre

6 \times 8 = 48

è già troppo grande →

42

Scrivi 47 come quoziente per 6 più resto

47 = 7 \times 6 + 5

→ resto

5

Controlla che il resto sia tra 0 e 5

0 \leq 5 \leq 5

, quindi è un resto valido →

47 \bmod 6 = 5

Risposta: $47 \bmod 6 = 5$ , quindi $47 \equiv 5 \pmod{6}$ . Il quoziente $7$ non fa parte della risposta.

Errori comuni

Scrivere $-3 \bmod 12 = -3$ (oppure $3$ )

Perché è sbagliato: Un resto deve essere uno dei numeri $0, 1, \ldots, n - 1$ . Tornando indietro di 3 ore dalle 12 non arrivi né a un numero negativo né al 3.

Corretto: Aggiungi il modulo finché il numero è nell'intervallo: $-3 + 12 = 9$ , quindi $-3 \bmod 12 = 9$ .

Dire che le 9 più 4 ore fanno le 13 su un orologio da 12 ore

Perché è sbagliato: La somma $9 + 4 = 13$ è giusta, ma manca l'ultima riduzione. Ogni risultato va ridotto ancora una volta.

Corretto: $13 \bmod 12 = 1$ : l'orologio segna l'1.

Dare il quoziente invece del resto: $47 \bmod 6 = 7$

Perché è sbagliato: $47 : 6 = 7$ con resto $5$ . L'operazione mod tiene solo ciò che avanza, non quante volte il 6 sta nel 47.

Corretto: $47 \bmod 6 = 5$ , perché $47 = 7 \times 6 + 5$ .

Ridurre l'esponente con il modulo: $2^9 \bmod 7$ diventa $2^2 = 4$ perché $9 \bmod 7 = 2$

Perché è sbagliato: Puoi ridurre la base modulo $n$ , ma non l'esponente. L'esponente segue la lunghezza del ciclo delle potenze, che qui è 3 e non 7.

Corretto: Le potenze di 2 modulo 7 sono $2, 4, 1, 2, 4, 1, \ldots$ (ciclo di lunghezza 3). $9 \bmod 3 = 0$ , quindi $2^9 \equiv 1 \pmod{7}$ . Verifica: $512 = 73 \times 7 + 1$ .

Visuale interattivo

Le 9 più 100 ore: conta i giri

12 posizioni sul quadrante: modulo 12

Partenza

Aggiungi

Parti da 9 e vai avanti di 100 ore.

I giorni della settimana sono modulo 7: prima indovina, poi guarda

7 posizioni sul quadrante: modulo 7

Dove si fermerà la lancetta? Tocca la posizione sul quadrante.

2 + 100 ≡ ? (mod 7)

Parti da mer e vai avanti di 100 giorni.

Congrui modulo 12: stessa posizione sul quadrante

12 posizioni sul quadrante: modulo 12

Primo numero

Secondo numero

38 = 3 × 12 + 2

14 = 1 × 12 + 2

38 − 14 = 24 = 2 × 12

38 ≡ 14 (mod 12)

38 e 14 finiscono nella stessa posizione perché la loro differenza 24 è un multiplo di 12.

Numeri sulla posizione 2: … -10, 2, 14, 26, 38 …

Le ultime cifre delle potenze di 3 (modulo 10) si ripetono

10 posizioni sul quadrante: modulo 10

Base

Esponente

Moltiplica per 3 ancora e ancora, e tieni solo il resto ogni volta.

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Quanto fa

23 \bmod 5

Perché è importante

L'aritmetica modulare è la matematica di tutto ciò che gira in tondo:

Il tempo: gli orologi contano modulo 12 o 24, i giorni della settimana modulo 7. Che ore saranno tra 100 ore? Che giorno sarà tra 100 giorni?
Le cifre di controllo: l'ultima cifra di un codice a barre (EAN-13) si sceglie modulo 10, quella di un ISBN-10 modulo 11, e l'IBAN di un conto bancario si verifica modulo 97. Basta una cifra sbagliata e il controllo fallisce.
I numeri enormi: puoi trovare a mente l'ultima cifra di $3^{100}$ (un numero di 48 cifre), perché le ultime cifre sono resti modulo 10 e si ripetono in un ciclo.
L'informatica: le tabelle hash, i generatori di numeri casuali e la crittografia RSA dietro l'home banking calcolano tutti modulo $n$ .

Conosci già un caso: pari e dispari è semplicemente il calcolo modulo 2 (resto 0 o 1).

Applicazioni nel mondo reale

Calendari: che giorno sarà?

Una settimana ha 7 giorni, quindi i giorni della settimana si ripetono modulo 7. Le app di calendario, gli orari e gli indovinelli sui compleanni lo usano di continuo.

Esempio:

Un anno normale ha $365$ giorni e $365 = 52 \times 7 + 1$ . Quindi un compleanno che quest'anno cade di lunedì l'anno prossimo cadrà di martedì (a meno che in mezzo ci sia un 29 febbraio).

1Provaci tu stesso

Oggi è mercoledì. Il tuo scambio all'estero inizia tra esattamente 100 giorni. Numera i giorni lunedì $= 0$ , martedì $= 1$ e così via fino a domenica $= 6$ .

In che giorno della settimana inizia lo scambio?

Passo 1: Scegli la risposta giusta

Scegli il giorno:

Codici a barre e cifre di controllo

L'ultima cifra di ogni codice a barre EAN-13 è una cifra di controllo, scelta con l'aritmetica modulo 10. Lo scanner la ricalcola e rifiuta un codice con una cifra letta male.

Esempio:

Per il codice del libro $978030640615$ la somma pesata (pesi $1, 3, 1, 3, \ldots$ ) è $93$ , e $93 \bmod 10 = 3$ . La cifra di controllo è $10 - 3 = 7$ , quindi il codice completo è $9780306406157$ .

2Provaci tu stesso

Un negozio crea un codice prodotto con le 12 cifre $400123456789$ . Le cifre nelle posizioni 1, 3, 5, ... contano una volta, quelle nelle posizioni 2, 4, 6, ... contano tre volte. La cifra di controllo rende il totale un multiplo di 10.

Qual è la cifra di controllo?

Passo 1: Scrivi l'espressione matematica

Cifra di controllo:

Lavoro a turni e orologio a 24 ore

Gli orari dei treni, i turni in ospedale e i piani di volo usano l'orologio a 24 ore, cioè l'aritmetica modulo 24.

Esempio:

Un turno di notte inizia alle 22:00 e dura 9 ore: $22 + 9 = 31$ e $31 \bmod 24 = 7$ , quindi finisce alle 07:00.

3Provaci tu stesso

Un collaudo di una macchina in una fabbrica inizia alle 19:00 e dura 75 ore senza pause.

A che ora (da 0 a 23) finisce il collaudo?

Passo 1: Scrivi l'espressione matematica

Ora di fine:

Punti chiave

1 $a \bmod n$ è il resto della divisione di $a$ per $n$ ed è sempre uno dei numeri $0, 1, \ldots, n - 1$
2 $a \equiv b \pmod{n}$ significa che $a$ e $b$ danno lo stesso resto, cioè che $n$ divide $a - b$
3Un orologio calcola modulo 12, l'orologio a 24 ore modulo 24, i giorni della settimana modulo 7 e pari/dispari modulo 2
4In somme, differenze e prodotti puoi ridurre prima ogni numero e poi ridurre ancora il risultato
5Per un numero negativo aggiungi $n$ finché cade in $0, \ldots, n - 1$ : $-3 \bmod 12 = 9$
6Le potenze si ripetono in cicli modulo $n$ : trova la lunghezza del ciclo e riduci l'esponente modulo quella lunghezza, non modulo $n$

Domande frequenti

Per i numeri positivi sì. Per i numeri negativi molti linguaggi di programmazione danno un risultato negativo, per esempio

-3

per

-3

diviso

12

. In matematica il resto è sempre tra

0

n - 1

, quindi

-3 \bmod 12 = 9

. La calcolatrice di questa pagina funziona così: mod(-3, 12) dà 9.

Glossario

Modulo: Il numero fisso $n$ per cui dividi; i resti sono $0, 1, \ldots, n - 1$ (12 per un orologio, 7 per i giorni della settimana)
Resto: Ciò che avanza nella divisione: in $a = q \times n + r$ con $0 \leq r \leq n - 1$ è $r$
a mod n: Il resto della divisione di $a$ per $n$ , per esempio $17 \bmod 5 = 2$ e $-3 \bmod 12 = 9$
Congruo modulo n: Due numeri con lo stesso resto modulo $n$ , si scrive $a \equiv b \pmod{n}$ ; in modo equivalente $n$ divide $a - b$
Lunghezza del ciclo: Dopo quanti passi i resti delle potenze cominciano a ripetersi, per esempio 4 per le ultime cifre delle potenze di 3
Cifra di controllo: Una cifra in più alla fine di un codice (codice a barre, ISBN), scelta in modo che una somma pesata sia divisibile per 10 o per 11

Scheda formule

Divisione con resto

a = q \times n + r, \quad 0 \leq r \leq n - 1

$r$ è $a \bmod n$, $q$ è il quoziente

Congruenza

a \equiv b \pmod{n} \iff n \mid (a - b)

Stesso resto, oppure: la differenza è un multiplo di $n$

Prima riduci

(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n

Lo stesso vale per sottrazione e moltiplicazione

Numeri negativi

x \bmod n = (x + k \times n) \bmod n

Aggiungi un multiplo di $n$ finché il numero cade in $0, \ldots, n - 1$: $-3 + 12 = 9$

Sfida di oggiUn problema, tre tentativi

Altro su questo argomento

Numeri pari e dispari

Elementare15 min

Quadrati perfetti e numeri quadrati

Intermedio25 min