A aritmética modular é aritmética sobre um círculo. Dois números são congruentes módulo n se diferem por um múltiplo de n. Um relógio faz aritmética mod 12: 10 horas depois das 5 são 3, não 15. Essa ideia simples sustenta toda a criptografia moderna, funções hash, códigos de correção de erros e boa parte da teoria dos números.
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 |
A aritmética modular define congruência: a é congruente a b mod n se n divide a-b. Gauss a sistematizou em 1801. Ela está na base de toda a criptografia moderna de chave pública: a cifra RSA depende do pequeno teorema de Fermat, segundo o qual a^(p-1) é congruente a 1 mod p para qualquer primo p que não divida a. Funções hash usam operações modulares para mapear entradas grandes em saídas de tamanho fixo. Os inteiros mod n formam um anel completo e, quando n é primo, um corpo finito.