Here is how I think of problems of this type.
The relation ax≡b (mod c) is the same as the equation ax=b+cy where x,y∈Z. If I find the integer solutions to the equation, I would have found the integer solutions to the relation. One way to find integer solutions to the equation would be to introduce substitute variables.
Here is the crucial idea: the purpose for introducing substitute variables is to create a new system of equations so that when the system of equations were solved using substitution (I keep the coefficients integers during the substitution process), each of the original variables are expressed in terms of substitute variables. If this can be done, all I have to do is enumerate integer values for the substitute variables and I will get integer values for the original variables.
So as an example, given the equation ax-cy=b, first I factor out the greatest common divisor of a,c and b. Suppose〖 gcd〗(a,c)=1. Which variable do I begin with? I would choose the equation with the smallest coefficient that is greater than 1. This coefficient is the coefficient of the substitute variable in the new equation. The other coefficients of the new equation are the remainders of the other coefficients from the equation if you divide the other coefficients with the selected coefficient. I proceed to add substitute variables until the coefficient of the last substitute variable is 1. At this point, I perform substitution right away to convert the new system in upper-echelon form. Then I repeat the search for the smallest coefficient that is greater than 1 and continue. I stop when all of the coefficients in the original system are 1. If there are no integer solutions, I get an equation with a coefficient greater than 1 or less than 1, and a right-hand constant that is greater than 0 or less than 0.
I use matrices to manually perform all computations.