Introduction This article describes how my program "Euclid" solves x,y in the equation Ax + By = C, for integers A,B,C,x,y. These type of equations arise from puzzles like this:
John: 40% of the cars is for you. Of the remaining 60%, grant 5 of your choice to a museum. Helen: 40% of the remaining cars is for you. After your choice, grant 3 of the remaining cars to a museum. Emily: 40% of the remaining cars is for you. After your choice, grant 1 car to a museum. Roderick : the remaining cars are yours. Say, the collection counts x vehicles, then:
216x - 1000y = 4600 The core of solving such equations is the use of the Euclidean Algorithm. So, first this algorithm is discussed. After that, we will see how the algorithm is applied to obtain the desired results. The Euclidean Algorithm A somewhat free interpretation of the Euclidean algorithm is:
gcd(14,7) = gcd(7,7) = 7. A proof can be constructed of 2 sub-proofs:
A = ad and B = bd then: A - B = ad - bd = d(a - b) and (A - B)/d = a - b which is an integer. So (A - B) must have a factor d.
A does not have a factor d. B has a factor d and B = bd we must proof: gcd(A-B,B) = d is impossible assume: A - B has a factor d, then A - B = A - bd = kd, where k is some integer dividing by d : A/d - b = k A/d = k + b b and k are integers, A/d is a fraction so this is impossible. A - B can never have a factor d. if A > B then repeatative application yields:
B is subtracted from A until A - kB < B. where A > B , A,B are positive and have no common factors. from these results, solutions of the original equation will be calculated. Standardizing the equation Back to the original equation 216x - 1000y = 4600 216, 1000 and 4600 have a common factor 8. Dividing by 8 simplifies the equation to:
If A,B,C have a common factor, A,B and C can be divided by this factor to simplify the equation. So, from this point, we assume that A,B and C have no common factors. If just A and B have a common factor, say d, and A = ad, B = bd, then
ax + by = C/d C/d will be a fraction but (ax + by) is integer. Conclusion: there is no solution in this case. Hereafter we assume, that A and B have no common factors, so gcd(A,B) = 1. Also, we expect in Ax + By =C that
27x - 125y = 575 is therefore transformed to 27x + 125y = 575, (remember to complement y later) and to 125x + 27y = 575, remember to swap x and y later. If C = 0 then Ax + By = 0 has the solutions:
Say (x_{1} , y_{1}) is a solution of Ax + By = C and (x_{0} , y_{0}) is a solution of Ax + By = 0 then combining
where k is some integer ...-2,-1,0,1,2,3....... Conclusion: Ax + By = C has no solution or an infinite number of solutions. Handling very big numbers Back to 125x + 27y = 575 To solve this equation, first 125x + 27y = 1 must be solved. If x_{1},y_{1} is a solution, than x = 575x_{1}, y = 575y_{1} is the result we want. This approach is not advisable because x and y may become very large, even exceding the range of integers thus limiting the amount of equations we are able to solve. Therefore is it better to keep the value of C as close to zero as possible. This can be done by subtracting(adding) A+B,A,B or (A-B) to C and introducing correction numbers to x and y. Instead of solving Ax + By = C we solve
after that subtract A from C, incrementing xcorr, then subtract B from C, and finally subtract (A-B) from C while incrementing xcorr, decrementing ycorr. In this way the smallest value of C is obtained. Look at 125x + 27y = 575 again. 27 + 125 = 152, so 125(x-3) + 27(y-3) = 575 - 3*152 = 119 remembering xcorr = 3, ycorr = 3 we solve 125x+ 27y = 119 Next subtracting 4*27 from 119: ycorr = 3+4 = 7 and we solve 125x + 27y = 119 - 4*27 = 11. As a last step, using the Euclidean algorithm, we solve 125x + 27y = 1 and multiply the answer by 11 to find interim values for x,y. Hereafter, for the final answer, correction numbers, swaps and complements along the route have to be remembered. Solving Ax + By = 1 Using the Euclidean algorithm, we calculate gcd(A,B).
B - q_{2}r_{1} = r_{2} r_{1} - q_{3}r_{2} = r_{3} r_{2} - q_{4}r_{3} = r_{4} The process ends when r = 1, the gcd, because A and B had no common factors. We may write the system of equations: (if r_{4} = 1) By applying elementary rules we can sweep columns 2,3,4 to zero. After that, the vector product results:
Ax + By = 1 swaps and complements taken into account. The original problem: This concludes the description. Below, I present the kernel of the program "Euclid", where Ax + By = 1 is solved.
Interested in the source code? Click [here] to download the complete Delphi-3 project. |
||||||||||||||||||||||||||||||||||||