Théorie > Théorie des nombres > Divers résultats et méthodes

Général
Résumé Chapitre entier
Points théoriques
Lifting The Exponent Lemma Exemples d'application Théorème de Zsigmondy Exemples d'application Vieta Jumping
Exercices
Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5

Vieta Jumping

Le Vieta jumping est une technique de preuve. Son nom provient du fait qu'elle utilise les formules de Viète. Cette technique est assez récente puisque sa première apparition dans une preuve d'un problème d'olympiade date de 1988, avec le problème le plus difficile de l'IMO 1988. Nous prendrons ce problème en exemple plus bas.

Vieta jumping standard

La technique standard de Vieta jumping s'applique lorsque l'on doit prouver une affirmation sur des variables vérifiant une certaine relation. Afin d'être plus concret, nous allons illustrer la technique sur le problème 6 de l'IMO 1988, dont l'énoncé est le suivant :

Problème (IMO 1988, P6)
Soit $a$ et $b$ des entiers strictement positifs tels que $ab+1$ divise $a^2+b^2$. Montrer que $\dfrac{a^2+b^2}{ab+1}$ est un carré parfait.

Solution
La technique comporte plusieurs étapes et consiste en une preuve par l'absurde :

  1. On suppose par l'absurde qu'il existe des variables vérifiant les hypothèses mais ne vérifiant pas l'affirmation demandée.
    Sur l'exemple : Supposons qu'il existe $a$ et $b$ tels que $ab+1$ divise $a^2+b^2$ mais $\frac{a^2+b^2}{ab+1}$ n'est pas un carré parfait. Nous supposons donc que $\frac{a^2+b^2}{ab+1} = k$ est entier mais n'est pas un carré parfait.

  2. On considère une solution "minimale" (dans un certain sens à préciser) $(A,B)$ à la relation du point 1. En ce point, cette méthode va se rapprocher de la méthode de descente infinie.
    Sur l'exemple : Fixons $k$ une fois pour toute et prenons $(A,B)$ tels que $\frac{A^2+B^2}{AB+1} = k$, avec $A+B$ minimal. Nous supposons sans perte de généralité que $A \geq B$ (cela se révélera utile plus tard).

  3. On réarrange la relation sur $A$ et $B$ en une équation quadratique dont les coefficients dépendent de $B$ et dont une racine est $A$. On utilise alors les formules de Viète pour déterminer la deuxième racine $R$ de cette équation quadratique.
    Sur l'exemple : La relation plus haut peut se réécrire $A^2+B^2 = k \cdot (AB+1)$, ou encore $A^2 - kB \cdot A + (B^2 - k) = 0$. Autrement dit, $A$ est une racine du polynôme
    $$x^2 - kB \cdot x + (B^2-k) = 0.$$ La deuxième racine $R$ de ce polynôme vérifie, par les formules de Viète, $R+A = kB$ et $R \cdot A = B^2-k$. On a donc $R = kB - A\ \ (*)$ ainsi que $R = \frac{B^2-k}{A}\ \ (**)$.

  4. On montre que la deuxième racine $R$ de l'équation quadratique donne lieu à une deuxième solution $(R,B)$ qui est à la fois valide (c'est-à-dire vérifiant les hypothèses) et plus petite que la solution $(A,B)$. Cela contredit la minimalité de $(A,B)$ et termine la preuve.
    Sur l'exemple : L'équation $(*)$ implique que le nombre $R$ est entier, et l'équation $(**)$ implique que $R$ est non-nul (car $k$ n'est pas un carré). Du fait que $\frac{R^2+B^2}{RB+1} = k > 0$ il découle aussi que $R$ est positif. Finalement, on a $R = \frac{B^2-k}{A} \leq \frac{A^2-k}{A} < A$, ce qui montre que $R < A$. Donc $(R,B)$ vérifie la même équation que $(A,B)$ mais est tel que $R+B < A+B$, ce qui contredit la minimalité de $(A,B)$. On a donc notre absurdité.

Autre exemple avec les idées du Vieta jumping

La méthode décrite ci-dessus est la méthode "standard", mais l'idée essentielle est d'utiliser les formules de Viète pour construire une solution plus petite que celle en notre possession. Il n'est donc pas obligatoire de suivre à la lettre les étapes ci-dessus pour pouvoir dire qu'on a utilisé le Vieta jumping. Voici un autre problème pour lequel on peut appliquer ce type de méthode :

Problème
Soit $a$ et $b$ des entiers strictement positifs tels que $ab$ divise $a^2+b^2+1$. Prouver que $\dfrac{a^2+b^2+1}{ab} = 3$.

Une solution à ce problème est la suivante :

Solution
  1. Si $a = b$, alors $a^2$ divise $2a^2+1$ donc $a = 1$ et l'énoncé est bien vérifié. Supposons à présent que $a \neq b$, et sans perte de généralité que $a > b$.

  2. Notons $k = \frac{a^2+b^2+1}{ab}$. Cette relation s'écrit aussi $a^2 - bk \cdot a + (b^2+1) = 0$. Donc $a$ est une racine du polynôme
    $$x^2 - bk \cdot x + (b^2+1) = 0.$$ L'autre racine $r$ de ce polynôme vérifie, au vu des formules de Viète, $a+r = bk$ et $ar = b^2+1$. On a donc $r = bk - a \ \ (*)$ et $r = \frac{b^2+1}{a} \ \ (**)$.

  3. On a par $(*)$ que $r$ est un nombre entier, et par $(**)$ que $r > 0$. De plus, comme $a > b$, on a $r = \frac{b^2+1}{a} < b$ sauf pour $(a,b) = (2,1)$. À moins d'être dans ce dernier cas, on peut donc remplacer $(a,b)$ par $(b,r)$, qui est une solution plus petite et pour laquelle la valeur de $k$ reste inchangée.

  4. Cette opération peut être répétée tant que $(a,b) \neq (2,1)$. À terme, on arrive au cas où $(a,b) = (2,1)$ pour lequel on a $k = 3$. Cela signifie que, depuis le début de notre descente, $k$ est égal à $3$.

(Cette page est inspirée de l'article Wikipédia correspondant.)