Vieta jumping

Das Vieta jumping ist eine Beweistechnik aus der Zahlentheorie. Es wird meist für Probleme verwendet, in welchen ein Quotient zweier positiver ganzer Zahlen gegeben ist, gemeinsam mit einer zu beweisenden Aussage über dessen Lösungen. Es gibt mehrere Varianten des Vieta jumping, die alle auf dem Prinzip des unendlichen Abstiegs durch das wiederholte Ermitteln neuer Lösungen mit Hilfe des Satzes von Vieta aufbauen.

Geschichte

Bekanntheit erlangte die Beweismethode dadurch, dass mit ihr die sechste Aufgabe der Internationalen Mathematik-Olympiade 1988 lösbar ist, die als die schwerste Aufgabe des Wettbewerbs galt:

Es seien $a$ und $b$ positive ganze Zahlen, sodass $a^2+b^2$ durch $ab+1$ teilbar ist. Zeige, dass $\frac{a^2+b^2}{ab+1}$ eine Quadratzahl ist.

Arthur Engel schrieb folgendes über den Schwierigkeitsgrad der Aufgabe: Vorlage:Zitat Vorlage:Zitat

Unter den Teilnehmer, die die maximale Punktzahl für das Lösen der Aufgabe erhielten, waren unter anderem Ngô Bảo Châu, Ravi Vakil, Zvezdelina Stankova und Nicușor Dan. Emanouil Atanassov aus Bulgarien löste die Aufgabe unter Nutzung des Vieta Jumping in einer besonders eleganten Weise und erhielt hierfür einen Sonderpreis.

Standard Vieta jumping

Das Prinzip des Standard Vieta jumping ist ein Beweis durch Widerspruch und besteht aus den folgenden drei Schritten:

1. Annahme, dass eine Lösung existiert, die die gegebenen Voraussetzungen verletzt.
2. Auswahl der kleinsten dieser Lösungen nach einer bestimmten Definition der Minimalität.
3. Beweis, dass dadurch eine neue, kleinere Lösung entsteht und damit ein Widerspruch.

Beispiel

Wir betrachten die oben beschriebene sechste Aufgabe der IMO 1988:

1. Sei $k$ eine natürliche Zahl, die keine Quadratzahl ist. Wir nehmen an, dass es zwei positive ganze Zahlen $a$ und $b$ mit $k=\frac{a^2+b^2}{ab+1}$ gibt.
2. Seien $A$ und $B$ die in der Summe kleinstmöglichen positiven ganze Zahlen, sodass die Bedingung erfüllt ist. O.B.d.A. sei $A\ge B$.
3. Sei $B$ fest und $A=x$. Durch Umformung erhalten wir $x^2-(kB)x+(B^2-k)=0$. Eine Lösung ist offensichtlich $x_1=A$. Durch den Satz von Vieta gilt ferner für die zweite Lösung $x_2=kB-A$ und $x_2=\frac{B^2-k}{A}$.
4. Der erste Ausdruck impliziert, dass $x_2$ ganzzahlig ist, der zweite, dass $x_2\ne 0$, da $k$ nach Voraussetzung keine Quadratzahl ist. Über $\frac{x_2^2+B^2}{x_{2}B+1}=k>0$ folgt weiter, dass $x_2$ positiv-ganzzahlig ist. Ferner gilt wegen $A\ge B$ auch $x_2=\frac{B^2-k}{A}<A$ und damit $x_2+B<A+B$ was der Minimalität von $(A,B)$ widerspricht.

Konstant absteigendes Vieta jumping

Die Methode des konstant absteigenden Vieta jumping wird benutzt, um eine Aussage bezüglich einer Konstanten $k$, die etwas mit dem Verhältnis von $a$ und $b$ zu tun hat, zu beweisen. Anders als beim standard Vieta jumping, handelt es sich beim konstant absteigenden Vieta jumping nicht um einen Beweis durch Widerspruch. Es besteht aus vier Schritten:

1. Beweis des Gleichheitsfalls, sodass o. B. d. A. $a>b$ angenommen werden kann.
2. Es werden $b$ und $k$ fixiert sowie der zu zeigende zu einer quadratischen Gleichung umgeformt, die $a$ als Lösung besitzt. Die andere Lösung $x_2$ ist über den Satz von Vieta bestimmt.
3. Es wird gezeigt, dass für alle $(a,b)$ oberhalb eines bestimmten Basisfalls $0<x_2<b<a$ gilt und dass $x_2$ eine ganze Zahl ist. Es kann also $(a,b)$ durch $(b,x_2)$ ersetzt werden und dieser Vorgang wiederholt werden, bis der Basisfall erreicht ist.
4. Die Aussage wird für den Basisfall bewiesen, und da $k$ über den Beweisprozess hinweg konstant geblieben ist, ist dies hinreichend dafür, dass die Aussage für alle geordneten Zahlenpaare gilt.

Beispiel

Seien $a$ und $b$ positive ganze Zahlen, sodass $a^2+b^2+1$ durch $ab$ teilbar ist. Zeige, dass $3ab=a^2+b^2+1$ gilt.

1. Wenn $a=b$ muss $2a^2-1$ durch $a^2$ teilbar sein und damit $a=b=1$, d. h. $3(1)(1)=1^2+1^{2}1$. O.B.d.A. können wir also $a>b$ annehmen.
2. Sei $k=\frac{a^2+b^2+1}{ab}$. Durch Umformung und Substituierung erhalten wir $x^2-(kb)x+(b^2+1)=0$. Hierzu ist eine Lösung $a$. Damit gilt nach Vieta für die zweite Lösung $x_2=kb-a=\frac{b^2+1}{a}$.
3. Die erste Darstellung zeigt, dass $x_2$ ganzzahlig ist, die zweite, dass $x_2$ positiv ist. Ferner ist wegen $a>b$ auch $x_2=\frac{b^2+1}{a}<b$, für alle $b>1$.
4. Der Basisfall ist $b=1$. Damit die Bedingung erfüllt ist, muss also $a^2+2$ durch $a$ teilbar sein, weshalb $a$ entweder $1$ oder $2$ sein muss. Da der erste Fall zu Beginn bereits ausgeschlossen wurde, erhalten wir $k=\frac{a^2+b^2+1}{ab}=\frac{6}{2}=3$. Und $k$ während des Beweises konstant war, ist dies hinreichend um zu zeigen, dass $k=3$ immer gilt.

Weblinks

• Vieta Root Jumping auf Brilliant.org
• Youtube-Video mit Erläuterung der Lösung von E. Atanassov