Na aritmética modular, não temos uma operação de divisão. No entanto, temos inversos modulares. Um inverso multiplicativo modular de um número inteiro $a$ é um número inteiro $x$ de modo que $a \cdot x$ é igual a $1$ sob o módulo de algum número $m$. Para escrevê-lo de maneira formal: queremos encontrar um número inteiro $x$ no qual $$a \cdot x \equiv 1 \mod m.$$ Nota: $mod$ = % e $gcd$ = $mdc$. Também denotaremos $x$ como $a^{-1}$.
Devemos notar que o inverso modular nem sempre existe. Por exemplo, seja $m = 4$, $a = 2$. Ao verificar todos os valores possíveis com módulo $m$ deve ficar claro que é possível não encontrar $a^{-1}$ satisfazendo a equação acima. Pode-se provar que o inverso modular existe se, e somente se, $a$ e $m$ são primos entre si (ou seja, coprimos, o máximo divisor comum entre os dois é 1 ($\gcd/mdc(a, m) = 1$)).
Neste artigo, apresentamos dois métodos para encontrar o inverso modular, caso exista, e um método para encontrar o inverso modular para todos os números em tempo linear.
Considere a seguinte equação (com $x$ e $y$ desconhecidos):
$$a \cdot x + m \cdot y = 1$$
Esta é uma equação diofantina linear com duas variáveis. Quando o $\ mdc(a, m) = 1$, a equação tem uma solução que pode ser encontrada usando o algoritmo de Euclides Estendido. O $\ gcd/mdc(a, m) = 1$ também é a condição para o inverso modular existir.
Agora, se usarmos o módulo $m$ de ambos os lados, podemos nos livrar de $m \cdot y$, e a equação se tornará:
$$a \cdot x \equiv 1 \mod m$$
Assim, o inverso modular de $a$ é $x$.
Implementação:
int x, y;
int g = euclides(a, m, x, y); //algoritmo de euclides estendido
if (g != 1) {
cout << "Sem solução!";
}
else {
x = (x % m + m) % m;
cout << x << endl;
}
Observe que nós modificamos x.
O x resultante do algoritmo de Euclides pode ser negativo, portanto, x % m também pode ser negativo, precisamos adicionar m primeiro para torná-lo positivo.
Outro método para encontrar o inverso modular é usar o teorema de Euler, no qual afirma que a seguinte congruência é verdadeira se $a$ e $m$ forem coprimos:
$$a^{\phi (m)} \equiv 1 \mod m$$
$\phi$ é a função totiente de Euler. Novamente, observe que $a$ e $m$ serem coprimos também é a condição para o inverso modular existir.
Se $m$ é um número primo, isso simplifica o pequeno teorema de Fermat:
$$a^{m - 1} \equiv 1 \mod m$$
Multiplique ambos os lados das equações acima por $a^{-1}$, e obtemos:
A partir desses resultados, podemos encontrar o inverso modular usando o algoritmo da exponenciação binária, que funciona em tempo $O(\log m)$.
Embora esse método seja mais fácil de entender do que o descrito no parágrafo anterior, no caso em que $m$ não seja um número primo, precisamos calcular a função de Euler, no qual envolve a fatoração de $m$, o que pode ser bem difícil. Se a fatoração de $m$ é conhecida, então a complexidade desse método é $O(\log m)$.
O problema é: queremos calcular o inverso modular para cada número no intervalo $[1, m-1]$.
Aplicando os algoritmos descritos nas seções anteriores, podemos obter uma solução com complexidade $O(m \log m)$.
Aqui apresentamos um algoritmo melhor com complexidade $O(m)$. No entanto, para este algoritmo específico, é requerido que o módulo $m$ seja primo.
Denotamos como $\text{inv}[i]$ o inverso modular de $i$. Assim, para $i > 1$ a equação seguinte é válida:
$$\text{inv}[i] = - \left\lfloor \frac{m}{i} \right\rfloor \cdot \text{inv}[m \bmod i] \bmod m$$
Portanto, a implementação é:
inv[1] = 1;
for(int i = 2; i < m; ++i)
inv[i] = (m - (m/i) * inv[m%i] % m) % m;
Nós temos: $$m \bmod i = m - \left\lfloor \frac{m}{i} \right\rfloor \cdot i$$ Tirando o módulo $m$ de ambos os lados, teremos: $$m \bmod i \equiv - \left\lfloor \frac{m}{i} \right\rfloor \cdot i \mod m$$ Multiplicando ambos os lados por $i^{-1} \cdot (m \bmod i)^{-1}$, temos: $$(m \bmod i) \cdot i^{-1} \cdot (m \bmod i)^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot i \cdot i^{-1} \cdot (m \bmod i)^{-1} \mod m,$$ simplificando: $$i^{-1} \equiv -\left\lfloor \frac{m}{i} \right\rfloor \cdot (m \bmod i)^{-1} \mod m,$$