| Ax+By+....Cw+Ez=F |
| Diophantine coefficients and free term (separated by a space) |
| The original Diophantine equation |
| General solution of the original equation |
| String solution |
An algorithm for finding the general solution of a Diophantine equation with many unknowns is considered.
In the material Solving a system of two homogeneous Diophantine equations, we mentioned that for the solution we needed a general solution of the Diophantine equation.
Now we'll look at how we get it.
At the moment, the method described on the website of the Department of Number Theory of Mechanics and Mathematics of Moscow State University is widespread in society .
"for the equation a_1 * x_1 +… + a_n * x_n = b, we construct a matrix of n + 1 rows and n columns. The first row is the coefficients for the unknowns in the equation, the rest is the identity matrix. We bring the matrix to such a form that all the elements of the first row zero except for the first, which is equal to GCD.Column transformations: multiply the column by -1, add any other column to the column, multiply by an integer, multiply the column by -1. Then the elements of the first row will be the result of substitution of the corresponding columns in the expression. And the answer is the first column multiplied by b / gcd plus the remaining columns multiplied by any integers. " (c) https://habr.com/ru/post/330632/
My version of the solution of finding a general solution to an arbitrary homogeneous Diophantine equation.
For this I only need the knowledge of how to solve an equation with two unknowns , and we have this knowledge in the form of two formulas.
\(\begin {cases} x_k = ca ^ {\phi (b) -1} + bk, \\y_k = c \frac {1-a ^ {\phi (b)}} {b} -ak, \end {cases} \)
where \(\phi () \) is the Euler function
We will consider the solution immediately on an example, this is clearer.
\(- 5x_1 + 15x_2 + 72x_3-90x_4 + 120x_5 = -13 \)
Let us bring this equation to the form \(Ax + By = C \)
where \(A = gcd (-5,15,72, -90) = 1 \), \(B = 120 \), and \(C = -13 \)
\(x + 120y = -13 \)
Its roots look like
\(x = 107 \\y = -1 \)
Then we can assert that \(- 5x_1 + 15x_2 + 72x_3-90x_4 = 107 \)
a \(x_5 = y = -1 \)
Let's repeat what we did just now
\(A = gcd (-5,15,72) = 1 \), \(B = -90 \), a \(C = 107 \)
We solve
\(x-90y = 107 \)
Its roots look like
\(x = 17 \\y = -1 \)
\(x_4 = y = -1 \)
We continue
\(- 5x_1 + 15x_2 + 72x_3 = 17 \)
\(A = gcd (-5,15) = 5 \), \(B = 72 \), a \(C = 17 \)
Notice that the GCD is 5?
We solve
\(5x + 72y = 17 \)
Its roots look like
\(x = 61 \\y = -4 \)
\(x_3 = y = -4 \)
And the last move remained
Since at the previous stage we have already allocated / taken out the GCD
then the last equation has the form \(- x + 3y = 61 \)
And its roots
\(x = 2 \\y = 21 \)
and consequently
\(x_2 = y = 21 \)
\(x_1 = y = 2 \)
Now we can say with absolute certainty that we have found a particular solution of the original equation and it has the form
\((x_1, x_2, x_3, x_4, x_5) = (2, 21, -4, -1, -1) \)
check it out?
\(- 5 * 2 + 15 * 21 + 72 * (- 4) -90 * (- 1) +120 * (- 1) = - 10 + 315-288 + 90-120 = \\305-288-30 = 275-288 = -13 \)
Q.E.D.
Now we proceed to the second stage.
We argue:
- since a particular solution leads to the following:
\(- 5x_1 + 15x_2 + 72x_3-90x_4 + 120x_5 = 0 \)
then it is logical to assume that we can find the same solution for
\(- 5y_1 + 15y_2 + 72y_3-90y_4 = -120 \)
Find the partial roots for this equation \((y_1, y_2, y_3, y_4) = (0.16, -5.0) \)
Then we solve the equation
\(- 5z_1 + 15z_2 + 72z_3 = 90 \)
Find the private roots for this equation \((z_1, z_2, z_3) = (0,6,0) \)
Ultimately, we will have the following private solutions
\((2, 21, -4, -1, -1) \)
\((0.16, -5.0) \)
\((0,6,0) \)
\((0, -24.5) \)
\((15,5) \)
Let's construct a matrix
\(\begin {pmatrix} 15 & 0 & 0 & 0 & 2 \\5 & -24 & 6 & 16 & 21 \\0 & 5 & 0 & -5 & -4 \\0 & 0 & 1 & 0 & -1 \\0 & 0 & 0 & 1 & -1 \\\end {pmatrix} \)
This will be the general solution.
It is checked quite easily by multiplying the vector of values of the original equation by this matrix
The result is a vector where all zeros except the last value and it coincides with the free term of the equation
\(\begin {pmatrix} -5 & 15 & 72 & -90 & 120 \end {pmatrix} * \begin {pmatrix} 15 & 0 & 0 & 0 & 2 \\5 & -24 & 6 & 16 & 21 \\0 & 5 & 0 & -5 & -4 \\0 & 0 & 1 & 0 & -1 \\0 & 0 &0 & 1 & -1 \end {pmatrix} = \begin {pmatrix} 0 & 0 & 0 & 0 & -13 \end {pmatrix}\)