I just asked this question on stackoverflow.com and had it closed before I could get any reasonable help, with the suggestion to move it to a math site. I don't understand the math, and don't speak the math speak, and need an algorithm, not simply math jargon for the answer.
With a, b, and c as known values, % being the typical computer modulus operator, and with a and b relatively prime, how do I compute a legitimate x? I know that x exists, that's how c came into being... I just need to solve for x.
Someone on stackoverflow pointed me to wikipedia on Linear Diophantine equations for a solution to ax + by = c where x and y are integers (which is almost a re-write of ax % b = c, I need ax - by = c), but I don't know what half this stuff means, or how to implement it in code.
"Let g be the greatest common divisor of a and b. Both terms in ax + by are divisible by g; therefore, c must also be divisible by g, or the equation has no solutions. By dividing both sides by c/g, the equation can be reduced to Bezout's identity sa + tb = g where s and t can be found by the extended Euclidean algorithm."
Ok, that's great in theory... but. How do I use such a thing to find s and t? And even further, how would I use s to find x?