Perhaps an augmented matrix view of a solution method to the problem may help shed light on Niven’s method. A motivation for the solution method is to express each original variable (x, y) as a function of one or more than one parameter variable (t0, t1, t2, …). In this expression, each original variable should be basic (i.e. its coefficient is 1 in only one and only one equation, and the coefficient of every other original variable in the equation is 0).
To find such an expression the linear equation may be manipulated algebraically – obeying the properties/theorems/laws regarding operations on the elements of Z, the Set of Integers. There are two types of manipulations: constraint generation and basis conversion. The constraint generation phase introduces parameter variables (t0, t1, t2, …) and the basis conversion phase transforms the original variables from non-basic variables into basic variables.
The constraint generation phase uses Theorem 1. Basis conversion uses back substitution.
Given ax + by = c and 1 < |a| < |b| then at + dy = e where b = a * t0 + d, c = a * t1 + e, d < a, e < a and a,b,c,d,e,x,y,t0,t1 are integers.
Let a be called the hinge coefficient. Let d and e be called remainders.
Termination of Theorem 1 Application
In general, the constraint generation phase ends in one of three situations:
- The remainders are d=1 and e is integer and non-zero. In this case there are integer solutions and they are found by proceeding to the second phase.
- The remainders are d=0 and e=0. In this case the original linear equation has a greatest common divisor found in the last application of Theorem 1; in other words, the greatest common factor is the hinge coefficient found in the most recent application of Theorem 1. The derived equations too have the same greatest common divisor. In this case, factor out the greatest common divisor from each of the original equation and derived equations. Then take the new system of equations and proceed to the second phase.
- The remainders are d=0 and e is integer and non-zero. The most recent derived equation is inconsistent. In this case there are no integer solutions.
Back Substitution Caveat
After each back substitution if there is a greatest common divisor greater than 1 then it should be removed before proceeding to the next back substitution step.
Solution by Augmented Matrix Format
Step-by-Step Explanation for the Augmented Matrix Format
For the example problem 147x + 258y = 369, Step 0 is given. The application of Theorem 1 to Step 0 is:
258 = 147*1 + 111
369 = 147*2 + 75
Based on this application, we arrive at Step 1. The application of Theorem 2 to Step 1 is:
147 = 111*1 + 36
75 = 111*0 + 75
Thus we arrive at Step 2. And so on. After arriving at Step 4 we discover that the original equation (Step 0) has a greatest common factor – it is true for the derived equations (Step 1 to Step 3). So before moving on, we remove the greatest common factor from all equations and arrive at Steps 5, 6, 7, and 8.
Step 9 is a copy of Step 5. Then we perform back substitution, Step 9 into Step 6 to get Step 10; then Step 10 into Step 7 to get Step 11; and Step 11 into Step 8 to get Step 12. Thus a solution is found in Step 11 and Step 12:
x = -1 + 86*t2
y = 2 – 49*t2
For more information, please see “How I found the multiplicative inverse …” (Chionglo, 2018).
Argolo, P. (2018). A doubt about Diophantine equations (Ivan Niven). Retrieved on May 29, 2018 from A doubt about Diophantine equations (Ivan Niven).
Chionglo, J. F. (2018). How I found the multiplicative inverse of 47 modulo 64: A reply to a question at Cryptography Stack Exchange. Available at https://www.academia.edu/33091938/How_I_found_the_multiplicative_inverse_of_47_modulo_64.