Solving linear diophantine equations with any number of unknowns

    image

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


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

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


    “What's so complicated?” You ask. Indeed, only one equation and as many as four unknowns. Therefore, three variables are free, and the latter depends on them. So let's express it soon! For example, through a variablea , then the set of solutions is as follows:

    { a = 17 - 8 b - 3 c - 2 dfiveb , c , d R


    Where R is the set of any real numbers.

    Well, the decision really turned out to be too trivial. Then we will complicate our task and make it more interesting.

    Let us recalllinear equations with integer coefficients and integer roots, which, in fact, are a variety ofDiophantine equations. Specifically, we impose on our equation the corresponding restriction on the integer number of coefficients and roots. The coefficients for unknowns are already integer (5 ; 8 ; 3 ; 2 ; 17 ), but the unknowns themselves must be limited to the following:

    a , b , c , d Z


    Where Z is the set of integers.

    Now, the solution obtained at the beginning of the article “does not fail”, since we run the risk of gettinga as a rational (fractional) number. So how to solve this equationexclusivelyin integers?

    Those interested in solving this problem, I ask for cat.

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

    5 a + 8 b + 3 c + 2 d = 175 a + 8 b + 2 ( c + d ) + c = 17


    The task still seems incomprehensible, in such cases, mathematicians usually make some kind of replacement. Let us and you weed her:

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


    Oh, we have achieved an interesting result! Coefficient forc we nowequal to unity, which means that you and I can express this unknown through the rest of the unknowns in this equation without any division (which we sinned at the very beginning of the article). Let's do it:

    5 a + 8 b + 2 t + c = 17 c = 17 - 5 a - 8 b - 2 t


    I’ll pay attention that this tells us that whatever a , b , t (in the framework of diophantine equations), anywayc will remain an integer, and that's fine.

    Remembering thatc + d = t it is fair to say thatd = t - c . And substituting insteadc we get the result obtained above:

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


    Here we also see that no matter what a , b , t , anywayd will remain an integer, and that is still beautiful.

    Then a brilliant idea comes to mind: so let'sa , b , t will be declared as free variables, andc , d we will express through them! In fact, we have already done this. It remains only to write down the answer in the decision system:

    { a , b , t Zc = 17 - 5 a - 8 b - 2 td = 3 t + 5 a + 8 b - 17


    Now you can see that in the system of solutions there is no division anywhere , which means that solutions will always be integer. Let's try to find a particular solution to the original equation, putting, for example, thata = 1 ; b is 2 ; t = 3 :

    { a = 1b = 2t = 3c = 17 - 5 1 - 8 2 - 2 3 = - 10d = 3 3 + 5 1 + 8 2 - 17 = 13


    Substitute in the original equation:

    5 1 + 8 2 + 3 ( - 10 ) + 2 13 = 17 17 = 17


    Identically cool! Let's try again with another example?

    3 a + 7 b - 11 c = 1


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

    3 a + 7 b + 11 c = 1


    As we recall, our task is to make such transformations so that the unknown appears in our equation with a unit coefficient in 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 unity. However, you need to understand that you can take only the number that is necessarily some coefficient of the equation (neither more nor less), otherwise we will come across a tautology / contradiction or fractions (in other words, it is impossible for free variables to appear somewhere except in the last replacement). So:

    3 a + 7 b + 11 c = 1 3 ( a + b ) + 4 b + 11 c = 1


    We introduce the replacement a + b = t 1 , then we get:

    3 ( a + b ) + 4 b + 11 c = 1 3 t 1 + 4 b + 11 c = 1


    Again, take it as a bracket and finally get the unknown in the equation with a unit coefficient:

    3 t 1 + 4 b + 11 c = 1 3 ( t 1 + b ) + b + 11 c = 1


    We introduce the replacement t 1 + b = t 2 , then:

    3 ( t 1 + b ) + b + 11 c = 1 3 t 2 + b + 11 c = 1


    We express from here our lonely unknown b :

    3 t 2 + b + 11 c = 1 b = 1 - 11 c - 3 t 2


    It follows that whatever c , t 2 we did not take,b will remain an integer anyway. Then we findt 1 from the relationt 1 + b = t 2 :

    t 1 + b = t 2t 1 = t 2 - b = t 2 - ( 1 - 11 s - 3 t 2 )t 1 = 4 t 2 + 11 s - 1


    Similarly, we find a from the relationa + b = t 1 :

    a + b = t 1a = t 1 - b = 4 t 2 + 11 c - 1 - ( 1 - 11 c - 3 t 2 )a = 7 t 2 + 22 s - 2


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

    { a = 7 t 2 - 22 s - 2b = - 3 t 2 + 11 c + 1c , t 2Z



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

    a 1 b 1 + a 2 b 2 + . . + a n b n = N


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


    (Where Is the largest common factor ).
    Evidence
    Доказательство в рамках этой статьи не рассматривается, так как это повод для отдельной статьи. Увидеть его вы можете, например, в чудесной книге В. Серпинского «О решении уравнений в целых числах» в §2.


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

    1. Check if the equation is solvable at all (by the above property ) If the answer is yes, go to the next step.
    2. To speed up the process, we divide all the coefficients (including the free term) into their .
    3. We get rid of negative coefficients in the equation by replacing
    4. We carry out a series of replacements (breaking apart some of the terms of the equation into sums and combining them in brackets) so that in the end one of the terms of the equation is with unit coefficients, and we can derive it without any division. Remembering that only the number that is necessarily some coefficient of the equation (neither more nor less) can be taken as a bracket, otherwise we will come across a tautology / contradiction or fractions (in other words, it is impossible for free variables to appear somewhere other than as in the last replacement). Finally, we declare all the variables through which it is expressed as free.
    5. We deduce the remaining variables through the above (we deduce from all our substitutions), without forgetting also about the reverse substitutions.
    6. We unite everything in a single system of solutions.

    In conclusion, it is worth saying that it is also possible to add restrictions on each term of the equation in the form of inequality on it (then a system of inequalities is added to the solution system, according to which it will be necessary to adjust the answer), and also add something else interesting. Do not forget about the fact that the decision algorithm is strict and can be written in the form of a computer program.

    Peter was with you,
    thank you for your attention.

    Also popular now: