Solving equations of the form ax + by = c has been around for a long time. The mathematician Diophantus of Alexandria (200-284 AD) gave a general solution for when problems of this type are solvable. Of course he was only interested in integer solutions, so when we say a problem like this is solvable, we mean that there exist integers x and y such that ax + by = c. Because Diophantus showed when these equations are solvable, they are today known as Diophantine equations. More specifically, they are linear Diophantine equations. In general, linear Diophantine equations are solvable if and only if the greatest common divisor of a and b divides c. So this answers part B in your question. If you try to find integers x and y such that 3x + 6y = 4, you'll have problems. Notice that gcd(3,6) = 3 and since 3 does not divide four, the problem has no solution. You're welcome to try to find a solution, but you'd be wasting your time. If the linear Diophantine equation is solvable, there is an infinite number of integer solutions. Here's how to solve them: You first need to know the Euclidean algorithm for determining the gcd of a and b. So let's do that. It's easiest to show an example of how it works: Let's say you want to find the gcd of 6 and 64. Proceed as follows (the idea is a generalization of the division algorithm): 64 = 10*6 + 4 6 = 1*4 + 2 4 = 2*2 + 0 When you get a zero in the "remainder" spot, you're done. The gcd is the previous remainder. So in this case, the gcd of 6 and 64 is two. Let's do another example: Find the gcd of 12 and 136. 136 = 11*12 + 4 12 = 3*4 + 0 so the gcd of 12 and 136 is 4. One of the things that Euclid showed is that you can express gcd(a,b) as a linear combination of a and b. That is, there always exist integers x and y such that ax + by = d, where d = gcd(a,b). This is getting closer to what we want, but we're not quite there yet. The way to find the integers x and y is to use the Euclidean algorithm (which you just did to find the gcd of a and b) in reverse. Let's go to 2 Solve for the gcd: 2 = 6 - 1*4 Now look at the next line up in your Euclidean algorithm: 64 = 10*6 + 4 Solve this for the remainder: 4 = 64 - 10*6. Now substitute this expression of the number four into the last line we had: 2 = 6 - 1*4 2 = 6 - 1*4 2 = 6 - 1*(64 - 10*6) 2 = 6 - 64 + 10*6 2 = 11*6 - 64 We have found the desired integers. So if we had been asked to find integers x and y such that 6x + 64y = 2, we could reply that x = 11 and y = -1 back to when we found the gcd of 6 and 64. We said that was 2. So that means we can find integers x and y such that 6x + 64y = 2. Let's find them. Here's how to do it. Start with the next to the last line in your Euclidean algorithm (the one that gave the gcd): 6 = 1*4 + 2 Solve for the gcd: 2 = 6 - 1*4 Now look at the next line up in your Euclidean algorithm: 64 = 10*6 + 4 Solve this for the remainder: 4 = 64 - 10*6. Now substitute this expression of the number four into the last line we had: 2 = 6 - 1*4 2 = 6 - 1*4 2 = 6 - 1*(64 - 10*6) 2 = 6 - 64 + 10*6 2 = 11*6 - 64 We have found the desired integers. So if we had been asked to find integers x and y such that 6x + 64y = 2, we could reply that x = 11 and y = -1. Let's do another example like this. Find integers x and y such that 12378x + 3054y = 6 Well, we first need to find gcd(12378,3054). It should be obvious at this point that gcd(12378,3054) = 6 because I haven't told you how to finish the problem if the right-hand side is not equal to gcd(a,b). We proceed to find gcd(12378,3054): 12378 = 4*3054 + 162 3054 = 18*162 + 138 162 = 1*138 + 24 138 = 5*24 + 18 24 = 1*18 + 6 18 = 3*6 + 0 So gcd(12378,3054) is indeed 6. Now write 6 as a linear combination of 12378 and 3054 by reversing the steps of the Euclidean algorithm that was used to find the gcd. 6 = 24 - 18 = 24 - (138 - 5*24) = 6*24 - 138 = 6(162-138) - 138 = 6*162 - 7*138 = 6*162 - 7(3054 - 18*162) = 132*162 - 7*3054 = 132(12378 - 4*3054) - 7*3054 = 132*12378 + (-535)*3054 Thus x = 132 and y = -535 The French mathematician Gabriel Lame (1795-1870) proved that the number of steps required in the Euclidean Algorithm is at most five times the number of digits in the smaller integer. In this example, the smaller integer (3054) has four digits, so the total number of divisions cannot be greater than 20; in fact, only six divisions were needed.