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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_1x_1 + a_2x_2 + a_3x_3 + \dots + a_nx_n + c = 0} mit ganzzahligen Koeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i} , bei der man sich nur für ganzzahlige Lösungen interessiert. Linear bedeutet, dass die Variablen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} nicht in Potenzen auftreten (Im Gegensatz zur allgemeinen diophantischen Gleichung).

Auflösung von Gleichungen mit zwei Variablen

Die lineare diophantische Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ax + by = c \qquad (*)}

mit vorgegebenen ganzen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 $P:=(x,y)$ Gitterpunkte mit ganzzahligen Koordinaten in der Euklidischen Ebene, die auf der durch $(*)$ definierten Geraden liegen.

Lösungen der homogenen Gleichung

Schreibt man $a=ga'$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a'} teilbar. Sämtliche Lösungen der homogenen Gleichung sind also durch

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

für eine beliebige ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=x_0+tb',\quad y=y_0-ta'}

für beliebige ganze Zahlen $t$ .

Explizite Lösung mittels Satz von Euler

Der Satz von Euler lautet

Aus

\mathrm {ggT} (a,b)=1

folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 $\mathrm {ggT}$ bereits herausdividiert ist und deshalb $\mathrm {ggT} (a,b)=1$ gilt.^[1] Dann betrachtet man die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (*)} modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} , was $ax\equiv c{\pmod {b}}$ ergibt. Der Satz von Euler liefert dann eine explizite Lösung $x$ , nämlich

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \equiv c a^{\varphi(b)-1} \pmod b} ,

d. h. alle Zahlen der Form Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = c a^{\varphi(b)-1} + tb} .

Eingesetzt in die Ausgangsgleichung ergibt das

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y = c\frac {1- a^{\varphi(b)}} b - ta } ,

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

Berechnungsbeispiel

Die Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y) = (0,10)} .

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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}}

Es folgt $2=6-4=6-(10-6)=2\cdot 6+(-1)\cdot 10$ . Durch Multiplikation mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 100/2=50} ergibt sich:

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

also die Partikularlösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x,y)=(100,-50).}