Solving linear diophantine equations with any number of unknowns.

Hello, dear readers! Continuing a series of amateurish articles on mathematics.

• First part
• The second part of

Today I propose to reflect on some interesting mathematical problem.
Namely, let's solve the following linear equation for warm-up:

$$

$$5a + 8b + 3c + 2d = 17$$

“What is difficult?” - you ask. Indeed, only one equation and as many as four unknowns. Consequently, three variables are free, and the latter depends on these. So let's express it soon! For example, through the variable $$$a$ , then the set of solutions is as follows:

$$

$$\ begin {cases} \ displaystyle {a = \ frac {17-8b-3c-2d} {5} \\ b, c, d \ in \ mathbb {R}} \ end {cases}$$

Where $$$\ mathbb {R}$ - the set of any real numbers.

Well, the solution really turned out to be too trivial. Then we will complicate our task and make it more interesting.
')
Recall the linear equations with integer coefficients and integer roots , which, in fact, are a kind of Diophantine equations . Specifically, we impose on our equation a corresponding restriction on the integer coefficients and roots. Odds for unknowns are integers ( $$$5; eight; 3; 2; $ 1$ ), but the unknowns themselves must be limited to the following:

$$

$$a, b, c, d \ in \ mathbb {Z}$$

Where $$$\ mathbb {Z}$ - set of integers.

Now, the solution obtained at the beginning of the article “does not go away”, since we risk getting $$$a$ as a rational (fractional) number. So how to solve this equation exclusively in integers?

Interested in the decision of the given problem I ask under kat.

And we continue. Let's try to make some elementary transformations of the desired equation:

$$

$$5a + 8b + 3c + 2d = 17 \\ \ Leftrightarrow 5a + 8b + 2 (c + d) + c = 17$$

The task still looks incomprehensible; in such cases, mathematicians usually make some kind of replacement. Let us and her bahney with you:

$$

$$c + d = t \ Rightarrow \\ 5a + 8b + 2 (c + d) + c = 17 \ Leftrightarrow 5a + 8b + 2t + c = $ 1$$

Oops, we have achieved an interesting result! Coefficient of $$$c$ we are now equal to one , which means that you and I can express this unknown through the remaining unknowns in this equation without any divisions (which we sinned at the very beginning of the article). Let's do it:

$$

$$5a + 8b + 2t + c = 17 \ Leftrightarrow c = 17-5a-8b-2t$$

Let me note that this tells us that whatever $$$a, b, t$ (within the framework of Diophantine equations), anyway $$$c$ will remain an integer, and that's fine.

Remembering that $$$c + d = t$ fair to say that $$$d = t-c$ . And substituting instead $$$c$ the result obtained above will be obtained:

$$

$$d = t-c = t- (17-5a-8b-2t) = 3t + 5a + 8b-17$$

Here we also see that what would not be $$$a, b, t$ , does not matter $$$d$ will remain an integer, and it is still beautiful.

Then a brilliant idea comes to mind: so let's $$$a, b, t$ declare as free variables, and $$$c, d$ will express through them! In fact, we have already done it. It remains only to record the answer in the system solutions:

$$

$$\ begin {cases} \ displaystyle {a, b, t \ in \ mathbb {Z} \\ c = 17-5a-8b-2t \\ d = 3t + 5a + 8b-17} \ end {cases}$$

Now it is possible to contemplate that there is no division anywhere in the system of solutions, which means that decisions will always be integers. Let's try to find a particular solution to the original equation, for example, putting $$$a = 1; b = 2; t = 3$ :

$$

$$\ begin {cases} \ displaystyle {a = 1 \\ b = 2 \\ t = 3 \\ c = 17-5 \ cdot1-8 \ cdot2-2 \ cdot3 = -10 \\ d = 3 \ cdot3 + 5 \ cdot1 + 8 \ cdot2-17 = 13} \ end {cases}$$

Substitute in the original equation:

$$

$$5 \ cdot1 + 8 \ cdot2 + 3 \ cdot (-10) +2 \ cdot13 = 17 \ Leftrightarrow 17 = 17$$

Identical, cool! Let's try one more time on another example?

$$

$$3a + 7b-11c = 1$$

Here we see a negative coefficient, it can give us a lot of problems, so let's get rid of sin by replacing it $$$c '= - c$ , then the equation will be as follows:

$$

$$3a + 7b + 11c '= 1$$

As we remember, our task is to make such transformations so that in our equation there is an unknown with a unit coefficient for it (to then express it through the others without any division). To do this, we must again take something out of the box, the fastest is to take the coefficients from the equation that are closest to one. However, you need to understand that you can take only the number that necessarily is some coefficient of the equation (no more, no less), otherwise we run into a tautology / contradiction or fractions (in other words, it is impossible for free variables to appear somewhere except in the last replacement). So:

$$

$$3a + 7b + 11c '= 1 \ Leftrightarrow 3 (a + b) + 4b + 11c' = 1$$

We introduce a replacement $$$a + b = t_1$ , then we get:

$$

$$3 (a + b) + 4b + 11c '= 1 \ Leftrightarrow 3t_1 + 4b + 11c' = 1$$

Again, we take the bracket and finally we get in the equation the unknown with the unit coefficient:

$$

$$3t_1 + 4b + 11c '= 1 \ Leftrightarrow 3 (t_1 + b) + b + 11c' = 1$$

We introduce a replacement $$$t_1 + b = t_2$ , then:

$$

$$3 (t_1 + b) + b + 11c '= 1 \ Leftrightarrow 3t_2 + b + 11c' = 1$$

Express from here our lonely unknown $$$b$ :

$$

$$3t_2 + b + 11c '= 1 \ Leftrightarrow b = 1-11c'-3t_2$$

From this it follows that whatever $$$c ', t_2$ we didn't take $$$b$ still be an integer. Then we find $$$t_1$ from the ratio $$$t_1 + b = t_2$ :

$$

$$t_1 + b = t_2 \ Leftrightarrow t_1 = t_2-b = t_2- (1-11c'-3t_2) \\ \ Leftrightarrow t_1 = 4t_2 + 11c'-1$$

Similarly, we find $$$a$ from the ratio $$$a + b = t_1$ :

$$

$$a + b = t_1 \ Leftrightarrow a = t_1-b = 4t_2 + 11c'-1 - (1-11c'-3t_2) \\ \ Leftrightarrow a = 7t_2 + 22c'-2$$

This is where our decision system has matured - we have expressed absolutely all unknowns, without resorting to division, thereby showing that the solution will definitely be integer. Also do not forget that $$$c '= - c$ , and we need to introduce a reverse replacement. Then the final decision system is as follows:

$$

$$\ begin {cases} \ displaystyle {a = 7t_2-22c-2 \\ b = -3t_2 + 11c + 1 \\ c, t_2 \ in \ mathbb {Z}} \ end {cases}$$

Thus, it remains to answer the question - is it possible to solve any such equation? The answer is no, if the equation is in principle unsolvable. This occurs in those cases where the free member is not divided completely into the GCD of all coefficients with unknowns. In other words, having the equation:

$$

$$a_1b_1 + a_2b_2 + .. + a_nb_n = N$$

To solve it in integers, the following condition is sufficient:

$$

$$N \ mod GCD (a_1, a_2, .., a_n) = 0$$

(Where $$$GCD$ - the greatest common divisor ).


Summarizing the above, we will write out an action algorithm for solving linear Diophantine equations with any number of unknowns:

1. We check if the equation can be solved at all (using the above described property $$$N \ mod GCD (a_1, a_2, .., a_n) = 0$ ). If the answer is yes, go to the next item.
2. To speed up the process, we divide all coefficients (including the free term) into their $$$GCD$ .
3. We get rid of negative coefficients in the equation by replacing $$$a'_n = -a_n$
4. We carry out a series of substitutions (breaking up some terms of the equation into sums and combining them into brackets) so that in the end one of the terms of the equation has unit coefficients, and we can derive it without any division. Remembering that only one number can be taken as a bracket, which is necessarily some coefficient of the equation (no more, no less), otherwise we run into a tautology / contradiction or fractions (in other words, it is impossible for free variables to appear somewhere except as in the last replacement). Finally, we declare all the variables through which it is expressed as free.
5. We deduce the rest of the variables through the above (we deduce from all our replacements), not forgetting also about reverse replacements.
6. We combine everything into a single solution system.

In conclusion, it should be said that it is also possible to add restrictions on each term of the equation in the form of inequality on it (then the system of inequalities is added to the system of solutions, according to which you will need to correct the answer), and also add something interesting. Another thing to keep in mind is that the solution algorithm is strict and can be recorded in the form of a computer program.

Peter was with you
Thanks for attention.