Resultado
Sem mod
Voltas completas
mdc(a, n)

    Mais sobre aritmética modular

    Relógio modular

    Cinco horas depois das 9 são 2 horas, porque 9 + 5 = 14 e 14 é mais 2 do que 12. Isto é aritmética modular: contar num relógio que recomeça em 0 depois de n. Escolha uma operação, introduza n, a e b, e a calculadora dá o resultado com todos os passos detalhados, desde o resto de uma divisão até aos quadrados sucessivos e ao algoritmo de Euclides estendido, enquanto o relógio mostra como se chega ao resultado. Escolha uma operação e introduza o módulo n e os números a e b; funcionam números inteiros até 30 algarismos, também negativos, e n pode ir até 10^18. O relógio tem n posições com o 0 no topo, e o ponteiro aponta para o resultado. A adição e a subtração são desenhadas como uma espiral de b passos, com um anel por cada volta completa; a multiplicação como saltos de a; as potências como as cordas a, a², a³ …, que se fecham num ciclo; o inverso e a divisão como os múltiplos que caem em 1 ou em a. Os passos mostram o mesmo cálculo em números. Até mod 20 é mostrada a tabela da operação; clique numa célula para usar os seus números. Exemplo preenche um problema clássico.

    Como funciona

    1. Escolha uma operação: a mod n, adição, subtração, multiplicação, divisão, uma potência ou o inverso de a.
    2. Introduza o módulo n e os números a e b, ou escolha um exemplo como o último algarismo de 7^2026 ou uma pequena mensagem RSA.
    3. Leia o resultado e os passos, siga o caminho no relógio e, até mod 20, clique numa célula da tabela para experimentar os seus números.

    O que significa a mod n

    a mod n é o resto da divisão de a por n: 17 mod 5 = 2, porque 17 = 3 × 5 + 2. O resto vai sempre de 0 a n − 1, também para números negativos: −7 mod 3 = 2, porque −7 = −3 × 3 + 2. No relógio, isso significa andar 7 passos para trás a partir de 0. Dois números com o mesmo resto são congruentes, o que se escreve 17 ≡ 2 (mod 5), uma notação introduzida por Carl Friedrich Gauss em 1801. Somas, diferenças e produtos podem ser reduzidos mod n em qualquer passo, o que mantém os números pequenos.

    Onde se usa a aritmética modular

    Os relógios e os calendários funcionam mod 12, mod 24 e mod 7: 100 dias depois de uma quarta-feira é sexta-feira, porque 100 mod 7 = 2. Os dígitos de controlo usam-na para detetar erros de digitação, desde os números ISBN-10 (mod 11) aos números de cartão bancário (mod 10) e aos IBAN (mod 97). As cifras deslocam as letras mod 26, e a cifra afim precisa de um inverso mod 26 para decifrar. O RSA, que protege grande parte da internet, cifra uma mensagem m como m^e mod n e decifra com outra potência: com n = 3233, 65^17 mod 3233 = 2790 e 2790^413 mod 3233 = 65.

    Perguntas frequentes

    Como se calcula a mod n para um número negativo?

    Some ou subtraia múltiplos de n até o número ficar entre 0 e n − 1. Para −7 mod 3: −7 + 9 = 2, portanto o resultado é 2. Algumas linguagens de programação dão antes −1 para −7 % 3, porque arredondam o quociente para zero; em matemática, o resto nunca é negativo.

    O que é um inverso modular?

    O inverso de a mod n é o número x com a × x ≡ 1 (mod n). O inverso de 7 mod 26 é 15, porque 7 × 15 = 105 = 4 × 26 + 1. Só existe quando a e n não têm nenhum fator comum, e o algoritmo de Euclides estendido encontra-o. Dividir por a mod n significa multiplicar pelo seu inverso.

    Como se pode calcular mod n uma potência como 7^2026?

    Por quadrados sucessivos: eleve 7 ao quadrado uma e outra vez, reduzindo mod n de cada vez, para obter 7^1, 7^2, 7^4, 7^8 e assim por diante, e depois multiplique as que compõem 2026 em binário. Isso exige 10 elevações ao quadrado e 7 multiplicações em vez de 2.025 multiplicações, e os números nunca ficam maiores do que n². 7^2026 termina em 9.

    Porque é que o relógio mostra 0 em vez de 12?

    Na aritmética modular, os restos vão de 0 a n − 1, por isso num relógio com 12 posições o meio-dia é 0. 12 ≡ 0 (mod 12); um relógio comum simplesmente mostra 12 onde a matemática escreve 0.

    Até que tamanho podem ir os números?

    a e b podem ter até 30 algarismos e ser negativos, e o módulo pode ir até 10^18. A calculadora trabalha com números inteiros exatos no seu navegador, por isso até exemplos do tamanho do RSA dão resultados exatos, e nada é enviado para lado nenhum.

    Pronto para experimentar?

    Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

    Ir para o editor