Entendendo Aritmética Modular Intuitivamente (A Matemática do Relógio e Por Que o Resto Manda)

São nove da manhã e um voo parte em cinco horas. Ninguém aponta para o mostrador e lê quatorze. Você diz duas, e fez isso sem pensar, porque o mostrador de um relógio não tem quatorze. As horas dão a volta no doze e começam de novo. Você faz aritmética modular desde que aprendeu a ver a hora; só nunca foi apresentado à notação.

É esse o assunto inteiro. Escolha um número no qual dar a volta, esqueça toda volta completa e guarde apenas onde você parou. O que torna isso digno de um artigo é que esse único hábito, guardar só o resto, resolve problemas que de frente parecem impossíveis: o último dígito de um número de setenta dígitos, se um número gigante é divisível por 9, por que o número de um cartão de crédito é válido ou não, e como uma mensagem pode ser embaralhada de modo que só o destinatário consiga desembaralhá-la.

Este artigo é a imagem: o que é de fato um resto, por que você tem permissão para reduzir antes de calcular, o que acontece com negativos e com potências, e de onde vem a única dificuldade honesta, a divisão.

Um resto é onde você para, não o que sobrou

A definição padrão diz que $a \bmod n$ é o resto da divisão de $a$ por $n$. Isso está correto e também é a razão de o assunto parecer uma obrigação chata, porque "resto" soa como a sucata que fica depois de uma divisão, um detalhe de última hora.

Imagem melhor: uma pista circular com $n$ marcas, numeradas de $0$ a $n-1$. Para achar $a \bmod n$, comece no $0$ e caminhe $a$ passos pela pista. Onde você para é a resposta. Caminhar 17 passos por uma pista com 5 marcas dá três voltas completas (15 passos) e mais 2, então você para na marca 2. Daí $17 \bmod 5 = 2$. As voltas completas são o quociente; onde você para é o resto.

Essa imagem faz duas coisas que a definição não faz. Ela garante que o resto sempre caia no intervalo de $0$ a $n-1$, já que essas são as únicas marcas. E explica por que dois números podem ser "o mesmo" módulo $n$ mesmo sendo absurdamente diferentes: $2$, $17$, $102$ e $5{,}000{,}002$ param todos na marca 2 de uma pista de 5 marcas. Eles diferem por voltas, e a pista não guarda lembrança de voltas.

Os matemáticos escrevem essa ideia como uma congruência:

$$17 \equiv 2 \pmod{5}$$

Leia como "17 para onde 2 para, na pista de 5". A barra tripla não é um sinal de igual, porque 17 e 2 não são iguais. Ela diz que os dois são intercambiáveis para qualquer pergunta que só se interesse pela posição na pista. A versão precisa: $a \equiv b \pmod{n}$ significa que $n$ divide $a - b$, o que é apenas dizer que os dois números diferem por um número inteiro de voltas.

Somar e multiplicar só se importam com onde você está

Aqui está o fato que transforma a aritmética modular em ferramenta, e não em curiosidade. Se você vai somar dois números e depois achar o resto, pode achar os restos primeiro, somá-los e reduzir de novo. A resposta é idêntica. O mesmo vale para a subtração e a multiplicação.

Na pista é óbvio. Somar 17 significa caminhar 17 passos, que são três voltas mais 2. As três voltas devolvem você ao ponto de partida e não mudam nada, então somar 17 tem exatamente o mesmo efeito que somar 2. As voltas escondidas dentro de um número são peso morto, e seguem peso morto através da soma e da multiplicação, porque um múltiplo de $n$ vezes qualquer coisa continua múltiplo de $n$.

Escrito por extenso, com $a = qn + r$ e $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Tudo no primeiro parêntese é volta. Só $rs$ sobrevive, então $ab \bmod n$ é $rs \bmod n$. Os restos carregam toda a informação de que a pergunta precisa.

É por isso que a dica no tópico de aritmética do Math Zen manda reduzir passo a passo em vez de calcular o valor completo. Suponha que você queira $123 \times 456 \bmod 7$. Você poderia multiplicar até 56,088 e dividir por 7 na chave. Ou pode notar que $123 = 119 + 4$, logo $123 \equiv 4$, e $456 = 455 + 1$, logo $456 \equiv 1$, e a resposta é $4 \times 1 = 4$. Duas reduções pequenas substituem uma multiplicação de quatro dígitos. O hábito é: nunca deixe um número crescer além de $n$ se você só se importa com o resto dele.

Os números negativos caminham para o outro lado

A imagem da pista também resolve o caso que mais derruba as pessoas. Quanto é $-3 \bmod 5$?

Caminhe 3 passos para trás a partir do 0 em uma pista de 5 marcas. Você passa pelo 4, depois pelo 3, e para no 2. Então $-3 \equiv 2 \pmod{5}$. Um número negativo é apenas uma caminhada no sentido contrário, a mesma ideia de Entendendo Números Negativos Intuitivamente, e o resto continua sendo onde você para, ainda entre $0$ e $n-1$.

O atalho: some voltas até o número ficar positivo. $-3 + 5 = 2$. Para $-14 \bmod 5$, some 15 (três voltas) e obtenha 1. Calculadoras e linguagens de programação discordam sobre restos negativos, e algumas devolvem $-4$ para $-14 \bmod 5$, então em uma prova sempre dê a resposta como a marca não negativa da pista, e confira a convenção da sua calculadora antes de confiar nela.

A subtração é a mesma história. $3 - 8 \pmod{5}$ é $-5$, que é exatamente uma volta para trás, então a resposta é 0. Ou reduza primeiro: $8 \equiv 3$, logo $3 - 3 = 0$.

O último dígito de uma potência enorme

Este é o problema que convence as pessoas de que vale a pena conhecer o assunto, e ele é consequência direta da regra de reduzir primeiro.

O último dígito de um número é o número mod 10, porque as dezenas, as centenas e tudo acima são múltiplos de 10 e voltam a parar no 0 em uma pista de 10 marcas. Então "qual é o último dígito de $7^{100}$" é a pergunta "quanto é $7^{100} \bmod 10$", e você nunca precisa calcular $7^{100}$.

Em vez disso, observe as potências de 7 caminhando pela pista de 10, reduzindo a cada passo:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

Assim que você chega ao 1, o ciclo recomeça: 7, 9, 3, 1, 7, 9, 3, 1, com período 4. Como $100 = 4 \times 25$, a centésima potência fica no fim de um ciclo completo, no mesmo ponto que $7^4$, e seu último dígito é 1.

Toda base tem um ciclo módulo 10, e a maioria é curta. As potências de 2 percorrem 2, 4, 8, 6. As de 3 percorrem 3, 9, 7, 1. As de 5 e de 6 nunca se movem. O método é sempre o mesmo: descubra o tamanho do ciclo reduzindo pelo caminho, divida o expoente pelo tamanho do ciclo, e o resto dessa divisão diz em que ponto do ciclo você está. É a ideia dos expoentes como multiplicação repetida, rodando em uma pista circular em vez de uma reta.

Por que o teste da soma dos dígitos para o 9 funciona

Todo mundo aprende que um número é divisível por 9 se seus dígitos somam um múltiplo de 9, e quase ninguém aprende por quê. A aritmética modular transforma isso em um argumento de uma linha.

Dez é uma volta mais um em uma pista de 9: $10 \equiv 1 \pmod{9}$. Então $100 = 10 \times 10 \equiv 1 \times 1 = 1$, e toda potência de 10 também é congruente a 1. Assim, um número como $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ é congruente a $4 + 5 + 2 + 7 = 18 \pmod{9}$, e 18 é $0$ na pista de 9, então 4,527 é divisível por 9. A soma dos dígitos não é um truque. É o próprio número, visto módulo 9.

O teste para o 3 funciona pela mesma razão, já que $10 \equiv 1 \pmod{3}$ também. O teste para o 11 vem de $10 \equiv -1 \pmod{11}$, o que faz as potências de 10 alternarem entre $1$ e $-1$ e dá a soma alternada dos dígitos. Todas as regras de divisibilidade que mandaram você decorar são um único fato, "reduza as potências de 10", aplicado a pistas diferentes.

Dígitos verificadores: aritmética modular na sua carteira

Todo ISBN, todo número de cartão de crédito e todo código de barras termina com um dígito cuja única função é ser um resto.

O último dígito de um ISBN de 13 dígitos é escolhido de modo que uma soma ponderada dos treze dígitos, com pesos alternando 1 e 3, seja congruente a $0 \pmod{10}$. Digite um dígito errado e a soma para em outro lugar da pista de 10, e o leitor recusa o código. Os cartões de crédito usam o algoritmo de Luhn, uma ponderação um pouco mais esperta que também pega a maioria dos casos em que dois dígitos vizinhos são trocados de lugar, de novo conferindo uma soma módulo 10.

Esses são os primos humildes de uma aplicação muito maior. A criptografia moderna se apoia no fato de que elevar um número a uma potência módulo um $n$ muito grande é fácil, enquanto reverter o processo sem uma chave secreta não é. A busca de ciclo que você fez acima para $7^{100}$ é a mesma operação, ampliada para números com centenas de dígitos, e a regra de reduzir pelo caminho é o único motivo de ela ser calculável.

A divisão é onde a pista fica esburacada

Soma, subtração e multiplicação se comportam em uma pista exatamente como se comportam na reta numérica. A divisão não, e é aqui que o assunto ganha sua reputação.

Na reta numérica comum, dividir por 4 significa multiplicar por $\tfrac{1}{4}$, o número que, vezes 4, dá 1. Em uma pista de 12, existe uma marca que, vezes 4, para no 1? Teste todas: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, e o padrão 4, 8, 0 se repete para sempre. Ele nunca acerta o 1. Então na pista de 12 não existe dividir por 4.

A razão é que 4 e 12 compartilham um fator. Comece com um múltiplo de 4, some ou tire voltas de 12, e você continua com um múltiplo de 4, então nunca consegue parar 1 depois de um múltiplo de 12. Tente 5 em vez disso: $5 \times 5 = 25 = 24 + 1 \equiv 1$, então 5 é seu próprio inverso na pista de 12 e dividir por 5 funciona bem. A regra: $a$ tem inverso módulo $n$ exatamente quando $a$ e $n$ não têm nenhum fator comum além de 1.

Essa regra tem uma consequência marcante. Se $n$ é primo, nada de $1$ até $n - 1$ compartilha fator com ele, então toda marca não nula tem inverso e você pode dividir livremente. As pistas primas são as em que todas as quatro operações funcionam, o que explica em boa parte por que os primos, cujo estoque a infinitude dos primos garante, estão no centro da teoria dos números e da criptografia.

De onde vêm os erros

A aritmética modular tem poucas peças móveis, e os erros são correspondentemente específicos.

O primeiro é reduzir o expoente em vez da base. Em $7^{100} \bmod 10$, você pode reduzir 7 módulo 10 (já está reduzido) e pode reduzir o expoente módulo o tamanho do ciclo uma vez que o conheça, mas não pode reduzir 100 módulo 10 e calcular $7^0$. Os expoentes vivem em outra pista, aquela cujo tamanho é o tamanho do ciclo, e misturar as duas pistas é o erro mais comum do assunto.

O segundo é um resto negativo. $-14 \bmod 5$ é 1, não $-4$. Mesma posição na pista, mas só um dos dois é o nome convencional, e os gabaritos querem o não negativo.

O terceiro é dividir sem conferir se existe inverso. Cancelar um fator comum dos dois lados de uma congruência só é legítimo se esse fator não compartilhar nada com o módulo. De $4 \times 2 \equiv 4 \times 5 \pmod{12}$, que é verdade porque os dois lados dão 8, você não pode cancelar o 4 e concluir que $2 \equiv 5$, o que é falso. As voltas que você descarta ao cancelar têm de ser voltas da pista original.

O quarto é esquecer de reduzir no final. Obter $rs = 21$ em uma pista de 7 e escrever 21 não é exatamente errado, mas também não é uma resposta. A resposta é uma marca da pista, e 21 são três voltas, então a marca é 0.

Onde o Math Zen se encaixa

O tópico de aritmética do Math Zen tem um bloco dedicado à aritmética modular, e a progressão é construída em torno do hábito de reduzir primeiro, não em torno da notação. Os primeiros problemas pedem restos simples e congruências com módulos pequenos, até que "onde eu paro" fique automático. Os blocos intermediários misturam negativos e produtos, onde o ponto é reduzir cada fator antes de multiplicar e dar o resto não negativo. Os blocos finais são os problemas de último dígito e de tamanho de ciclo, que são os que aparecem em provas de olimpíada e exames de admissão e que castigam quem tenta calcular a potência completa.

Como as sessões são curtas e os problemas voltam em intervalos espaçados, como descrito em repetição espaçada para praticar matemática, a manobra de achar o ciclo vira reflexo em vez de um procedimento que você precisa consultar. A maioria das pessoas não tem uma lacuna em aritmética modular que um capítulo de livro resolveria. Elas têm uma imagem, a pista, que nunca foi desenhada para elas, e umas quarenta repetições que nunca foram feitas.

A conclusão

Aritmética modular é aritmética em uma pista circular com $n$ marcas. Um resto é onde você para depois de caminhar $a$ passos, as voltas completas são esquecidas, e dois números são congruentes quando param na mesma marca. Como as voltas não contribuem em nada para somas e produtos, você pode reduzir cada número ao seu resto antes de somar ou multiplicar, e essa única permissão transforma contas impossíveis, como o último dígito de $7^{100}$, em ciclos curtos que você traça à mão. Os testes de divisibilidade são as potências de 10 reduzidas módulo 9, 3 ou 11. Os dígitos verificadores são restos que pegam erros de digitação. A divisão só funciona quando o número não compartilha fator com a pista, e é por isso que as pistas primas são especiais.

Quando um problema modular empaca, desenhe a pista. Pergunte onde cada peça para, reduza pelo caminho e mantenha o expoente na pista dele. A resposta é uma marca entre $0$ e $n - 1$, e a imagem vai levar você até lá antes da fórmula.