For ax % b = c, where a, b, and c are known, how do I find a compliant x?
From what I can tell, this is *not* the multiplicative inverse of modulo (which is what I keep finding with google searches), since x is the unknown.  b and a are relatively prime, and % is the modulus operator used in most programming languages.  Using a for loop to find matches could take up to 4 billion iterations to find the matching value of x.  I know there is more than one value for x which solves this equation... I need the smallest that is greater than 0.

I know this could be re-written as ax - by = c where both x and y are unknown, but I don't know how to solve this equation for a matching x where both x and y are integers.  I keep running into Euclid's solution for gcd(m, n) = 1 in conjunction to this problem, but although I can implement this algorithm, I don't know how to use the results to solve my problem.

Although this appears to be a math question, it is in the domain of "computer" math and algorithms instead of the theoretical I keep finding with google searches.  I'm hoping for a simple algorithm, equation, or built-in math call if possible - sample code would be awesome.

Thanks.
For ax % b = c, where a, b, and c are known, how do I find a compliant x?
===

From what I can tell, this is *not* the multiplicative inverse of modulo (which is what I keep finding with google searches), since x is the unknown.  b and a are relatively prime, and % is the modulus operator used in most programming languages.  Using a for loop to find matches could take up to 4 billion iterations to find the matching value of x.  I know there is more than one value for x which solves this equation... I need the smallest that is greater than 0.

I know this could be re-written as ax - by = c where both x and y are unknown, but I don't know how to solve this equation for a matching x where both x and y are integers.  I keep running into Euclid's solution for gcd(m, n) = 1 in conjunction to this problem, but although I can implement this algorithm, I don't know how to use the results to solve my problem.

Although this appears to be a math question, it is in the domain of "computer" math and algorithms instead of the theoretical I keep finding with google searches.  I'm hoping for a simple algorithm, equation, or built-in math call if possible - sample code would be awesome.

Thanks.