Como usar congruência modular para encontrar soluções inteiras de uma equação linear diofantina ax+by=c?

Usando congruências para obter uma solução particular e parametrizar todas as soluções.

Explicação:
1) Verifique se gcd(a,b) | c. Se não, não há solução.
2) Reduza a equação módulo um dos coeficientes para obter uma congruência (por exemplo, módulo b): \(a x \equiv c \pmod b\).
3) Se \(\gcd(a,b)=1\), encontre o inverso de \(a\) módulo \(b\) para achar \(x\) numa classe: \(x\equiv a^{-1}c\pmod b\).
4) Escreva \(x=x_0+bk\) e substitua na equação original para obter \(y\) em função de \(k\). Isso gera todas as soluções inteiras.

Exemplo:
Resolver \(4x+7y=50\).
Reduzindo módulo 7: \(4x\equiv50\equiv1\pmod7\) (pois \(50-49=1\)).
O inverso de 4 módulo 7 é 2, porque \(4\cdot2\equiv1\pmod7\). Então \(x\equiv2\pmod7\), isto é \(x=2+7k\).
Substituindo: \(4(2+7k)+7y=50\Rightarrow 8+28k+7y=50\Rightarrow 7y=42-28k\Rightarrow y=6-4k\).
Portanto todas as soluções inteiras são \(x=2+7k,\;y=6-4k\) para \(k\in\mathbb{Z}\).
Exemplos numéricos: para \(k=0\) temos \(x=2,y=6\); para \(k=1\) temos \(x=9,y=2\).