Inverso multiplicativo modular
Esta calculadora calcula o inverso multiplicativo modular de um determinado número inteiro a módulo m.This calculator calculates modular multiplicative inverse of an given integer a modulo m
Esta calculadora calcula o inverso multiplicativo modular de um determinado número inteiro a módulo m.This calculator calculates modular multiplicative inverse of an given integer a modulo m. A teoria está abaixo da calculadora.
O inverso multiplicativo modular de um número inteiro a módulo m é um número inteiro b tanto que
,
Pode ser notado , onde o fato de que a inversão m-modular está implícita.
O inverso multiplicativo de um módulo m se e apenas se a e m forem primos entre si (ex. se gcd(a, m) = 1). S o inverso multiplicativo modular de um módulo m existe, a operação da divisão por um módulo m pode ser definida multiplicando pelo inverso. Zero não tem inverso multiplicativo modular.
O inverso multiplicativo modular de um módulo m pode ser encontrado com o Algoritmo de Euclides estendido.
Para mostrar isso, vejamos esta equação:
Essa é uma equação diofantina linear com duas incógnitas, referente a Equações diofantinas lineares. Uma vez que um pode ser dividido sem sobra apenas por um, essa equação tem solução apenas se .
A solução pode ser encontrando com o algoritmo de Euclides estendido. A operação de módulo em ambas as partes da equação nos dá
Portanto, x é o inverso multiplicativo modular do módulo m.
Comentários