In Puzzle 73, we solved a Diophantine equation, an equation requiring an integral solution, and we used a standard method of solving a Diophantine equation of the form Px + Qy = T, where x and y are the variables and P, Q and T are integers. You can find one illustration of this method in the solution section of Puzzle 73. We shall now give some more illustrations of this method, specify as well as I can the general steps of the procedure, and discuss the possibility of a potentially simpler method.
Find all positive integers x and y that are solutions to equation (1) . In this particular case, we can simplify the equation by dividing all the coefficients by their greatest common factor, which gives us .
Solving for x in terms of y, we get (2) .
(3) Let . Solving for y in terms of A, we get (4) .
(5) Let . Solving for A in terms of B, we get (6) . (7) Let . Solving for B in terms of C, we get (8) . (9) Let . S0lving for C in terms of D, we get (10) . (11) Let . Solving for D in terms of E, we get (12) .
Applying equations (11) and (12) to equation (10) and simplifying, we get (13) . Applying equations (9), (12) and (13) to (8) and simplifying, we get (14) . Applying equations (7), (13) and (14) to (6) and simplifying, we get (15) . Applying equations (5), (14) and (15) to (4) and simplifying, we get (16) . Applying equations (3), (15) and (16) to (2) and simplifying, we get (17) .
So we now have parametric equations for x and y. E must be an integer for both x and y to be integers. For , . For , . Therefore, we can’t get both x and y to be positive simultaneously, so there are no solutions.
The method we have used, then, to solve an equation of the form, Px + Qy = T, is to derive parametric equations for x and y by using the algorithm:
- Isolate the variable having the lesser of the absolute values of the two numerical coefficients in the form, , minimizing the absolute values of the coefficients of the numerator.
- Assign a new variable to the fraction in step 1 and isolate with the same conditions as in step 1.
- Repeat step 2 to isolate the variable in the fraction until there is no fraction to which to assign a new variable.
- In the reverse of the order in which they were introduced, solve for each introduced variable and the original variables in terms of the last introduced variable, until you have parametric equations for the original variables in terms of the last introduced variable.
- Apply any other conditions given for the original variables.
But do we really have to go through all that to know there are no solutions? Can’t we just reason about the original equation or, in this case, to make it a little easier, about its equivalent, ? If , then , so . Since implies x is not an integer, there are no solutions.
Maybe the simplicity of this solution is due to there being no solutions in this case. How about equations that do have solutions? We’ll get to them next time.
TO BE CONTINUED