Relógio de aritmética modular

Escolha o módulo n e a operação. Veja o resultado em um relógio modular e examine as tabelas de adição/multiplicação.

Exemplo resolvido — Relógio de aritmética modular

Expressão	7 x 5 (mod 12)
Resultado	11

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Um módulo primo devolve a divisão 🖖

A aritmética modular trata de inteiros sob um módulo cíclico n, escrito como a ≡ b (mod n). Este sistema algébrico forma um anel comutativo Z/nZ. Se o módulo p for primo, o anel torna-se um corpo, significando que cada elemento não nulo tem um inverso multiplicativo.

Por que se chama aritmética do relógio 🖖

Num relógio de 12 horas, 4 horas depois das 11 são 3, não 15 — os números voltam ao início ao passar de 12. É exatamente isso a aritmética modular: a ≡ b (mod n) significa que a e b deixam o mesmo resto quando divididos por n. Assim, 15 ≡ 3 (mod 12). A ideia central: a aritmética modular guarda apenas o resto da divisão, e o relógio desta ferramenta mostra os números girando em círculo.

A regra do 9 é aritmética modular disfarçada 🖖

A velha regra "um número é divisível por 9 se a soma dos seus algarismos também for" é pura aritmética modular. Como 10 ≡ 1 (mod 9), toda potência de 10 também é ≡ 1, de modo que um número é congruente à soma dos seus algarismos (mod 9). O mesmo fato sustenta a prova dos nove, um método com séculos de idade para conferir contas à mão.

ARITMÉTICA MODULAR — QUANDO DÁ PARA DIVIDIR E QUANDO NÃO?

Em que caso de aritmética modular você está?

Trabalhar módulo n significa guardar só o resto, e a soma, a subtração e a multiplicação saem ilesas disso. A divisão não. Poder dividir por um número — ele ter inverso — depende unicamente de compartilhar ou não um fator com n, e é por isso que um módulo primo se comporta de forma tão diferente de um composto. O caso depende da operação e de que tipo de número é n.

Soma — sempre bem comportada, seja qual for n 13 + 5 ≡ 6 (mod 12)

Módulo primo — dá para dividir por todo elemento não nulo φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Módulo composto — por quase nenhum elemento dá para dividir 2 × 3 ≡ 0, φ(6) = 2

Potências repetidas — elas ciclam, e Fermat diz onde a^p−1 ≡ 1 (mod p)

Soma — sempre bem comportada, seja qual for n

O que você sabe: Qualquer módulo. Somar, subtrair e multiplicar módulo n estão sempre definidos, e todo elemento tem seu oposto aditivo.

O que verificar: 13 + 5 ≡ 6 (mod 12)

Exemplo resolvido: Um relógio de 12 horas: 13 + 5 = 18, e 18 mod 12 = 6. Cinco horas depois de uma hora são seis horas.

Abrir este caso: relógio mod 12

Soma — sempre bem comportada, seja qual for n. A tabela de soma módulo 12: cada linha é a anterior deslocada uma casa, e cada valor aparece exatamente uma vez. Qualquer módulo. Somar, subtrair e multiplicar módulo n estão sempre definidos, e todo elemento tem seu oposto aditivo. — A tabela de soma módulo 12: cada linha é a anterior deslocada uma casa, e cada valor aparece exatamente uma vez.

Módulo primo — dá para dividir por todo elemento não nulo

O que você sabe: n é primo. Então nenhum elemento não nulo compartilha fator com n, de modo que todos têm inverso multiplicativo.

O que verificar: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Exemplo resolvido: Módulo 7: 3 × 4 = 12 ≡ 5. Os seis valores não nulos 1…6 são invertíveis, então a tabela de multiplicação não tem zeros fora da primeira linha.

Abrir este caso: primo mod 7

Módulo primo — dá para dividir por todo elemento não nulo. A tabela de multiplicação módulo 7: nenhum zero abaixo da primeira linha, e cada linha uma permutação de 1 a 6. n é primo. Então nenhum elemento não nulo compartilha fator com n, de modo que todos têm inverso multiplicativo. — A tabela de multiplicação módulo 7: nenhum zero abaixo da primeira linha, e cada linha uma permutação de 1 a 6.

Módulo composto — por quase nenhum elemento dá para dividir

O que você sabe: n é composto. Só os valores coprimos com n têm inverso; o resto são divisores de zero, e dividir por eles não significa nada.

O que verificar: 2 × 3 ≡ 0, φ(6) = 2

Exemplo resolvido: Módulo 6: 2 × 4 = 8 ≡ 2. Nem 2 nem 4 é invertível, pois mdc(2,6) = 2 e mdc(4,6) = 2. Só 1 e 5 são unidades — dois de seis.

Abrir este caso: composto mod 6

Módulo composto — por quase nenhum elemento dá para dividir. A tabela de multiplicação módulo 6, salpicada de zeros e com apenas duas linhas que são permutações. n é composto. Só os valores coprimos com n têm inverso; o resto são divisores de zero, e dividir por eles não significa nada. — A tabela de multiplicação módulo 6, salpicada de zeros e com apenas duas linhas que são permutações.

Potências repetidas — elas ciclam, e Fermat diz onde

O que você sabe: Elevar a uma potência módulo n. Para p primo e a não divisível por p, os expoentes se repetem com período que divide p − 1.

O que verificar: a^p−1 ≡ 1 (mod p)

Exemplo resolvido: Módulo 13: 7¹² ≡ 1. O pequeno teorema de Fermat garante isso para toda base de 1 a 12, sem calcular uma única potência grande.

Abrir este caso: Fermat mod 13

Potências repetidas — elas ciclam, e Fermat diz onde. As potências de cada base módulo 13; a coluna do expoente 12 volta a 1 para toda unidade. Elevar a uma potência módulo n. Para p primo e a não divisível por p, os expoentes se repetem com período que divide p − 1. — As potências de cada base módulo 13; a coluna do expoente 12 volta a 1 para toda unidade.

Problema resolvido na íntegra

Calcular 7 12 mod 13 na grelha completa 5 passos
Calcule 7¹² mod 13 sem nunca escrever 7¹². Esta é a operação a^k com n = 13, a = 7 e k = 12, e a grelha é a tabela completa de a^k mod 13.
1. 7¹² é 13 841 287 201 — onze dígitos para uma resposta que tem de resultar num valor entre 0 e 12. A redução conserva-se na multiplicação: o resíduo de um produto depende apenas dos resíduos dos seus fatores, pelo que se pode reduzir após cada passo em vez de o fazer apenas no fim.
  
  $7^{12} = 13841287201, x y mod n = ((x mod n) (y mod n)) mod n$
2. O pequeno teorema de Fermat determina a resposta antes de se efetuar qualquer aritmética. Para um primo p e um a que p não divide, a^p−1 ≡ 1; aqui p = 13 e k é exatamente p − 1, pelo que o resultado é 1 e tudo o que se segue é uma verificação do teorema em vez de uma procura pela resposta.
  
  $p = 13 prime, 13 ∤ 7 ⟹ 7^{12} = 7^{p - 1} \equiv 1 (mod 13)$
3. Elevar ao quadrado duplica o expoente, pelo que três elevações ao quadrado atingem 7⁸. Cada linha reduz-se antes de a seguinte começar, razão pela qual nenhum número em todo o cálculo excede 100.
  
  $7^{2} = 49 \equiv 10, 7^{4} \equiv 1 0^{2} = 100 \equiv 9, 7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
4. 12 é 8 + 4, e ambas essas potências foram calculadas no percurso, pelo que mais uma multiplicação conclui o processo. Quatro multiplicações no total, contra as onze que um produto da esquerda para a direita de doze setes exigiria — e a poupança cresce com o expoente, não com o módulo.
  
  $12 = 110 0_{2} = 8 + 4 ⟹ 7^{12} \equiv 7^{8} \cdot 7^{4} \equiv 3 \times 9 = 27 \equiv 1 (mod 13)$
5. A ordem de 7, isto é, o menor k com 7^k ≡ 1, tem de dividir 12, pelo que é um dos valores 1, 2, 3, 4, 6 e 12. A verificação dos cinco divisores próprios exclui cada um deles, logo a ordem é exatamente 12.
  
  $7^{1} \equiv 7, 7^{2} \equiv 10, 7^{3} \equiv 5, 7^{4} \equiv 9, 7^{6} \equiv 12 ⟹ ord_{13} (7) = 12$
Resposta

As três elevações ao quadrado e a multiplicação final reproduzem a linha da ferramenta para a = 7 sem erro: 10 em k = 2, 9 em k = 4, 3 em k = 8, e 1 em k = 12 onde Fermat afirmou que estaria. Como a ordem é 12 e não um divisor próprio deste — o teste da ordem necessitava de 12 em k = 6, que não é 1 — essa linha é uma permutação dos números de 1 a 12, atingindo cada resíduo não nulo exatamente uma vez, o que torna 7 uma raiz primitiva mod 13. Leia agora a linha no outro sentido: dado 11, determine k. Não existe um método de elevação ao quadrado e multiplicação para isso, apenas uma pesquisa, e essa assimetria entre o sentido direto fácil e o sentido inverso difícil é toda a base da troca de chaves de Diffie–Hellman. O algoritmo escala de uma forma que a tabela não consegue: um expoente de 2048 bits custa no máximo cerca de 4 000 multiplicações modulares, enquanto a potência por ele designada exigiria sensivelmente 2,7 × 10⁶¹⁶ dígitos para ser escrita por extenso.

$ord_{13} (7) = 12 ⟹ {7^{k} mod 13}_{k = 1}^{12} = {1, 2, \dots, 12}$

Percurso de aprendizagem

Quando duas coisas vão dar ao mesmo valor

Conduz a Paradoxo do aniversário

Referências (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Matemática →

Problemas de exemplo

relógio mod 12 - Aritmética do relógio: 13 ≡ 1 (mod 12), então 13+5 dá a volta e resulta em 6.
primo mod 7 - Módulo primo: as linhas de multiplicação não nulas se comportam como permutações.
composto mod 6 - Módulo composto mostra linhas repetidas onde gcd(row,n) > 1.
Fermat mod 13 - Padrão do tipo Fermat: a^(p-1) ≡ 1 mod p para p primo e gcd(a,p)=1.