Lösungen der homogenen Gleichung

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

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

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

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

für eine beliebige ganze Zahl ${\displaystyle t}$ gegeben.

Auffinden einer Partikularlösung

Mithilfe des erweiterten euklidischen Algorithmus kann man Zahlen ${\displaystyle u,v}$ bestimmen, so dass

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

gilt. Setzt man ${\displaystyle s=c/g,}$ so ist

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

eine Lösung der Gleichung ${\displaystyle (*)}$.

Gesamtheit der Lösungen

Die Gesamtheit der Lösungen von ${\displaystyle (*)}$ ist gegeben durch

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

für beliebige ganze Zahlen ${\displaystyle t}$.

Explizite Lösung mittels Satz von Euler

Der Satz von Euler lautet

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

Darin ist ${\displaystyle \varphi (b)}$ die Eulersche Phi-Funktion, d. h. die Anzahl der zu ${\displaystyle 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 ${\displaystyle (*)}$ modulo ${\displaystyle b}$, was ${\displaystyle ax\equiv c{\pmod {b}}}$ ergibt. Der Satz von Euler liefert dann eine explizite Lösung ${\displaystyle 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 Euler ebenfalls eine ganze Zahl ist.

Partikularlösung

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

Der erweiterte euklidische Algorithmus liefert für die gegebene Gleichung

${\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 ${\displaystyle 2=6-4=6-(10-6)=2\cdot 6+(-1)\cdot 10}$. Durch Multiplikation mit ${\displaystyle 100/2=50}$ ergibt sich:

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

also die Partikularlösung ${\displaystyle (x,y)=(100,-50).}$

Lösungen der homogenen Gleichung

Es ist ${\displaystyle a=6,b=10,g=2}$, also ${\displaystyle a'=3,b'=5}$. Die homogene Gleichung

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

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

Gesamtheit der Lösungen

Alle Lösungen ergeben sich also als

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

beispielsweise sind die Lösungen mit nichtnegativen ${\displaystyle x}$ und ${\displaystyle y}$

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