For ax % b = c, where a, b, and c are known, how do I find a compliant x? 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?
Thanks.
 A: Here it is as C-style code.
You can see the Euclidean algorithm at work: p and q get reduced while we simultaneously keep track of both p and q as linear combinations of a and b.  In the end this gives us exactly the numbers we need.  The comments should allow you to understand it enough to debug it in whatever your favorite language is.  The assert statements are basically asserting that c indeed comes from an a*x%b calculation with the given a and b.
I will assume a>=0 and b>0.
if (a == b) {
  assert(c==0);
  return 0; (* any value of x satisfies a*x % b == c in this case *)
}
int pa = 1, pb = 0, p = a, qa = 0, qb = 1, q = b; (* p always == pa*a+pb*b *)
while (p > 0 && q > 0) {
  if (q > p) { (* might be false on first pass, but then always true *)
    m = q / p;  (* integer arithmetic, assuming positive p,q *)
    q -= m * p;
    qa -= m * pa;
    qb -= m * pb;
  }
  if (q > 0) { (* q must be less than p *)
    m = p / q;
    p -= m * q;
    pa -= m * qa;
    pb -= m * qb;
  }
}
(* now one of p or q is zero, and the other is the gcd *)
assert(c % (p+q) == 0); (* c should be a multiple of the gcd, p+q *)
m = c / (p+q);
if (p > 0) (* p==pa*a+pb*b, and m*p==c, so c==m*pa*a+m*pb*b, so x=m*pa *)
  return pa > 0 ? m*pa % b : b - (m*-pa) % b;
else
  return qa > 0 ? m*qa % b : b - (m*-qa) % b;

A: Here, for example, is the extended Euclidean algorithm in Python. Apply that to your numbers $a$ and $b$, to get what they call $u_1$, $u_2$, $u_3$ corresponding to your $s$, $t$, $g$. Then $x=s \cdot (c/g)$ (where $c/g$ must be an integer since you knew that there was a solution).
