Vieta jumping

Grundidee und Bedeutung

Vieta jumping ist eine Beweistechnik aus der Zahlentheorie. Sie wird vor allem bei Problemen eingesetzt, in denen ein Quotient zweier positiver ganzer Zahlen vorgegeben ist und eine Aussage über dessen Lösungen bewiesen werden soll. Die Methode beruht auf dem Prinzip des unendlichen Abstiegs: Aus einer angenommenen oder gegebenen Lösung wird wiederholt eine neue Lösung mit kleineren Zahlen erzeugt. Dazu wird eine quadratische Gleichung aufgestellt, deren eine Lösung bekannt ist; die zweite Lösung wird mithilfe des Satzes von Vieta bestimmt.

Entscheidend ist, dass die neue Lösung weiterhin die ursprünglichen Bedingungen erfüllt und zugleich kleiner ist. Je nach Variante wird damit entweder ein Widerspruch zur Minimalität einer Lösung gewonnen oder ein beliebiges Zahlenpaar schrittweise auf einen Basisfall zurückgeführt. Die Konstante, die im jeweiligen Problem eine Rolle spielt, bleibt während dieses Vorgangs unverändert.

Historischer Bezug: IMO-Aufgabe von 1988

Bekannt wurde Vieta jumping insbesondere durch die sechste Aufgabe der Internationalen Mathematik-Olympiade (IMO) von 1988, die als besonders schwierige Aufgabe galt:

Für positive ganze Zahlen a und b soll gezeigt werden, dass aus der Teilbarkeit von a²+b² durch ab+1 folgt, dass (a²+b²)/(ab+1) eine Quadratzahl ist.

Nach dem im Artikel wiedergegebenen Bericht von Arthur Engel konnten weder die sechs Mitglieder des australischen Aufgabenausschusses noch vier renommierte australische Zahlentheoretiker die Aufgabe innerhalb von sechs Stunden lösen. Die Jury wählte sie schließlich trotz ihrer außergewöhnlichen Schwierigkeit als letzte Aufgabe des Wettbewerbs aus. Elf Teilnehmer gaben vollständige Lösungen ab. Zu den Teilnehmern mit maximaler Punktzahl gehörten unter anderem Ngô Bảo Châu, Ravi Vakil, Zvezdelina Stankova und Nicușor Dan. Emanouil Atanassov aus Bulgarien löste die Aufgabe besonders elegant mit Vieta jumping und erhielt dafür einen Sonderpreis.

Standard-Vieta-Jumping

Das Standard-Vieta-jumping ist ein Widerspruchsbeweis mit drei Grundschritten:

• Man nimmt an, dass es eine Lösung gibt, welche die zu beweisende Aussage verletzt.
• Unter allen solchen Lösungen wählt man eine kleinste Lösung nach einer geeigneten Minimalitätsdefinition.
• Man konstruiert daraus eine weitere Lösung, die ebenfalls die Bedingungen erfüllt, aber kleiner ist. Das widerspricht der Wahl der kleinsten Lösung.

Im Beispiel zur IMO-Aufgabe wird angenommen, dass k keine Quadratzahl ist und positive ganze Zahlen a und b existieren mit k=(a²+b²)/(ab+1). Unter den entsprechenden Paaren wird ein Paar (A,B) mit minimaler Summe gewählt; ohne Einschränkung gilt A≥B.

Man hält B fest und setzt A=x. Die Bedingung lässt sich zu

x²−(kB)x+(B²−k)=0

umformen. Eine Lösung ist x₁=A. Nach dem Satz von Vieta ist die zweite Lösung

x₂=kB−A=(B²−k)/A.

Aus der ersten Darstellung folgt, dass x₂ ganzzahlig ist. Die zweite Darstellung zeigt, dass x₂ nicht 0 sein kann, weil k keine Quadratzahl ist. Außerdem gilt

(x₂²+B²)/(x₂B+1)=k>0,

sodass x₂ positiv-ganzzahlig ist. Wegen A≥B gilt ferner x₂=(B²−k)/A<A. Damit ist x₂+B<A+B. Das Paar (x₂,B) wäre also eine kleinere Lösung, was der Minimalität von (A,B) widerspricht. Folglich kann die angenommene nichtquadratische Zahl k nicht existieren.

Konstant absteigendes Vieta jumping

Das konstant absteigende Vieta jumping dient dazu, eine Aussage über eine Konstante k zu beweisen, die mit dem Verhältnis von a und b zusammenhängt. Im Unterschied zum Standardverfahren ist es kein Widerspruchsbeweis. Stattdessen wird jedes zulässige Zahlenpaar durch eine Folge kleinerer Paare auf einen Basisfall zurückgeführt, wobei k konstant bleibt.

Die Methode besteht aus vier Schritten:

• Zuerst wird der Gleichheitsfall untersucht. Danach kann ohne Einschränkung beispielsweise a>b angenommen werden.
• Man fixiert b und k und formt die zu beweisende Beziehung in eine quadratische Gleichung um, deren eine Lösung a ist. Die andere Lösung x₂ wird mit dem Satz von Vieta bestimmt.
• Für alle Paare oberhalb eines bestimmten Basisfalls wird gezeigt, dass 0<x₂<b<a gilt und x₂ ganzzahlig ist. Das Paar (a,b) kann daher durch (b,x₂) ersetzt werden. Dieser Vorgang wird wiederholt, bis der Basisfall erreicht ist.
• Schließlich wird die Aussage im Basisfall bewiesen. Da k während des gesamten Abstiegs unverändert bleibt, gilt die Aussage für alle geordneten Zahlenpaare.

Als Beispiel werden positive ganze Zahlen a und b betrachtet, für die a²+b²+1 durch ab teilbar ist. Zu zeigen ist

3ab=a²+b²+1.

Für a=b muss 2a²−1 durch a² teilbar sein. Daher gilt a=b=1; in diesem Fall ist 3·1·1=1²+1²+1. Somit kann ohne Einschränkung a>b angenommen werden.

Man setzt

k=(a²+b²+1)/(ab).

Nach Umformung erhält man die quadratische Gleichung

x²−(kb)x+(b²+1)=0,

deren eine Lösung a ist. Die zweite Lösung lautet nach Vieta

x₂=kb−a=(b²+1)/a.

Die erste Darstellung zeigt, dass x₂ ganzzahlig ist, die zweite, dass x₂ positiv ist. Für a>b gilt außerdem x₂=(b²+1)/a<b, sofern b>1. Der Abstieg endet deshalb beim Basisfall b=1. Dann muss a²+2 durch a teilbar sein, sodass a entweder 1 oder 2 ist. Der Fall a=b=1 wurde bereits behandelt; somit bleibt a=2. Daraus folgt k=(2²+1²+1)/(2·1)=6/2=3. Weil k während des gesamten Beweises konstant war, gilt k=3 für jedes zulässige Paar und damit die behauptete Gleichung.