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.

Um relógio com doze posições numeradas de 0 a 11 e um caminho em espiral que dá uma volta ao mostrador de 9 a 2
Um relógio com doze posições numeradas de 0 a 11 e um caminho em espiral que dá uma volta ao mostrador de 9 a 2

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.

Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.

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.

Retrato de Pierre de Fermat
Retrato de Pierre de Fermat
Retrato de Leonhard Euler
Retrato de Leonhard Euler

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