A linear Diophantine equation (named after the Greek mathematician Diophantos of Alexandria , probably around 250 AD) is an equation of the form with integer coefficients in which one is only interested in integer solutions . Linear means that the variables do not appear in powers (in contrast to the general Diophantine equation ).
Solving equations with two variables
The linear Diophantine equation
with given integers has integer solutions in and if and only if is divisible by and by the greatest common divisor ( ) . Ie the left side is divisible by, so it must also be divisible by . We assume this in the following.
As with any linear equation, the difference between two solutions is a solution to the corresponding homogeneous equation
If one is looking for a solution to the original, inhomogeneous equation , one then speaks of a "particular solution ", then one obtains all other solutions of the inhomogeneous equation by superposition with the solutions of the homogeneous equation .
Geometrically interpreted are grid points with integer coordinates in the Euclidean plane that lie on the straight line defined by .
Solutions to the homogeneous equation
If you write and with , the homogeneous equation is equivalent to
and there and are coprime is divisible by , and by . So all solutions of the homogeneous equation are through
given for any integer .
Finding a particular solution
With the help of the extended Euclidean algorithm one can find numbers such that
-
With
applies. If you put so is
a solution to the equation .
Totality of solutions
The totality of the solutions of is given by
for any whole number .
Explicit solution using Euler's Theorem
The Euler is
- From follows .
Therein is the Euler's totient function , d. H. the number of residual classes to be coprime.
For the sake of simplicity, we assume that it has already been divided out and therefore applies. Then look at the equation modulo what results. Euler's theorem then provides an explicit solution , namely
-
,
d. H. all numbers of the form .
Inserted into the output equation, this results
-
,
which is also an integer by Euler's theorem.
Calculation example
the equation
should be solved.
Particular solution
With simple numerical examples like this one, a particular solution can easily be read off or guessed, here for example .
The extended Euclidean algorithm yields for the given equation
It follows . Multiplication with gives:
so the particular solution
Solutions to the homogeneous equation
It is so . The homogeneous equation
so has the solutions for whole numbers
Totality of solutions
So all solutions result as
for example, the solutions with nonnegative and
Explicit solution using Euler's Theorem
After dividing by that one gets . With follows and .
Web links
Individual evidence
-
↑ E. Krätzel: Number theory . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, p. 24 .