Solução geral do algoritmo estendido de Euclides (exgcd) para equações ax + by = gcd(a, b)

O algoritmo estendido de Euclides permite encontrar não apenas o máximo divisor comum (mdc) de dois números inteiros, mas também os coeficientes inteiros x e y da equação linear ax + by = mdc(a, b). A seguir, exploramos a solução geral dessa equação.

/*
Conceito de solução geral
Em equações lineares com duas variáveis, quando temos apenas uma equação, existem infinitas soluções.
A solução geral é uma forma que permite expressar todas as soluções a partir de uma única solução particular.

Definido o conceito, vamos derivar as expressões.
Primeiramente, suponha que x, y seja uma solução para ax + by = mdc(a, b).
Então temos y = (mdc(a, b) - ax) / b (1), onde y, x, a, b são inteiros.

Considere outra solução x0 = x + k (2), com k e x0 inteiros.
Então a*x0 + b*y0 = mdc(a, b);
y0 = (mdc(a, b) - a*x0) / b (3)
Substituindo (2) em (3), obtemos:
y0 = (mdc(a, b) - ax - ak)/b <==> y0 = (mdc(a, b) - ax)/b - a/b * k (4)

Das equações (4) e (1), temos y0 = y - a/b * k (5)
Para garantir que y0 seja inteiro, e sabendo que y é inteiro, então a/b * k deve ser inteiro.
Seja d = mdc(a, b);
a = a' * d, b = b' * d, onde a' e b' são primos entre si (se não fossem primos, d poderia ser
aumentado pelo mdc de a' e b', contradizendo a definição de d como mdc).
Então a/b * k = a'/b' * k.
Como a' e b' são primos entre si, para a'/b' * k ser inteiro, k deve ser múltiplo de b' (quando k = 0, o resultado é 0, que também é inteiro).
Caso contrário, o denominador b' não seria completamente cancelado, resultando em um número não inteiro.
Portanto, k = n*b', onde n é um inteiro qualquer.
Como b' * d = b, temos b' = b / d, logo k = n*b/d.
Assim, x0 = x + n*b/d (6)
Combinando (5) e (6), obtemos y0 = y - n*a/d (7)

A solução geral é então:
x0 = x + n*b/d
y0 = y - n*a/d
Na notação mais comum:
x0 = x + k*b/d (onde k é um inteiro qualquer, não o mesmo k anterior)
y0 = y - k*a/d

A menor solução positiva inteira pode ser obtida com x % (b / d);
Considerando que x pode ser negativo, uma expressão mais precisa é:
(x % (b/d) + b/d) % (b/d)
Isso efetivamente remove todos os múltiplos de b/d, deixando a menor solução positiva.
*/

Exemplo prático: Resolvendo equações de congruência

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int n, m;

int exgcd(int a, int b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    LL x, y, d;
    cin >> n >> m;
    d = exgcd(n, m, x, y);
    cout << (x % m + m) % m << endl; // Como d=1 neste caso, não precisamos dividir
    return 0;
}

Informação comlpementar

Aqui está uma correção e explicação adicional:

A equação linear exgcd pode ser expandida para verificar a existência de soluções inteiras.
Embora soluções decimais sempre existam, precisamos de soluções inteiras que atendam aos nossos requisitos.
Sabemos que a equação ax + by = d, obtida via exgcd, sempre tem soluções inteiras.
No entanto, quando expandimos a equação por um fator não inteiro, isso pode não ser mais verdadeiro.
A expansão deve ser por um múltiplo inteiro. Por exemplo, expandir por 1/2 pode não funcionar.

Considere a equação 6x + 2y = 2, que tem soluções inteiras.
No entanto, 6*x0 + 2*y0 = 1 não tem soluções inteiras (onde x = 2*x0, y = 2*y0).

Para a equação ax + by = k, a condição para que existam soluções inteiras é que k seja um múltiplo inteiro de d:
k % d == 0, onde k = n * d.

A solução geral é dada por x = x0 + k*b/mdc(a, b), onde m = mdc(a, b), t = d / mdc(a, b).
Mesmo quando a equação é expandida, a forma geral da solução permanece válida, pois:
a(x*t + k*b/m) + b(y*t - k*a/m) = d
axt + byt + akb/m - bka/m = d
axt + byt = d

A equação original permanece inalterada, mostrando que a forma geral da solução continua aplicável.
Esta lógica pode ser estendida para outros casos similares.