Modular arithmetic è arithmetic on un circle. Two numeri sono congruent modulo n se they differ by un multiple di n. Un clock does arithmetic mod 12: 10 hours after 5 o'clock è 3, not 15. Questo simple idea underlies tutti modern cryptography, hash funziones, codici correttori d'errore, e much di numero theory.
Every row and column contains {0,1,2,3,4} exactly once. The five elements form a closed group under addition mod 5. Red: sums that wrap around (≥5).
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
L'aritmetica modulare definisce la congruenza: a è congruo a b modulo n se n divide a-b. Gauss la sistematizzò nel 1801. È alla base di tutta la moderna crittografia a chiave pubblica: la cifratura RSA si appoggia al piccolo teorema di Fermat, che afferma che a^(p-1) è congruo a 1 modulo p per ogni numero primo p che non divide a. Le funzioni hash usano operazioni modulari per mappare input grandi in output di dimensione fissa. Gli interi modulo n formano un anello completo e, quando n è primo, un campo finito.