Trovare un resto

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$

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

100 ore sull'orologio

Sono le 9. Dove punterà la lancetta delle ore tra 100 ore?

Togli i giri completi: un giro dell'orologio dura 12 ore: $100 = 8 \times 12 + 4$, e 8 giri completi non cambiano nulla = $100 \bmod 12 = 4$

Aggiungi le ore rimanenti alla partenza: $9 + 4 = 13$ = $13$

Riduci di nuovo, perché sul quadrante non c'è il 13: $13 = 1 \times 12 + 1$ = $13 \bmod 12 = 1$

Answer: La lancetta punta sull'1. In una riga: $9 + 100 = 109 = 9 \times 12 + 1$, quindi $109 \equiv 1 \pmod{12}$.

Prima riduci, poi moltiplica

Calcola $(38 \times 27) \bmod 5$ senza moltiplicare i numeri grandi.

Riduci ogni fattore modulo 5: $38 = 7 \times 5 + 3$ e $27 = 5 \times 5 + 2$ = $38 \equiv 3$ e $27 \equiv 2 \pmod{5}$

Moltiplica i resti: $3 \times 2 = 6$ = $6$

Riduci il prodotto: $6 = 1 \times 5 + 1$ = $1$

Verifica con il prodotto completo: $38 \times 27 = 1026 = 205 \times 5 + 1$ = stesso resto $1$

Answer: $(38 \times 27) \bmod 5 = 1$. Riducendo prima è bastato calcolare $3 \times 2$.

Tornare indietro nel calendario

Oggi è mercoledì. Che giorno della settimana era 30 giorni fa? Numera i giorni lunedì $= 0$, martedì $= 1$ e così via fino a domenica $= 6$.

Dai il suo numero al giorno di oggi: lunedì $= 0$, martedì $= 1$, mercoledì $= 2$ = $2$

Tornare indietro nel tempo significa sottrarre: $2 - 30 = -28$ = $-28$

Trova il resto tra 0 e 6 del numero negativo: $-28 = (-4) \times 7 + 0$ = $-28 \bmod 7 = 0$

Ritrasforma il numero in un giorno: Il giorno $0$ è lunedì = lunedì

Answer: 30 giorni fa era lunedì. Verifica: 28 giorni fa era mercoledì (esattamente 4 settimane), e due giorni prima è lunedì.

L'ultima cifra di una potenza enorme

Qual è l'ultima cifra di $3^{100}$?

L'ultima cifra è il resto modulo 10. Scrivi le prime potenze: $3^1 = 3$, $3^2 = 9$, $3^3 = 27$, $3^4 = 81$ = ultime cifre $3, 9, 7, 1$

Individua il ciclo: $3^5 = 243$ finisce di nuovo con 3, perché l'ultima cifra successiva dipende solo da quella precedente = lunghezza del ciclo $4$

Trova dove cade l'esponente 100 nel ciclo: $100 = 25 \times 4 + 0$ = $100 \bmod 4 = 0$

Resto 0 significa l'ultimo posto del ciclo: $3^{100} = (3^4)^{25} \equiv 1^{25} = 1 \pmod{10}$ = ultima cifra $1$

Answer: $3^{100}$ finisce con $1$, anche se ha 48 cifre.

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

Why: 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.

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

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

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

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

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

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

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

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

Why: 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.

Correct: 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$.

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.

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).

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.

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$.

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.

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.

Q: $a \bmod n$ è lo stesso resto che mostra la mia calcolatrice o il mio computer?

A: 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$ e $n - 1$, quindi $-3 \bmod 12 = 9$. La calcolatrice di questa pagina funziona così: mod(-3, 12) dà 9.

Q: Che cosa significa il simbolo $\equiv$?

A: 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.

Q: Perché posso ridurre prima i numeri?

A: 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.

Q: Dove si usa l'aritmetica modulare fuori dalla scuola?

A: 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.