Benutzer:Farmdudler/Vieta-Jumping

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoVorlage:SSen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Farmdudler auf.

Vieta-Jumping bezeichnet eine mathematische Methode zur Beweisführung in der Zahlentheorie. Es wird auf Probleme angewandt, bei denen eine quadratische Gleichung in zwei natürlichen Zahlen (ungleich null) gegeben ist, über deren Lösungen eine Aussage zu bewgeisen ist. Es gibt viele Varianten des Vieta-Jumpings, von denen alle die Methode des Unendlichen Abstiegs verwenden, indem zu jeder Lösung der Gleichung mittels der Satzgruppe von Vieta eine kleinere gefunden wird.

Geschichte

Vieta-Jumping wurde erstmals auf Aufgaben der Mathematik-Olympiade angewandt. Das erste Olympiade-Beispiel, bei dem die Methode einzusetzen war, wurde 1988 bei der Internationalen Mathematik-Olympiade als sechstes Beispiel, welches für gewöhnlich das schwierigste ist, gestellt. Unter den sieben Teilnehmern, die für die Aufgabe das Maximum von acht Punkten erhielten, war der zukünftige Fields-Medaillenträger Ngô Bảo Châu.

Gewöhnliche Methode

Die gewöhnliche Methode entspricht einer reductio ad absurdum und besteht aus folgenden drei Schritten:

1. Es wird angenommen, die Gleichung besitze Lösungen, welche die zu beweisende Aussage nicht erfüllen.
2. Die kleinste Lösung $\scriptstyle (A,\,B)$, definiert durch die Minimalität einer Funktion von $\scriptstyle A$ und $\scriptstyle B$, meistens $\scriptstyle A\,+\,B$, wird betrachtet (Extremalprinzip). Die Gleichung wird dann zu einer quadratischen Gleichung in $\scriptstyle B$ umgeformt, deren eine Lösung $\scriptstyle A$ ist. Nun wird die Satzgruppe von Vieta verwendet, um die andere zu finden.
3. Es wird gezeigt, dass die zweite Lösung sowohl richtig als auch nach obiger Definition kleiner ist und somit die Minimalität der Lösung $\scriptstyle (A,\,B)$ widerlegt. Daraus folgt, dass die zu beweisende Aussage zutrifft.

Beispiel

1988 IMO #6. Es seien $\scriptstyle a$ und $\scriptstyle b$ natürliche Zählen ungleich null, sodass $\scriptstyle ab\,+\,1$ ein Teiler ist von $\scriptstyle a^{2}\,+\,b^{2}$. Man zeige, dass $\scriptstyle {\frac {a^{2}\,+\,b^{2}}{ab+1}}$ das Quadrat einer ganzen Zahl ist.

1. Sei $\scriptstyle k={\frac {a^{2}\,+\,b^{2}}{ab\,+\,1}}$. Wir nehmen an, dass eine oder mehrere Lösungen existieren, für die $\scriptstyle k$ nicht das Quadrat einer ganzen Zahl ist.
2. Für ein gegebenes $\scriptstyle k$ sei $\scriptstyle (A,\,B)$ die Lösung der Gleichung mit dem kleinstmöglichen Wert von $\scriptstyle A\,+\,B$ und $\scriptstyle A\;\geq \;B$. We can rearrange the equation and replace $\scriptstyle A$ with a variable $\scriptstyle x$ to yield $\scriptstyle x^{2}\,-\,(kB)x\,+\,(B^{2}\,-\,k)\;=\;0$. One root of this equation is $\scriptstyle x_{1}\;=\;A$. By Vieta's formulas, the other root may be written as follows: $\scriptstyle x_{2}\;=\;kB\,-\,A\;=\;{\frac {1}{A}}\left(B^{2}\,-\,k\right)$.
3. Die erste Gleichung zeigt, dass $\scriptstyle x_{2}$ eine ganze Zahl; die zweite, dass es ungleich null ist (denn wäre $\scriptstyle x\;=\;0$, so wäre $\scriptstyle k\;=\;B^{2}$, laut Annahme ist $\scriptstyle k$ jedoch kein Quadrat einer ganzen Zahl). Darüber hinaus kann $\scriptstyle x_{2}$ auch nicht kleiner null sein, da daraus folgte ${\begin{aligned}-kBx_{2}&\geq k\\\longrightarrow x_{2}^{2}-kBx_{2}+B^{2}-k&\geq x_{2}^{2}+k+B^{2}-k\\\longrightarrow x_{2}^{2}-kBx_{2}+B^{2}-k&>0\end{aligned}}$

was ein Widerspruch ist. Schließlich, ${\begin{aligned}&A\geq B\\\longrightarrow &x_{2}={\frac {B^{2}-k}{A}}<A\\\longrightarrow &x_{2}+B<A+B\end{aligned}}$ was jedoch der Minimalität der Lösung $\scriptstyle (A,\,B)$ widerspricht.

Kontinuierliches absteigendes Vieta-Jumping

Die Methode kontinuierlichen absteigenden Vieta-Jumpings wird verwendet, wenn eine Behauptung über eine Konstante $\scriptstyle k$, die etwas mit dem Verhältnis von $\scriptstyle a$ und $\scriptstyle b$ zu tun hat, bewiesen werden soll. Im Unterschied zur Gewöhnlichen Methode ist dies kein Beweis durch Widerspruch. Er besteht in vier Schritten:

1. Für den Gleichheitsfall sei die Behauptung bereits bewiesen, also kann angenommen werden, dass $\scriptstyle a\;>\;b$.
2. $\scriptstyle b$ und $\scriptstyle k$ sind konstant. Der Ausdruck in $\scriptstyle a$, $\scriptstyle b$, und $\scriptstyle k$ wird zu einer quadratische Gleichung mit Koeffizienten in $\scriptstyle b$ und $\scriptstyle k$ umgeformt, sodass eine ihrer Lösungen $\scriptstyle a$ ist. Die andere, $\scriptstyle x_{2}$ wird mit Vietas Formeln ermittelt.
3. Es ist für alle $\scriptstyle (a,\,b)$ über einem gewissen Grundwert gezeigt, dass $\scriptstyle 0\;<\;x_{2}\;<\;b\;<\;a$ und dass $\scriptstyle x_{2}$ eine ganze Zahl ist. Wir können also $\scriptstyle (a,\,b)$ durch $\scriptstyle (b,\,x_{2})$ ersetzen und den Vorgang wiederholen, bis wir beim Grundwert angekommen sind.
4. Die Aussage se für den Grundwert bewiesen, und da $\scriptstyle k$ während dem ganzen Prozess unverändert geblieben ist, genügt dies, um die Aussage für alle geordneten Paare zu zeigen.

Beispiel

Es seien $\scriptstyle a$ und $\scriptstyle b$ positive ganze Zahlen, sodass $\scriptstyle ab$ teilt $\scriptstyle a^{2}\,+\,b^{2}\,+\,1$. Zu zeigen ist, dass $\scriptstyle 3ab\;=\;a^{2}\,+\,b^{2}\,+\,1$.

1. Falls $\scriptstyle a\;=\;b$, muss $\scriptstyle a^{2}$ ein Teiler von $\scriptstyle 2a^{2}\,+\,1$ und dadurch auch von $\scriptstyle a\;=\;b\;=\;1$ und von $\scriptstyle 3(1)(1)\;=\;1^{2}\,+\,1^{2}\,+\,1$ sein.
2. Es sei $\scriptstyle k\;=\;{\frac {1}{ab}}\left(a^{2}\,+\,b^{2}\,+\,1\right)$. Wir formen um und substituieren, sodass $\scriptstyle x^{2}\,-\,(kb)x\,+\,(b^{2}\,+\,1)\;=\;0$. Eine Lösung dieser quadratischen Gleichung ist $a$, also kann laut Vieta die andere so geschrieben werden: $\scriptstyle x_{2}\;=\;kb\,-\,a\;=\;{\frac {b^{2}\,+\,1}{a}}$.
3. Die erste gleichung zeigt, dass $\scriptstyle x_{2}$ is an integer and the second that it is positive. Because $\scriptstyle a\;>\;b$, $\scriptstyle x_{2}\;=\;{\frac {1}{a}}\left(b^{2}\,+\,1\right)\;<\;b$ as long as $\scriptstyle b\;>\;1$.
4. The base case we arrive at is the case where $\scriptstyle b\;=\;1$. For this to satisfy the given condition, $\scriptstyle a$ must divide $\scriptstyle a^{2}\,+\,2$, making $\scriptstyle a$ either 1 or 2. The first case is eliminated because $\scriptstyle a\;=\;b$. In the second case, $\scriptstyle k\;=\;{\frac {1}{ab}}\left(a^{2}\,+\,b^{2}\,+\,1\right)\;=\;{\frac {6}{2}}\;=\;3$. As $\scriptstyle k$ has remained constant throughout this process, this is sufficient to show that $\scriptstyle k$ will always equal 3.

Geometrische Interpretationsmöglichkeit

Vieta jumping can be described in terms of lattice points on hyperbolas in the first quadrant. The same process of finding smaller roots is used instead to find lower lattice points on a hyperbola while remaining in the first quadrant. The procedure is as follows:

1. From the given condition we obtain the equation of a family of hyperbolas that are unchanged by switching $\scriptstyle x$ and $\scriptstyle y$ so that they are symmetric about the line $\scriptstyle y\;=\;x$.
2. Prove the desired result for the intersections of the hyperbolas and the line $\scriptstyle y\;=\;x$.
3. Assume there is some lattice point $\scriptstyle (x,\,y)$ on some hyperbola and without loss of generality $\scriptstyle x\;<\;y$. Then by Vieta's formulas, there is a corresponding lattice point with the same x-coordinate on the other branch of the hyperbola, and by reflection through $\scriptstyle y\;=\;x$ a new point on the original branch of the hyperbola is obtained.
4. It is shown that this process produces lower points on the same branch and can be repeated until some condition (such as $\scriptstyle x\;=\;0$) is achieved. Then by substitution of this condition into the equation of the hyperbola, the desired conclusion will be proven.

Beispiel

Diese Methode kann auf 1988 IMO #6 angewandt werden: Seien $\scriptstyle a$ und $\scriptstyle b$ positive ganze Zahlen, sodass $\scriptstyle ab\,+\,1$ teilt $\scriptstyle a^{2}\,+\,b^{2}$. Man zeige, dass $\scriptstyle {\frac {a^{2}\,+\,b^{2}}{ab\,+\,1}}$ ein perfektes Quadrat ist.

1. Es sei $\scriptstyle {\frac {a^{2}\,+\,b^{2}}{ab\,+\,1}}\;=\;q$, dann haben wir die Hyperbel $\scriptstyle a^{2}\,+\,b^{2}\,-\,qab\,-\,q\;=\;0$. Nenne sie $\scriptstyle H$.
2. Wenn $\scriptstyle a\;=\;b$, so gilt $\scriptstyle a\;=\;b\;=\;q\;=\;1$.
3. Sei $\scriptstyle (x,\,y)$ ein Punkt auf einem Ast von $\scriptstyle H$, und nehmen wir an, dass $\scriptstyle x\,<\,y$ sodass es auf dem höheren Ast liegt. Durch Anwendung von Vietas Formeln muss $\scriptstyle (x,\,qx\,-\,y)$ ein Punkt auf dem niedrigeren Ast von $\scriptstyle H$ sein. Folglich ist ebenso $\scriptstyle (qx\,-\,y,\,x)$ ein Punkt auf dem ursprünglichen Ast. Dieser neue Punkt hat eine niedrigere y-Koordinate, und liegt folglich unter dem ursprünglichen Punkt. Nachdem dieser auf dem oberen Ast liegt, ist er immer noch über $\scriptstyle y\;=\;x$.
4. Dieser Vorgang kann fortgesetzt werden. Nach der Gleichung $\scriptstyle H$ ist es mit diesem Prozess nicht möglich, in den zweiten Quadranten zu kommen. Demnach muss der Prozess mit $\scriptstyle x\;=\;0$ enden, und durch Substitution erhält man $\scriptstyle q\;=\;y^{2}$.