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)
(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
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 (x1 , y1) is a solution of Ax + By = C
and (x0 , y0) 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 x1,y1 is a solution, than x = 575x1, y = 575y1 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 - q2r1 = r2
r1 - q3r2 = r3
r2 - q4r3 = r4
The process ends when r = 1, the gcd, because A and B had no common factors.
We may write the system of equations: (if r4 = 1)
r3 + q3r2 - r1 = 0
r2 + q2r1 - B = 0
r1 + q1B + - A = 0
written as a matrix multiplication:
After that, the matrix has the form:
Ax + By = 1
swaps and complements taken into account.
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.