 <p>This is not a very good question for StackOverflow; it's better for one of the math sites. But I'll answer it here anyways.</p> <p>You certainly can do better than brute force, as you are doing here. You should be able to compute the answer in a few microseconds.</p> <p>There exists a solution if and only if the <em>greatest common divisor</em> of (A, B, C, D) divides K evenly. That's the extended form of <em>Bézout's identity</em>.</p> <p>In order to determine (1) what the gcd is and (2) what the values for p, q, r, s are, you use the <em>Extended Euclidean Algorithm</em>, which you can read about here:</p> <p><a href="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm</a></p> <p>My advice is to first write a program that solves simple linear Diophantine equations of the form <code>ax + by = c</code>. Once you've done that, then read the section of that Wikipedia article called "The case of more than two numbers", which describes how to extend the algorithm to handle your case.</p>