Linear Diophantine equation

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 ). ${\displaystyle a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\dots +a_{n}x_{n}+c=0}$ ${\displaystyle a_{i}}$ ${\displaystyle x_{i}}$

Solving equations with two variables

The linear Diophantine equation

${\displaystyle ax+by=c\qquad (*)}$

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. ${\displaystyle a,b,c}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle c}$ ${\displaystyle g}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle g}$ ${\displaystyle c}$ ${\displaystyle g}$

As with any linear equation, the difference between two solutions is a solution to the corresponding homogeneous equation

${\displaystyle ax+by=0.\,}$

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 . ${\displaystyle (*)}$ ${\displaystyle (*)}$

Geometrically interpreted are grid points with integer coordinates in the Euclidean plane that lie on the straight line defined by . ${\displaystyle P:=(x,y)}$ ${\displaystyle (*)}$

Solutions to the homogeneous equation

If you write and with , the homogeneous equation is equivalent to ${\displaystyle a=ga'}$ ${\displaystyle b=gb'}$ ${\displaystyle g=\operatorname {ggT} (a,b)}$

${\displaystyle a'x=-b'y,}$

and there and are coprime is divisible by , and by . So all solutions of the homogeneous equation are through ${\displaystyle a'}$ ${\displaystyle b'}$ ${\displaystyle x}$ ${\displaystyle b'}$ ${\displaystyle y}$ ${\displaystyle a'}$

${\displaystyle x=tb',\quad y=-ta'}$

given for any integer . ${\displaystyle t}$

Finding a particular solution

With the help of the extended Euclidean algorithm one can find numbers such that ${\displaystyle u,v}$

${\displaystyle au+bv=g}$ With ${\displaystyle g=\operatorname {ggT} (a,b)}$

applies. If you put so is ${\displaystyle s=c/g,}$

${\displaystyle x_{0}=su,\quad y_{0}=sv}$

a solution to the equation . ${\displaystyle (*)}$

Totality of solutions

The totality of the solutions of is given by ${\displaystyle (*)}$

${\displaystyle x=x_{0}+tb',\quad y=y_{0}-ta'}$

for any whole number . ${\displaystyle t}$

Explicit solution using Euler's Theorem

The Euler is

From follows . ${\displaystyle \mathrm {ggT} (a,b)=1}$ ${\displaystyle a^{\varphi (b)}\equiv 1{\pmod {b}}}$

Therein is the Euler's totient function , d. H. the number of residual classes to be coprime. ${\displaystyle \varphi (b)}$ ${\displaystyle b}$

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 ${\displaystyle \mathrm {ggT} }$ ${\displaystyle \mathrm {ggT} (a,b)=1}$ ${\displaystyle (*)}$ ${\displaystyle b}$ ${\displaystyle ax\equiv c{\pmod {b}}}$ ${\displaystyle x}$

${\displaystyle x\equiv ca^{\varphi (b)-1}{\pmod {b}}}$,

d. H. all numbers of the form . ${\displaystyle x=ca^{\varphi (b)-1}+tb}$

Inserted into the output equation, this results

${\displaystyle y=c{\frac {1-a^{\varphi (b)}}{b}}-ta}$,

which is also an integer by Euler's theorem.

Calculation example

the equation

${\displaystyle 6x+10y=100}$

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 . ${\displaystyle (x,y)=(0,10)}$

The extended Euclidean algorithm yields for the given equation

${\displaystyle {\begin{matrix}10&=&1\cdot 6&+&4\\6&=&1\cdot 4&+&2&\qquad {\mbox{(2 ist der ggT von 6 und 10)}}\\4&=&2\cdot 2&+&0\\\end{matrix}}}$

It follows . Multiplication with gives: ${\displaystyle 2=6-4=6-(10-6)=2\cdot 6+(-1)\cdot 10}$ ${\displaystyle 100/2=50}$

${\displaystyle 100=100\cdot 6+(-50)\cdot 10,}$

so the particular solution ${\displaystyle (x,y)=(100,-50).}$

Solutions to the homogeneous equation

It is so . The homogeneous equation ${\displaystyle a=6,b=10,g=2}$ ${\displaystyle a'=3,b'=5}$

${\displaystyle 6x+10y=0}$

so has the solutions for whole numbers ${\displaystyle (x,y)=(5t,-3t)}$ ${\displaystyle t.}$

Totality of solutions

So all solutions result as

${\displaystyle (x,y)=(100+5t,-50-3t),}$

for example, the solutions with nonnegative and ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle {\begin{matrix}t=-20:&(0,10)\\t=-19:&(5,7)\\t=-18:&(10,4)\\t=-17:&(15,1).\end{matrix}}}$

Explicit solution using Euler's Theorem

After dividing by that one gets . With follows and . ${\displaystyle \mathrm {ggT} =2}$ ${\displaystyle a=3,b=5,c=50}$ ${\displaystyle \varphi (5)=4}$ ${\displaystyle x=50\cdot 3^{3}+5t=1350+5t}$ ${\displaystyle y=50{\frac {1-3^{4}}{5}}-3t=-800-3t}$

Web links

• Online tool for solving linear Diophantine equations
• Technical thesis on linear Diophantine equations (PDF; 397 kB)
• Example: A farmer ...

Individual evidence

1. ↑ E. Krätzel: Number theory . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, p. 24 .