A doubt about Diophantine equations (Ivan Niven)

Question

I'm trying to justify why the method presented by Ivan Niven (and co-authors) to solve linear diophantine equations actually works. I refer to the device that uses identity matrix, presented on page 218, of the fifth edition of the book An Introduction to The Theory of Numbers.

Given the diophantine equation ax + by = c, the table is formed:

  a b c

  1 0

  0 1

The following three operations can be used on the first two columns:

(C1) Add an integral multiple of one of the first two columns to the other;

(C2) Exchange the first two columns;

(C3) Multiply all elements of one of the first two columns by -1.

The process terminates when a value of zero is obtained in the position initially occupied by a or b.

For example, given the equation 147x + 258y = 369, we finally arrive at:

0 3 369

86 -7

-49 4

From the first line, we take 3v = 369, that is: v = 123.

From the second line: x = 86 u - 7v, that is: x = 86u -861

of the third line: y = -49u + 4v, that is: y = -49u + 492

I ask for help.

Answer 1

First look at what happens just to $a$ and $b$ in this process. You will find that it is simply the Euclidean algorithm, in a sort of pedestrian manner, where instead of writing $$a=bQ+R$$ you say "let's multiply $b$ by $-1$ and then add the result $Q$ times to $a$, so as to get $a+Q(-b)=R$ instead of $a$.

The couple $a,b$ is replaced by $R,b$ and you keep going, until one of the numbers in that row is zero, that is when you reach a zero remainder, which means that the other number, $3$ in your example, is going to be $\gcd(a,b)$. If you ever have solved linear Diophantine equations with one or another method this should ring a bell.

Now what about the second and last rows?

The array that you gave is the skeleton of the following equation (which is the one you want to solve!): $$\left(\matrix{a&b\\1&0\\0&1}\right)\left(\matrix{x\\y}\right)=\left(\matrix{c\\x\\y}\right)$$

The second and last rows look stupid right now. But they are going to keep track of the change of variables that you make when you perform column operations.

If, say, you need to subtract the second column twice from the first. This corresponds to multiplying the matrix $\left(\matrix{a&b\\1&0\\0&1}\right)$ by $\left(\matrix{1&0\\-2&1}\right)$. The original equation is equivalent to $$\underbrace{\left(\matrix{a&b\\1&0\\0&1}\right)\left(\matrix{1&0\\-2&1}\right)}_{\text{Your new $3\times 2$ matrix}}\underbrace{\left(\matrix{1&0\\2&1}\right)\left(\matrix{x\\y}\right)}_{\text{Your new variable vector}\\\text{call it $\left(\matrix{u\\v}\right)$} }=\left(\matrix{c\\x\\y}\right)$$

• Every time you make a new operation on the columns, what happens is you insert a couple of column-operation-matrices that are inverse to each other, one of them changes the matrix, the other one changes the variables.
• At each step, the equation is equivalent to the original one.
• In the end, the variables are some $\left(\matrix{u\\v}\right)$ and the bottom $2\times 2$ square of the $3\times 2$ matrix is the inverse change of variable, that is, how to get $x$ and $y$ back from $u$ and $v$.

The exact same process is going on in a recent answer that I gave on how to compute quotients of finite abelian groups.

Answer 2

The gcd outcome is 3, with $$ 258 \cdot 4 - 147 \cdot 7 = 3 $$ or $$ 147 \cdot (-7) + 258 \cdot 4 = 3. $$ Next, $3 \cdot 123 = 369,$ so $$ 147 \cdot (-861) + 258 \cdot 492 = 369. $$ If you want positive entries (or nearly so) you can add a multiple of $\frac{258}{3} = 86$ to -861 while subtracting the same multiple of $\frac{147}{3} = 49$ from 492. One step at a time: $$ 147 \cdot (-775) + 258 \cdot 443 = 369. $$ $$ 147 \cdot (-689) + 258 \cdot 394 = 369. $$ $$ 147 \cdot (-603) + 258 \cdot 345 = 369. $$ $$ 147 \cdot (-517) + 258 \cdot 296 = 369. $$ $$ 147 \cdot (-431) + 258 \cdot 247 = 369. $$ $$ 147 \cdot (-345) + 258 \cdot 198 = 369. $$ $$ 147 \cdot (-259) + 258 \cdot 149 = 369. $$ $$ 147 \cdot (-173) + 258 \cdot 100 = 369. $$ $$ 147 \cdot (-87) + 258 \cdot 51 = 369. $$ $$ 147 \cdot (-1) + 258 \cdot 2 = 369. $$ $$ 147 \cdot 85 + 258 \cdot (-47) = 369. $$ $$ 147 \cdot 171 + 258 \cdot (-96) = 369. $$ Alright, cannot quite get both positive.

============================

$$ \gcd( 258, 147 ) = ??? $$

$$ \frac{ 258 }{ 147 } = 1 + \frac{ 111 }{ 147 } $$ $$ \frac{ 147 }{ 111 } = 1 + \frac{ 36 }{ 111 } $$ $$ \frac{ 111 }{ 36 } = 3 + \frac{ 3 }{ 36 } $$ $$ \frac{ 36 }{ 3 } = 12 + \frac{ 0 }{ 3 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 1 & & 1 & & 3 & & 12 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 7 }{ 4 } & & \frac{ 86 }{ 49 } \end{array} $$ $$ $$ $$ 86 \cdot 4 - 49 \cdot 7 = 1 $$

$$ \gcd( 258, 147 ) = 3 $$
$$ 258 \cdot 4 - 147 \cdot 7 = 3 $$

Answer 3

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.

Theorem 1

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.

Definition

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:

1. 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.
2. 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.
3. 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).

References

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.