Nell’aritmetica modulare si contano solo i resti, come su un orologio: 17 ore dopo le 9 sono le 2. È la matematica della crittografia (i codici delle carte e dei siti sicuri), dei codici di controllo, dei calendari. Le ricorrenze sono successioni in cui ogni termine si calcola dai precedenti.
Le congruenze
Due numeri sono congrui modulo n se danno lo stesso resto nella divisione per n, cioè se la loro differenza è un multiplo di n. Si scrive 26 ≡ 2 (mod 12). Il resto di 17 diviso 5 è 2: 17 mod 5 = 2.
Con le congruenze si può sommare e moltiplicare sostituendo ogni numero con il suo resto, e i conti restano piccoli.
Esempio17 − 3 · 5 = 2il resto di 17 diviso 5
L’algoritmo di Euclide
Il MCD di due numeri è uguale al MCD del più piccolo e del resto della divisione. Ripetendo, si arriva a un resto zero: l’ultimo resto non nullo è il MCD. Per 252 e 198: 252 = 1 · 198 + 54, 198 = 3 · 54 + 36, 54 = 1 · 36 + 18, 36 = 2 · 18. Il MCD è 18.
Ripercorrendo i passaggi all’indietro si scrive il MCD come combinazione dei due numeri (identità di Bézout): da qui si trova l’inverso modulo n. L’inverso di 3 modulo 7 è 5, perché 3 · 5 = 15 e 15 diviso 7 dà resto 1.
Equazioni e il teorema di Fermat
Per risolvere 2x ≡ 3 (mod 5) si moltiplica per l’inverso di 2, che è 3: x ≡ 9 ≡ 4 (mod 5).
Il piccolo teorema di Fermat: se p è primo e non divide a, allora ap−1 ≡ 1 (mod p). Così 36 ≡ 1 (mod 7), e per 3100 basta guardare il resto di 100 diviso 6, che è 4: 3100 ≡ 34 = 81 ≡ 4 (mod 7).
Le ricorrenze
Una ricorrenza dà ogni termine in funzione dei precedenti, più i primi termini. La più famosa è quella di Fibonacci: an = an−1 + an−2, con a0 = 0 e a1 = 1, che dà 0, 1, 1, 2, 3, 5, 8, 13…
Le ricorrenze lineari si risolvono come le equazioni differenziali: per an = 3an−1 − 2an−2 si cercano soluzioni del tipo tn, che portano all’equazione caratteristica t2 − 3t + 2 = 0, con soluzioni 1 e 2. Con a0 = 1 e a1 = 3 si trova la formula chiusa an = 2n+1 − 1.
Esempio23 + 1 − 1 = 15il termine con n = 3, e infatti i primi termini sono 1, 3, 7, 15
Attenzione
- Nelle congruenze non si può sempre dividere: si può “dividere” per un numero solo se è primo con il modulo, moltiplicando per il suo inverso.
- Il resto si prende sempre fra 0 e n − 1: −1 modulo 7 è 6.
- Una ricorrenza di ordine 2 ha bisogno di due termini iniziali per essere determinata.
Allenati
Un esercizio nuovo ogni volta: scrivi la risposta e controlla se è giusta. Si parte dal livello Base; con tre risposte giuste di fila si passa a quello successivo. Il livello lo puoi anche scegliere tu.
Carico l’esercizio…
Prova tu
Tocca un esercizio: lo svolgo passo passo. Prima prova a farlo a mente con le proprietà, poi confronta.