For ax % b = c, where a, b, and c are known, how do I find a compliant x? [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

From what I can tell, this is not the multiplicative invers开发者_StackOverflow中文版e 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.