System of diophantine linear equation online

The coefficients of the first diophantine equation
The coefficients of the second diophantine equation

The system of two diophantine equations
First equation
Second equation
General decision matrix
General decision matrix
String result
Check for the first equation
Check for the first equation
Check for the second equation
Check for the second equation

 

An original algorithm for solving two arbitrary homogeneous linear equations in integers is considered. Automatic calculation of decision matrix.

Let us need to solve a system of two Diophantine equations

$$\begin{alignedat}{3}2&a-11&b+13&c=1\\62&a+22&b-73&c=-31\end{alignedat}$$

Undoubtedly, you can solve this system as they do everything.

- Multiplying the first equation by 31 and subtracting from the second we get the classical Diophantine equation with two variables.

- Having decided which one can find all integer values ​​of the system

The working scheme, despite a lot of manual calculations

I do not like this approach and we will use a different method for the solution.

It is beautiful and understandable even for students who know about vectors and matrices.

Partially used is the algorithm described here in this article (p. 36.37)

It is finalized, reduced to matrix operations and generalized to any values.

We will study the algorithm and its work using an example.

We solve the following system of diophantine equations

$$\begin{alignedat}{3}49&a+22&b-26&c=12\\70&a-31&b+9&c=9\end{alignedat}$$

We took this example for the reason that it was solved on the Internet and a general solution was developed for it. So there is something to compare.

1. We find the general solution of the first equation from a given system. For example, let it be

8 14 20 -19 -30 -44 -1 1 0

$$\begin{cases}a=8m+14p+20\\b=-19m-30p-44\\c=-m+p+0\end{cases}$$

How to verify that this is a true equality? Yes, just multiply the coefficient vector of the first equation by the resulting matrix

$$\begin{pmatrix}49&22&-26\\\end{pmatrix}*\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\\\end{pmatrix}=\begin{pmatrix}0&0&12\\\end{pmatrix}$$

As you can see, the answer coincides with the free term of the first equation.

2. Now, since we have found a general solution to the first equation, let's substitute it into the second.

That is, in the equation $$70a-31b+9c=9$$ substitute our values

$$\begin{cases}a=8m+14p+20\\b=-19m-30p-44\\c=-m+p+0\end{cases}$$

You can substitute and reduce this with your hands, but in matrix calculus we only multiply the vector {70, -31,9} by our matrix.

$$\begin{pmatrix}70&-31&9\\\end{pmatrix}*\begin{pmatrix}8&14&20\\-19&-30&-44\\-1&1&0\\\end{pmatrix}=\begin{pmatrix}1140&1919&2764\\\end{pmatrix}$$

That is, we got the equation

$$1140m+1919p+2764=0$$

But, note that in the second equation the free term is not zero, but nine.

That is, we rewrite

1140m + 1919p + 2764 = 9

We transfer the free terms to the right side and get the classical Diophantine equation, which we can solve easily.

1140m + 1919p = -2755

The general solution is

Variable M

Variable P

3. Now do the inverse transformation.

I.e

into this system general system solution

instead of unknowns, we substitute the found m and p.

In matrix calculus, this is solved as follows:

We remove from the matrix Decision matrix last column. These are free members and they are still bothering us.

got

Decision matrix

Multiply this matrix by the matrix created from these equations

Variable M

Variable P

Diophantine equation matrix

we get

Multiplication result

The last column is free members, add to it the column that was removed at the beginning of this paragraph

that is, to the vector {-22 36 -11} we add {20 -44 0}

We get the system

Multiplication result

Therefore, the general solution of the system of two diophantine equations

takes on the form

general system solution

Check if they counted correctly

For the first equation

 

Multiplication result

For the second

Multiplication result

As you can see, the values ​​of the free terms coincide with the values ​​on the right side of the equations, and therefore we got a general solution.

But it’s too early to rejoice, despite the fact that we got a general solution, we do not get all the possible values.

Why? Yes, because the vector {-608 -2261 -3059} has GCD = 19

and in fact our general solution is

general solution of the diophantine system

Since the numbers in brackets must be integers, we denote them by t and ours, already exactly the final general solution to the system of two Diophantine equations, has the form

general solution of the diophantine system

Some more examples, and small remarks to the algorithm.


2a-11b + 13c = 1 && 62a + 22b-73c = -31

answer

a = 517k + 748 \\ b = 952k + 1378 \\ c = 726k + 1051

another example

\ begin {array} {lcl} -a + 7b + c-53d + 13d = -100 \\ 2a + 4b-16c-37d-32d = 0 \ end {array}

answer

a = -116p-85m + 139q-117 // b = -14p + 5m + 0q + 1 // c = -18p-14m + 20q-1 // d = 0p + 2m-2q + 2 // e = 0p + 0m + q-9

As you can see, it is possible to solve unlimited in the number of variables diophantine equations.

Now that calculator cannot.

Very much does not like equations with zero coefficients. Especially the first. For example, such a system

the calculator will not solve.

Type of equation
Type of equation

Well, how does he not decide? Decides if we resort to the trick, and try to remove all zero coefficients

Add to the first equation, the second. Thus, in the first equation, all zero coefficients disappear and the calculator can solve this system

The system of two diophantine equations
Type of equation
Type of equation
General decision matrix
General decision matrix

Verification shows that the general solution is correct.

And another example

The system of two diophantine equations
Type of equation
Type of equation
General decision matrix
General decision matrix

Good luck with your calculations !!

 

Copyright © 2020 AbakBot-online calculators. All Right Reserved. Author by Dmitry Varlamov