A aritmética modular explicada
Toda a gente já faz aritmética modular: 10 horas depois das 8 são 6 horas, e o dia a seguir a domingo é segunda-feira. Contar recomeçando em 0 depois de n passos acaba por ter uma aritmética própria e completa, com regras, surpresas e um lugar central na teoria dos números e na criptografia que protege a internet.
Restos e congruência
Divida a por n e fique apenas com o resto: isso é a mod n, um número de 0 a n − 1. 26 mod 7 = 5, porque 26 = 3 × 7 + 5. Os números com o mesmo resto comportam-se da mesma maneira mod n, por isso chamamos-lhes congruentes: 26 ≡ 5 ≡ −2 (mod 7). Carl Friedrich Gauss introduziu esta notação nas suas Disquisitiones Arithmeticae de 1801, e ela transformou as antigas observações de Fermat e Euler numa aritmética própria. Num relógio com n posições, cada número inteiro cai no seu resto; as voltas completas são esquecidas.
Somar, subtrair e multiplicar
As três operações comuns funcionam como de costume, e pode reduzir mod n sempre que quiser: o resto de uma soma é o resto da soma dos restos, e o mesmo vale para diferenças e produtos. Para encontrar o último algarismo de 37 × 48, multiplique apenas os últimos algarismos: 7 × 8 = 56, portanto termina em 6. É isto que torna a aritmética modular tão útil para os computadores: por maiores que sejam os números, os valores intermédios nunca excedem n².
A divisão precisa de um inverso
A divisão é a exceção. 2 × 3 ≡ 2 × 8 (mod 10), já que ambos são 6 mod 10, mas 3 e 8 são diferentes, por isso não se pode simplesmente cancelar o 2. Dividir por a significa multiplicar pelo seu inverso, o número x com a × x ≡ 1, que existe exatamente quando a e n não têm nenhum fator comum. O algoritmo de Euclides estendido encontra-o: executa os passos de divisão de Euclides para o máximo divisor comum e regista um multiplicador em cada passo, de modo que, quando o resto chega a 1, o multiplicador é o inverso. Quando n é primo, todos os números exceto 0 têm inverso, e a divisão funciona sempre.
Potências, Fermat e Euler
As potências repetem-se. Tome as potências de 3 mod 7: 3, 2, 6, 4, 5, 1 e depois novamente 3. O comprimento desse ciclo é a ordem de 3. Em 1640, Pierre de Fermat reparou que, para um primo p, a^(p − 1) ≡ 1 (mod p) sempre que p não divide a, pelo que todas as ordens dividem p − 1. Leonhard Euler demonstrou-o e generalizou-o a qualquer n, substituindo p − 1 pelo número de valores primos com n. As potências enormes calculam-se por quadrados sucessivos: a, a², a⁴, a⁸ …, cada uma o quadrado da anterior, reduzida mod n, e depois multiplicadas de acordo com os algarismos binários do expoente.
Dígitos de controlo e calendários
A aritmética modular apanha erros. O último algarismo de um ISBN-10 é escolhido de modo que uma soma ponderada dos dez algarismos seja múltiplo de 11, pelo que qualquer algarismo errado isolado e qualquer troca de dois algarismos vizinhos é detetada. Os números de cartão bancário usam a verificação de Luhn mod 10, e os IBAN uma verificação mod 97. Os calendários funcionam mod 7: o dia da semana de qualquer data pode ser determinado com alguns restos, e é assim que funcionam os calendários perpétuos e a regra do dia do juízo final.
Criptografia
A criptografia moderna assenta em potências modulares que são fáceis de calcular e difíceis de desfazer. Na troca de chaves de Diffie–Hellman, de 1976, duas pessoas combinam um segredo partilhado numa linha aberta trocando potências módulo um primo grande. O RSA, publicado em 1977 por Rivest, Shamir e Adleman, cifra uma mensagem m como m^e mod n, em que n é o produto de dois primos grandes, e decifra com um segundo expoente d que só quem conhece os dois primos consegue calcular. No exemplo clássico dos manuais, n = 3233 = 61 × 53, e = 17 e d = 413: 65 passa a 2790, e 2790 volta a ser 65.
Explore
Abra o relógio modular para calcular a mod n, somas, diferenças, produtos, potências, inversos e quocientes mod n, para números até 30 algarismos. Cada resultado vem com os seus passos: a divisão com resto, as potências dos quadrados sucessivos ou a tabela do algoritmo de Euclides estendido. O relógio desenha como se chega ao resultado, desde a espiral de uma adição ao ciclo das potências, e para n pequenos a tabela da operação mostra todos os resultados de uma só vez.
Perguntas frequentes
O que significa o símbolo ≡?
a ≡ b (mod n) diz que a e b deixam o mesmo resto quando divididos por n ou, de forma equivalente, que n divide a − b. 38 ≡ 2 (mod 12), porque 38 − 2 = 36 é múltiplo de 12.
mod é o mesmo que o operador % em programação?
Para números positivos, sim. Para números negativos, muitas linguagens, como C, Java e JavaScript, devolvem um resto negativo: aí −7 % 3 dá −1, enquanto −7 mod 3 = 2. O operador % do Python segue a convenção matemática para n positivo.
O que é a ordem de um número mod n?
O menor k > 0 com a^k ≡ 1 (mod n). Só existe quando a e n não têm nenhum fator comum. A ordem de 2 mod 7 é 3, porque 2³ = 8 ≡ 1, e a ordem de 3 mod 7 é 6, por isso as potências de 3 percorrem todos os restos não nulos: 3 é uma raiz primitiva mod 7.
Quem inventou a aritmética modular?
Os restos já eram usados muito antes, por exemplo no teorema chinês dos restos, entre os séculos III e V, e por Fermat e Euler. Gauss fez dela uma aritmética sistemática, com a notação das congruências, em 1801.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o relógio modular