Equação de Congruência Linear

Esta equação é da forma:

$$a \cdot x = b \pmod n,$$

onde $a$, $b$ e $n$ são inteiros conhecidos e $x$ é a variável.

É necessário encontrar o valor $x$ do intervalo $[0, n-1]$ (claramente, em toda a linha numérica, existem infinitas soluções que diferem entre si, em $n \cdot k$ , onde $k$ é qualquer inteiro). Se a solução não for única, consideraremos como obter todas as soluções.

Solução encontrando o Elemento Inverso

Vamos primeiro considerar um caso mais simples, onde $a$ e $n$ são coprimos ($\gcd(a, n) = 1$). Então, podemos encontrar o inverso de $a$ e, multiplicando ambos os lados da equação com o inverso, podemos obter uma solução única.

$$x = b \cdot a ^ {- 1} \pmod n$$

Agora considere o caso em que $a$ e $n$ são não-coprimos ($\gcd(a, n) \ne 1$). Então a solução nem sempre irá existir (por exemplo $2 \cdot x = 1 \pmod 4$ não tem solução).

Seja $g = \gcd(a, n)$, ou seja, o maior divisor comum de $a$ e $n$ (que, no caso, é maior que 1).

Então, se $b$ não for divisível por $g$, não há solução. De fato, para qualquer $x$, o lado esquerdo da equação $a \cdot x \pmod n$ , sempre é divisível por $g$, enquanto o lado direito não é, portanto, segue-se que não existem soluções.

Se $g$ divide $b$, então dividindo ambos os lados da equação por $g$ (ou seja, dividindo $a$, $b$ e $n$ por $g$), obtemos uma nova equação:

$$a^\prime \cdot x = b^\prime \pmod{n^\prime}$$

na qual $a^\prime$ e $n^\prime$ são coprimos, e já sabemos como lidar com essa equação. Nós temos $x^\prime$ como solução para $x$.

É claro que $x^\prime$ também será uma solução da equação original. No entanto, não será a única solução. Pode ser demonstrado que a equação original tem exatamente $g$ soluções, e elas serão da seguinte forma:

$$x_i = (x^\prime + i\cdot n^\prime) \pmod n \quad \text{for } i = 0 \ldots g-1$$

Resumindo, podemos dizer que o número de soluções da equação de congruência linear é igual a $g = \gcd(a, n)$ ou zero.

Solução com o algoritmo de Euclides Estendido

Podemos reescrever a congruência linear para a seguinte equação diofantina:

$$a \cdot x + n \cdot k = b,$$

onde $x$ e $k$ são inteiros conhecidos.

O método para resolver essa equação é descrito no artigo correspondente: equação diofantina linear e consiste em aplicar o algoritmo de Euclides estendido.

Ele também descreve o método de obter todas as soluções dessa equação a partir de uma solução encontrada e, aliás, esse método, quando cuidadosamente considerado, é absolutamente equivalente ao método descrito na seção anterior.