Lineare diophantische Gleichung

Eine lineare diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos von Alexandria, vermutlich um 250 n. Chr.) ist eine Gleichung der Form {\displaystyle a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\dots +a_{n}x_{n}+c=0} mit ganzzahligen Koeffizienten a_{i}, bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen x_{i} nicht in Potenzen auftreten (Im Gegensatz zur allgemeinen diophantischen Gleichung).

Auflösung von Gleichungen mit zwei Variablen

Die lineare diophantische Gleichung

ax+by=c\qquad (*)

mit vorgegebenen ganzen Zahlen a,b,c hat genau dann ganzzahlige Lösungen in x und y, wenn c durch den größten gemeinsamen Teiler (g) von a und b teilbar ist. D.h. die linke Seite ist durch g teilbar, also muss auch c durch g teilbar sein. Wir nehmen dies im Folgenden an.

Wie bei jeder linearen Gleichung ist die Differenz zweier Lösungen eine Lösung der zugehörigen homogenen Gleichung

ax+by=0.\,

Sucht man also eine Lösung der ursprünglichen, inhomogenen Gleichung (*), man spricht dann von einer "Partikularlösung", so erhält man durch Superposition mit den Lösungen der homogenen Gleichung sämtliche anderen Lösungen der inhomogenen Gleichung (*).

Geometrisch interpretiert sind {\displaystyle P:=(x,y)} Gitterpunkte mit ganzzahligen Koordinaten in der Euklidischen Ebene, die auf der durch (*) definierten Gerade liegen.

Lösungen der homogenen Gleichung

Schreibt man a=ga' und b=gb' mit g=\operatorname {ggT}(a,b), so ist die homogene Gleichung äquivalent zu

a'x=-b'y,

und da a' und b' teilerfremd sind, ist x durch b', und y durch a' teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch

x=tb',\quad y=-ta'

für eine beliebige ganze Zahl t gegeben.

Auffinden einer Partikularlösung

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen u,v bestimmen, so dass

au+bv=g mit g=\operatorname {ggT}(a,b)

gilt. Setzt man s=c/g, so ist

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

eine Lösung der Gleichung (*).

Gesamtheit der Lösungen

Die Gesamtheit der Lösungen von (*) ist gegeben durch

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

für beliebige ganze Zahlen t.

Explizite Lösung mittels Satz von Fermat-Euler

Der Satz von Fermat-Euler lautet

Aus {\displaystyle \mathrm {ggT} (a,b)=1} folgt {\displaystyle a^{\varphi (b)}\equiv 1{\pmod {b}}}.

Darin ist \varphi(b) die Eulersche Phi-Funktion, d.h. die Anzahl der zu b teilerfremden Restklassen.

Wir nehmen zur Vereinfachung an, dass der {\displaystyle \mathrm {ggT} } bereits herausdividiert ist und deshalb {\displaystyle \mathrm {ggT} (a,b)=1} gilt. Dann betrachtet man die Gleichung (*) modulo b, was {\displaystyle ax\equiv c{\pmod {b}}} ergibt. Der Satz von Fermat-Euler liefert dann eine explizite Lösung x, nämlich

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

d.h. alle Zahlen der Form {\displaystyle x=ca^{\varphi (b)-1}+tb}.

Eingesetzt in die Ausgangsgleichung ergibt das

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

was nach dem Satz von Fermat-Euler ebenfalls eine ganze Zahl ist.

Berechnungsbeispiel

Die Gleichung

6x+10y=100

soll gelöst werden.

Partikularlösung

Bei einfachen Zahlenbeispielen wie diesem lässt sich eine Partikularlösung leicht ablesen oder erraten, hier zum Beispiel (x,y)=(0,10).

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

{\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}}

Es folgt 2=6-4=6-(10-6)=2\cdot 6+(-1)\cdot 10. Durch Multiplikation mit 100/2=50 ergibt sich:

100=100\cdot 6+(-50)\cdot 10,

also die Partikularlösung (x,y)=(100,-50).

Lösungen der homogenen Gleichung

Es ist a=6,b=10,g=2, also a'=3,b'=5. Die homogene Gleichung

6x+10y=0

hat also die Lösungen (x,y)=(5t,-3t) für ganze Zahlen t.

Gesamtheit der Lösungen

Alle Lösungen ergeben sich also als

(x,y)=(100+5t,-50-3t),

beispielsweise sind die Lösungen mit nichtnegativen x und y

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

Explizite Lösung mittels Satz von Fermat-Euler

Nach dem Dividieren durch den {\displaystyle \mathrm {ggT} =2} erhält man {\displaystyle a=3,b=5,c=50}. Mit {\displaystyle \varphi (5)=4} ergibt sich folglich {\displaystyle x=50\cdot 3^{3}+5t=1350+5t} und {\displaystyle y=50{\frac {1-3^{4}}{5}}-3t=-800-3t}.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 24.09. 2022