Como usar congruências para restringir os valores de x na equação linear \(ax+by=c\) em números naturais?

Reduza a equação modulo b, obtenha \(ax\equiv c\pmod b\), determine a classe de resíduos de x, e então liste os x≥0 dessa classe que tornam \(y=(c-ax)/b\) inteiro e não negativo.

Explicação, reduza modulo \(b\) para eliminar \(y\), assim encontra-se uma condição sobre \(x\) em classes residuais, depois verifique as soluções não negativas plugando \(x\) na expressão de \(y\).

Exemplo: considere \(31=6x+5y\). Reduzindo modulo 5, \(6x\equiv x\equiv 31\equiv 1\pmod5\), logo \(x\equiv1\pmod5\). Os candidatos \(x\ge0\) são \(1,6,\dots\). Teste \(x=1\), obtemos \(y=(31-6)/5=5\ge0\), solução \((x,y)=(1,5)\). Teste \(x=6\), \(y=(31-36)/5<0\), rejeita-se. Assim a única solução em naturais é \((1,5)\).