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:^[1]^[2]

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.^[3]

Arthur Engel schrieb folgendes über den Schwierigkeitsgrad der Aufgabe:

„Nobody of the six members of the Australian problem committee could solve it. Two of the members were husband and wife George and Esther Szekeres, both famous problem solvers and problem creators. Since it was a number theoretic problem it was sent to the four most renowned Australian number theorists. They were asked to work on it for six hours. None of them could solve it in this time. The problem committee submitted it to the jury of the XXIX IMO marked with a double asterisk, which meant a superhard problem, possibly too hard to pose. After a long discussion, the jury finally had the courage to choose it as the last problem of the competition. Eleven students gave perfect solutions.“

– Arthur Engel

„Keiner der sechs Mitglieder des australischen Aufgabenausschusses konnte sie lösen. Zwei der Mitglieder waren das Ehepaar George und Esther Skekeres, beide bekannte Aufgabenlöser und -ersteller. Da es sich um ein Problem aus der Zahlentheorie handelte, wurde es an die vier renommiertesten australischen Mathematiker in diesem Teilgebiet weitergegeben. Sie sollten an der Aufgabe sechs Stunden lang arbeiten. Keiner von ihnen konnte das Problem in dieser Zeit lösen. Der Aufgabenausschuss legte es den Juroren der 29. IMO vor, gekennzeichnet mit einem doppelten Sternchen, was den enormen Schwierigkeitsgrad der Aufgabe kennzeichnen sollte. Nach einer langen Diskussion hatten die Juroren den Mut, das Problem als das letzte des Wettbewerbs auszuwählen. Elf Teilnehmer legten perfekte Lösungen vor.“

– Arthur Engel

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.^[4] Emanouil Atanassov aus Bulgarien löste die Aufgabe unter Nutzung des Vieta Jumping in einer besonders eleganten Weise und erhielt hierfür einen Sonderpreis.^[5]

Standard Vieta jumping

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

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

Beispiel

Wir betrachten die oben beschriebene sechste Aufgabe der IMO 1988:^[7]

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.
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\geq B$ .
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}}$ .
Der erste Ausdruck impliziert, dass $x_{2}$ ganzzahlig ist, der zweite, dass $x_{2}\neq 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\geq 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:^[8]

Beweis des Gleichheitsfalls, sodass o. B. d. A. $a>b$ angenommen werden kann.
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.
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.
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.

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.
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}}$ .
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$ .
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.