Última atualização: 2026-06-05

A aritmética modular é o ramo da teoria dos números que estuda inteiros reduzidos por um divisor fixo chamado módulo. Dois inteiros são congruentes módulo n quando a diferença entre eles é múltipla de n, escrevendo-se a ≡ b (mod n). Esta calculadora avalia três operações fundamentais: o resto da divisão euclidiana, a exponenciação modular rápida e o inverso modular.

A operação módulo

Para um módulo positivo n, a operação a mod n é definida como o único inteiro r em [0, n − 1] que satisfaz:

$a = q \times n + r$

onde q = ⌊a / n⌋ é o quociente inteiro e r é o resto. Essa definição produz sempre um resultado não negativo — diferentemente do operador de resto truncado presente em diversas linguagens de programação.

Exemplo. Para a = 17 e n = 5:

$q = \lfloor 17 / 5 \rfloor = 3$

$r = 17 - 3 \times 5 = 2$

Portanto, 17 mod 5 = 2. A analogia com um relógio circular de cinco posições é imediata: contando 17 passos, chega-se à posição 2.

Valores negativos. Para a = −7 e n = 5:

$q = \lfloor -7 / 5 \rfloor = -2$

$r = -7 - (-2) \times 5 = 3$

Assim, −7 mod 5 = 3, não −2. A definição matemática mantém r não negativo; o operador % em C e JavaScript devolveria −2. Python (tanto a versão 2 quanto a 3) já segue a divisão euclidiana e devolve 3.

Exponenciação modular

Calcular a^b mod n de forma direta — primeiro computando a^b e depois reduzindo — é impraticável para expoentes grandes, pois a^b cresce exponencialmente. A exponenciação modular rápida (quadração sucessiva) contorna esse problema reduzindo módulo n a cada passo.

O algoritmo decompõe o expoente em binário. Partindo de resultado = 1:

• A cada bit de b, do menos significativo ao mais significativo, eleva-se a base acumulada ao quadrado módulo n.
• Quando o bit é 1, multiplica-se o resultado pela potência atual da base, reduzindo módulo n.

Esse processo exige no máximo 2 log₂(b) multiplicações em vez de b − 1, e todos os valores intermediários permanecem em [0, n − 1].

Exemplo. Para a = 17, b = 3, n = 5:

$17 \equiv 2 \pmod{5}$

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

$17^3 = 17^2 \times 17 \equiv 4 \times 2 = 8 \equiv 3 \pmod{5}$

Portanto, 17^3 mod 5 = 3. Verificação direta: 17^3 = 4913 = 982 × 5 + 3.

Inverso modular

O inverso modular de a módulo n é um inteiro x que satisfaz:

$a \times x \equiv 1 \pmod{n}$

Esse inverso existe se e somente se mdc(a, n) = 1 — ou seja, a e n são coprimos. Quando n é primo, todo inteiro de 1 a n − 1 possui inverso. Quando n é composto, valores que compartilham um fator com n não têm inverso.

O algoritmo de Euclides estendido calcula o inverso quando ele existe. O método amplia o cálculo do máximo divisor comum para rastrear combinações lineares, obtendo inteiros s e t tais que:

$a \times s + n \times t = \text{mdc}(a, n)$

Quando mdc(a, n) = 1, o valor s é o inverso modular de a módulo n.

Exemplo. Para a = 3, n = 5:

Aplicando o algoritmo de Euclides estendido:

• 5 = 1 × 3 + 2
• 3 = 1 × 2 + 1

Substituição retroativa: 1 = 3 − 1 × 2 = 3 − 1 × (5 − 1 × 3) = 2 × 3 − 1 × 5

Portanto, 3 × 2 ≡ 1 (mod 5), ou seja, 3⁻¹ ≡ 2 (mod 5).

Verificação: 3 × 2 = 6 = 1 × 5 + 1.

Aplicações práticas

A aritmética modular aparece em diversas áreas da matemática e da computação:

• Criptografia de chave pública. O algoritmo RSA eleva uma mensagem a um grande expoente módulo o produto de dois números primos; a descriptografia utiliza o inverso modular do expoente de cifração.
• Dígitos verificadores. CPF, CNPJ, ISBN-13 e IBAN empregam aritmética modular para detectar erros de digitação.
• Cálculos de calendário. O dia da semana após d dias é determinado por d mod 7; o cálculo da data da Páscoa envolve congruências em ciclos múltiplos.
• Tabelas de dispersão. Uma chave é mapeada ao índice de um balde pelo cálculo chave mod tamanho_da_tabela.
• Estruturas cíclicas. Filas circulares e buffers em anel avançam o ponteiro de leitura/escrita por meio de índice mod capacidade.

Quociente inteiro e identidade euclidiana

Para todo par (a, n) com n ≥ 1, o quociente inteiro q = ⌊a / n⌋ e o resto r = a mod n satisfazem a identidade euclidiana:

$a = q \times n + r, \quad 0 \leq r < n$

Esta calculadora exibe tanto r quanto q, permitindo verificar a identidade diretamente para qualquer par de entradas.