Aritmética Modular — Matemática do Relógio, Mod e Congruência

A aritmética modular significa trabalhar com restos após a divisão por um inteiro positivo fixo chamado módulo. Se dois números deixam o mesmo resto, eles se comportam da mesma forma nesse sistema modular, por isso muita gente chama isso de matemática do relógio.

Em um relógio de $12$ horas, $13$ horas cai em $1$, e $29$ horas cai no mesmo lugar que $5$ horas. Esse ciclo que se repete é a intuição por trás da aritmética modular.

O Que Significa Mod Na Aritmética Modular

Para um inteiro $a$ e um inteiro positivo $n$, a expressão $a \bmod n$ significa o resto quando $a$ é dividido por $n$.

Exemplo:

$$29 \bmod 12 = 5$$

porque

$$29 = 12 \cdot 2 + 5$$

O módulo é $12$, então somar ou subtrair $12$ não muda a posição de chegada no ciclo.

O Que Significa Congruência Módulo $n$

Congruência é a forma formal de dizer que dois inteiros se comportam da mesma maneira módulo $n$.

$$a \equiv b \pmod n$$

significa que $a$ e $b$ deixam o mesmo resto quando são divididos por $n$. Um teste equivalente é

$$n \mid (a-b)$$

que significa “$n$ divide $a-b$”.

Então

$$29 \equiv 5 \pmod{12}$$

porque $29 - 5 = 24$, e $12$ divide $24$.

Essa distinção importa:

• $29 \bmod 12 = 5$ é uma afirmação sobre resto.
• $29 \equiv 5 \pmod{12}$ é uma afirmação de congruência.

Elas estão relacionadas, mas não são intercambiáveis.

Exemplo Resolvido: $29$ Horas Depois Das $8$ Horas

Suponha que agora sejam $8$ horas, e você queira saber que horas serão $29$ horas depois em um relógio de $12$ horas.

Primeiro, reduza $29$ módulo $12$:

$$29 \bmod 12 = 5$$

Então somar $29$ horas tem o mesmo efeito que somar $5$ horas:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

Depois,

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

Portanto, o relógio marca $1$ hora.

O passo principal é a redução. Em módulo $12$, substituir $29$ por $5$ mantém a resposta igual e torna a conta mais fácil.

Por Que Reduzir Primeiro Facilita Os Problemas

Números grandes costumam ser mais fáceis de lidar depois que você os substitui por um número menor congruente.

Por exemplo, módulo $7$,

$$100 \equiv 2 \pmod 7$$

porque $100 - 2 = 98$ é divisível por $7$. Se o problema só se importa com valores módulo $7$, você pode trabalhar com $2$ em vez de $100$.

Erros Comuns

Confundir igualdade com congruência

$29 \equiv 5 \pmod{12}$ não significa $29 = 5$. Significa que eles pertencem à mesma classe de resto módulo $12$.

Esquecer que o módulo importa

$17 \equiv 5 \pmod{12}$ é verdadeiro, mas $17 \equiv 5 \pmod{10}$ é falso. Congruência sempre está ligada a um módulo específico.

Tratar mod como divisão comum

$29 \bmod 12$ é o resto $5$, não o quociente $2$ e nem a fração $29/12$.

Supor que % em software sempre segue a mesma convenção matemática

Para números positivos, o % das linguagens de programação muitas vezes coincide com a ideia de resto que os alunos aprendem primeiro. Com números negativos, as convenções podem variar, então o resultado pode não coincidir com o menor resto não negativo usado em muitos cursos de matemática.

Onde A Aritmética Modular É Usada

Você vê aritmética modular sempre que valores se repetem em ciclos: relógios, dias da semana, sistemas de dígito verificador, hashing e muitas partes da teoria dos números.

Ela também aparece em criptografia, mas a mesma ideia básica continua valendo: os números são agrupados pelos seus restos, e números congruentes podem ser tratados como equivalentes dentro desse sistema.

Tente Um Problema Parecido

Que dia da semana será $100$ dias depois de uma segunda-feira? Como os dias se repetem módulo $7$, comece reduzindo $100$ módulo $7$ antes de responder.

Se quiser outro caso para comparar, experimente sua própria versão no GPAI Solver e veja se reduzir primeiro deixa o trabalho mais curto.