Como usar congruências para determinar x na equação linear ax + by = c?

Reduzindo módulo b, calcule o inverso de a mod b para obter \(x\equiv a^{-1}c\pmod b\); a solução geral é \(x=x_0+bk\) e \(y\) obtém-se por substituição.

Procedimento:
Reduza \(ax+by=c\) módulo \(b\), obtendo \(ax\equiv c\pmod b\).
Encontre o inverso de \(a\) módulo \(b\), tal que \(a\cdot a^{-1}\equiv1\pmod b\).
Calcule \(x\equiv a^{-1}c\pmod b\), escreva \(x=x_0+bk\) com \(k\in\mathbb{Z}\).
Substitua \(x\) na equação original para achar \(y\) em função de \(k\).

Exemplo:
Resolva \(7x-12y=5\).
Reduzindo módulo 12: \(7x\equiv5\pmod{12}\).
Como \(7\cdot7=49\equiv1\pmod{12}\), temos \(7^{-1}\equiv7\).
Logo \(x\equiv7\cdot5=35\equiv11\pmod{12}\), então \(x=11+12k\).
Substituindo: \(7(11+12k)-12y=5\Rightarrow77+84k-12y=5\Rightarrow84k-12y=-72\).
Dividindo por 12: \(7k-y=-6\Rightarrow y=7k+6\).
Tomando \(k=0\) obtém-se a solução natural \(x=11,\;y=6\), verifica-se \(7\cdot11-12\cdot6=77-72=5\).