Como usar congruências para encontrar uma solução inteira não negativa da equação ax+by=N?

Resposta

Reduza módulo, resolva a congruência para uma variável, escolha o menor valor ≥0 que satisfaça e calcule a outra variável.

Procedimento:
Reduza \(ax+by=N\) módulo \(b\), obtendo \(ax\equiv N\pmod b\). Resolva essa congruência para \(x\), escolha o menor \(x\ge 0\) que satisfaça, então calcule \(y=(N-ax)/b\) e verifique \(y\in\mathbb{Z}_{\ge 0}\).

Exemplo:
Resolver \(7x+5y=83\).
Reduzindo módulo \(5\): \(7x\equiv83\pmod5\Rightarrow 2x\equiv3\pmod5\).
Como \(2^{-1}\equiv3\pmod5\), temos \(x\equiv3\cdot3\equiv4\pmod5\).
Escolhendo o menor \(x\ge0\), \(x=4\).
Então \(y=(83-7\cdot4)/5=(83-28)/5=55/5=11\).
Solução não negativa: \(x=4,\;y=11\).