Calculadora de Inverso Multiplicativo Modular

Boas-vindas à calculadora de inverso multiplicativo modular da Omni! Ela está aqui para te ajudar sempre que você precisar determinar inversos modulares multiplicativos ou inversos modulares aditivos.

Se você não tiver certeza do que é o inverso multiplicativo modular, continue lendo! Daremos a você todas as definições necessárias e ensinaremos como encontrar o inverso modular à mão!

Antes de aprendermos o que é o inverso multiplicativo modular, precisamos nos familiarizar com a relação de congruência.

Seja n um número natural (diferente de zero). Diz-se que dois números inteiros a e b são congruentes módulo n se ambos tiverem o mesmo resto quando divididos por n. De forma equivalente, a situação é a mesma quando a diferença a - b é divisível por n com zero como resto, ou seja, se a - b for um múltiplo de n.

Denotamos o fato de que a e b são congruentes módulo n por:

a ≡ b (mod n).

Vamos dar uma olhada em dois exemplos.

• Exemplo 1.

  14 e 99 são congruentes módulo 5:

  14 ≡ 99 (mod 5)

  porque 99 - 14 = 85 e 85 é um múltiplo de 5. De forma equivalente, vemos que 14 e 99 têm o mesmo resto quando divididos por 5:

  14 mod 5 = 4

  99 mod 5 = 4

• Exemplo 2.

  14 e 99 são não congruentes no módulo 7.

  Isso ocorre porque 99 - 14 = 85 e 85 não é um múltiplo de 7. De forma equivalente, basta você verificar que 14 e 99 têm resto diferente quando divididos por 7:

  14 mod 7 = 0

  99 mod 7 = 1

Para saber mais sobre a operação de módulo e, em particular, suas aplicações na vida real, visite nossa calculadora de módulo.

Agora, estamos prontos para aprender o que é o inverso multiplicativo modular!

Sejam a e x números inteiros. Dizemos que x é um inverso modular de a quando uma operação algébrica performada em x e a produz o elemento identidade.

Dependendo do fato de a operação em questão ser adição ou multiplicação, distinguimos dois tipos de inversos modulares: aditivo e multiplicativo.

Vamos falar mais sobre essas duas noções:

Inverso aditivo modular

No caso da adição, o elemento de identidade é 0. Dizemos então que x é um inverso aditivo de a módulo m se a + x e 0 forem congruentes módulo m:

a + x ≡ 0 mod m

Um inverso aditivo de a módulo m sempre existe para cada a e m. Ele é dado por qualquer número da forma -a + k · m, em que k é um número inteiro. Normalmente, queremos encontrar o inverso no intervalo {0, ... , m - 1}, ou seja, no conjunto dos restos da divisão por m.

Como você pode encontrar o inverso aditivo modular à mão? Na verdade, é muito fácil! Aqui estão os passos que você pode seguir para encontrar o inverso modular aditivo de a inverso multiplicativo m:

1. Escreva -a.
2. Anote os números criados pela adição ou subtração repetida de m a a.
3. Escolha o número que fica entre 0 e m - 1.

Vamos ver essas etapas com alguns exemplos.

• Exemplo 1.

  Vamos encontrar o inverso aditivo de 4 módulo 30.

  Os números da forma -4 + 30k são: ..., -4, 26, 56, ....

  Portanto, no conjunto {0, ..., 29}, o inverso aditivo modular de 4 em 30 é 26.

• Exemplo 2.

  Vamos encontrar o inverso aditivo de 44 módulo 13.

  Os números da forma -44 + 13k são: ..., -44, -31, -18, -5, 8, 22....

  Portanto, no conjunto {0, ..., 12}, o inverso aditivo modular de 44 em 13 é 8.

Inverso multiplicativo modular

Lembre-se de que o elemento identidade da multiplicação é 1. Portanto, x é um inverso multiplicativo modular de a em m se a · x e 1 forem congruentes em m:

a · x ≡ 1 mod m

Ao contrário dos inversos aditivos, o inverso modular multiplicativo nem sempre existe! No entanto, se existir, todos os números da forma x + k · m satisfazem a congruência exigida. Em particular, nesses casos, você sempre pode encontrar a solução (exatamente uma!) no intervalo {1, ... , m - 1}.

Um exemplo

Não existe inverso multiplicativo modular de 2 no módulo 6. Você pode verificar essa afirmação verificando que, para x ∊ {1, 2, 3, 4, 5}, a operação 2 · x (mod 6) não produz 1.

É importante que você se lembre de que o inverso multiplicativo modular de a modulo m existe se e somente se a e m forem relativamente primos, ou seja, seu Máximo Divisor Comum (MDC) for igual a um. Também chamamos esses números de coprimos. Em particular, se m é primo, então o inverso multiplicativo modular módulo m existe para qualquer a ≠ 0 que não seja um múltiplo de m.

Toda a teoria dos inversos modulares pode parecer um pouco abstrata, e você provavelmente está se perguntando: "Por que alguém se preocuparia com inversos modulares multiplicativos?" Bem, você deve saber que o computar de inversos modulares multiplicativos é essencial na criptografia e, em particular, no método de criptografia RSA. Isso significa que os inversos multiplicativos modulares protegem seu cartão de crédito!

Obviamente, o método mais rápido de determinar inversos modulares multiplicativos é usar nossa calculadora de inverso multiplicativo! 😉 Entretanto, se você precisar aprender a encontrar o inverso modular à mão, consulte a próxima seção.

Nesta seção, explicaremos como você pode encontrar o inverso modular multiplicativo. Há três métodos principais:

• O método simples (apesar de ser simples, pode ser lento);
• O algoritmo de Euclides estendido (mais rápido, funciona em todos os casos); e
• O pequeno teorema de Fermat (mais rápido, mas funciona apenas em alguns casos).

Independentemente do método utilizado, o primeiro passo é certificar que o inverso modular multiplicativo existe: lembre-se de que você deve verificar se a e m são coprimos, ou seja, se MCD(a,m) = 1. Para fazer isso, você pode usar nossa calculadora de MDC e MMC 🇺🇸.

Método simples

Um método simples consiste em tentar todos os números do conjunto {0, ..., m - 1}. Para cada número x desse conjunto, calcule a · x mod m, ou seja, o resto da divisão de a · x por m.

O inverso multiplicativo modular de a modulo m é o valor de x para o qual esse resto é igual a 1.

Algoritmo de Euclides estendido

O segundo método utiliza a identidade de Bézout e o algoritmo de Euclides estendido.

Identidade de Bézout. Suponha que a e b sejam números inteiros. Existem dois inteiros x e y tais que: a · x + b · y = MDC(a, b).

Lembre-se de que o algoritmo de Euclides estendido nos permite determinar efetivamente MDC(a, b) junto com os inteiros x e y, cuja existência é garantida pela identidade de Bézout.

Agora, vamos ver como você pode usar essa teoria para encontrar o inverso multiplicativo de a módulo m:

1. Lembre-se de que a e m são considerados relativamente primos, portanto, MDC(a,m) = 1.

2. Assim, a partir da identidade de Bézout, sabemos que:

   a · x + m · y = 1

   para alguns números inteiros x e y. Para encontrá-los, usamos o algoritmo euclidiano estendido.

3. Agora, vamos ver como isso está conectado ao inverso modular multiplicativo. Aplicando a operação mod m em ambos os lados da equação acima, você obtém:

   a · x + m · y ≡ 1 (mod m)

4. Como toda multiplicidade de m é congruente a 0 módulo m, obtemos, em particular, m · y ≡ 0 (mod m). Como resultado, podemos simplificar a nossa equação para:

   a · x ≡ 1 (mod m)

Mas essa última equação diz que o inteiro x encontrado pelo algoritmo de Euclides estendido é precisamente o inverso multiplicativo modular de a modulo m! A propósito, esse é o método utilizado pela nossa calculadora de inverso modular multiplicativo. 😀 Você pode usar esse método para calcular o inverso modular.

O pequeno teorema de Fermat

O último método usa o pequeno teorema de Fermat. Assumimos que m é um número primo e que a não é divisível por m.

Pequeno teorema de Fermat:
Se m for primo e a não for divisível por m, então a^m-1 - 1 é divisível por m.

Podemos escrever a afirmação do pequeno teorema de Fermat como

a^m-1 - 1 ≡ 1 mod m

que, por sua vez, podemos reescrever como

a · a^m-2 - 1 ≡ 1 mod m

Essa equação diz que o inverso multiplicativo de a módulo m é igual a a^m-2.

A instrução de uso da calculadora de inverso multiplicativo modular é simples:

1. Escolha o tipo de inverso modular que você está interessado em encontrar:

• Inverso modular multiplicativo; ou
• Inverso modular aditivo.

2. Digite os coeficientes da equação que você deseja resolver.
3. Em nossa calculadora de inverso multiplicativo modular, você verá a resposta com uma breve explicação.