Olympiades internationales 1988 problème n° 6

Philémon · March 2021

Bonjour,

Un ami m'a posé le problème suivant que je ne connaissais pas :

Si 1 + ab divise a² + b² pour a et b entiers naturels alors le quotient est un carré.

J'ai bloqué longtemps mais j'ai fini par trouver une solution :
- qui montre le résultat demandé
- qui montre que le quotient est le carré du pgcd de a et b (pour a et b non nuls)
- qui permet de trouver tous les couples (a, b ) vérifiant l'énoncé.

Je sais maintenant que ce problème est archi-connu (Olympiades internationales) ainsi que la propriété avec le pgcd, mais pensez-vous que la caractérisation de tous les (a, b) - non demandée dans l'énoncé - soit quelque chose d'éventuellement original ?
Je communiquerai ma démonstration dès que j'aurai un peu de temps.

Merci d'avance.

yan2 · March 2021

Bonjour,

regarde le problème 5 de l'Olympiade mathématique du Canada 1998.

Yan2

lesmathspointclaires · April 2021

Bonjour,

Tu as un exemple non trivial de $ 1+ab $ qui divise $a^2+b^2$?

[Ah oui, c'est dans le problème dont parle Yan2, @Yan2 : comment as-tu fais pour le trouver ::o ?(:D ]

Sneg · April 2021

[Note personnelle : Le problème initial de ce fil est abordé sur la page Wikipédia intitulée « Saut de Viète », avec $a$ et $b$ entiers strictement positifs. Pour le reste, je ne sais pas.]

YvesM · April 2021

Bonjour,

Si $1+ab$ divise $a^2+b^2$ il existe $u$ tel que $a^2+b^2= u (1+ a b).$

Par exemple :
$a=2, b=8, u=4=2^2.$
ou
$a=7, b=343, u=49=7^2.$

Ignotus · April 2021

La question 6 légendaire de l’olympiade

, tu peux rechercher une technique dite "Vieta jumping" pour résoudre le problème en quelques lignes. Si je me rappelle bien c'est une démonstration par l'absurde, tu supposes une solution minimale et on trouve une autre plus petite !

depasse · April 2021

Bonjour à tous,

Si, $\forall (i,j) \in\mathbb{N^2}$, $$u_{ij} : = 0, \text{ si } \ j=0 \qquad\text{et}\quad \sum_{k \in \big[0 , \frac{j-1}{2} \big] \cap \mathbb N} (-1)^k \binom {j-1-k}{k} i^{\ 2j-4k-1}, \text{ si } \ j>0\ ,
$$ alors, $ \forall (a,b) \in\mathbb{N^2}$, $$\dfrac{a^2 +b^2}{1+ab} \in \mathbb{N} \ \Longleftrightarrow\ \exists i \in \mathbb{N} ,\ \dfrac{a^2 +b^2}{1+ab} =i^2 \ \Longleftrightarrow\ \exists (i ,j) \in \mathbb{N^2} , \ \{a,b\}=\{u_{ij},u_{ij +1}\}.

$$ Merci à qui voudra bien infirmer ou confirmer cette proposition. Si Philémon la confirme, je lui laisse l'honneur de donner sa preuve. Ah, flemme, quand tu nous tiens !
Bien cordialement.
Paul

Edit: Merci Alain pour ta mise en page. Je supprime un "\mid" qui s'est alors invité à tort, je pense.

Philémon · May 2021

Bonsoir à tous,

Désolé, je ne me suis pas connecté depuis quelque temps.

@depasse :

Merci.
J'ai été surpris de ton post car je ne pensais pas que a et b pussent (y a-t-il un prof de français dans la salle ?) être qualifiés par une formule fermée, ou plutôt je n'ai pas creusé cette possibilité, bien que l'ayant envisagée après avoir obtenu mon résultat (à mon âge "canonique", ça demande pas mal d'efforts, et aussi "flemme, etc").

C'est typiquement le genre de formule à la Ramanujan, on imagine très bien quelqu'un avoir soudainement l'intuition d'une telle formule après une petite sieste.

De mon côté c'est par une itération que j'ai qualifié tous les (a , b), pour a, b > 0 en fait (si l'un est nul on n'a pas trop de problème).

Je vais regarder si les (uij, uij+1) vérifient les conditions de mon itération, auquel cas ce sera OK de toute manière car on peut avec j = 1 et j = 2 reconstituer tous les "piliers" de mon itération, à savoir les couples (i, i au cube).

Je donnerai ma démonstration (purement arithmétique, pas de propriétés de polynômes ni de coniques) dès que j'aurai le temps.

Enfin, une petite remarque : a et b étant permutables, soit il faut rajouter dans ton équivalence les (uij+1, uij), soit, i étant donné, pour tout j il existe m tel que uij = uim+1 et uij+1=uim

Bonne soirée.

depasse · May 2021

Bonjour à tous,

Merci Philémon pour ta réponse, pour le moins flatteuse!

"pussent" est rare mais parfaitement employé.

J'ai bien écrit "$\{a,b\}=\{u_{ij},u_{ij+1}\}$" et non "$(a,b)=(u_{ij},u_{ij+1})$" (:P)

Quant à la formule close, elle découle de $u_{ij+2}=\dfrac{u_{ij+1}^3-u_{ij}}{1+u_{ij}u_{ij+1}}$ :

$u_{i0}=0$
$u_{i1}=i$
$u_{i2}=i^3$
$u_{i3}=i^5-i$
$u_{i4}=i^7-2i^3$
$u_{i5}=i^9-3i^5+i$
$u_{i6}=i^{11}-4i^7+3i^3$
$u_{i7}=i^{13}-5i^9+6i^5-i$
$u_{i8}=i^{15}-6i^{11}+10i^7-4i^3$

Après la sieste (ou quelques verres), on lit ces calculs de travers (en diagonale) et crèvent alors les yeux : $(1,-1), (1,-2,1),(1,-3,3,-1),(1,-4,6,-4),(1,-5,10),(1,-6) $. On a gagné: merci binôme! et on s'offre la flemme de démontrer sa formule.

Amicalement
Paul

jandri · May 2021

Je suis d'accord avec tout ce qu'a écrit Paul sauf pour le cas $i=1$ (avec ses notations) dans lequel la formule générale n'est pas valable.

Je trouve que la notation avec deux indices est un peu lourde et je préfère noter $\dfrac{a^2 +b^2}{1+ab}=r^2$ plutôt que $i^2$.

Le cas $r=0$ est sans intérêt. Dans le cas $r=1$ il y a exactement deux paires solutions, $\{a,b\}=\{0,1\}$ et $\{a,b\}=\{1,1\}$.

Dans le cas $r\geq2$, il y a une infinité de solutions, les paires $\{a,b\}=\{u_n,u_{n+1}\}$ où la suite $(u_n)$ est définie par $u_0=0,\;u_1=r$ et la relation de récurrence $u_{n+2}=r^2 u_{n+1}-u_n$.
Edit : merci à Philémon de m'avoir signalé la coquille, c'est bien $u_0=0$.

Comme l'a justement fait remarquer Paul, le calcul des premières valeurs et la comparaison avec le triangle de Pascal laisse deviner la formule générale qui se démontre aisément par récurrence : $$u_n=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}(-1)^k{n-1-k\choose k}r^{2n-1-4k}$$

On peut remarquer que $u_n=rP_n(r^2)$ où $P_n$ est le polynôme de Tchebichev normalisé de deuxième espèce défini par $\dfrac{\sin(nt)}{\sin t}=P_n(2\cos t)$.

Philémon · May 2021

Bonsoir,

La relation de récurrence donnée par jandri est la même que celle que j'ai trouvée, à ceci près que je construis une suite de couples d'entiers naturels en définissant l'itération pour deux indices consécutifs (ça aide moins pour trouver une formule, je reconnais).

Mais il y a une erreur d'initialisation chez jandri, car (1, r) ne vérifie pas la relation (a² + b²) = r²(1 + ab) dès lors que r > 1, il faut partir de (r, rcube), j'avais déjà écrit que c'étaient les "piliers" de l'itération.

Donc les entiers (a, b) > 0 tels que 1 + ab divise a² + b² sont :

(1,1) et tous les termes des suites paramétrées par n entier quelconque > 1 et définies comme suit par récurrence :

(a0, b0) = (ncube, n)
(ai+1, bi+1) = (n²ai - bi, ai)

et les mêmes suites en permutant les deux termes de chaque couple (intervertir "abcisse" et "ordonnée"), sinon présupposer dans l'énoncé a supérieur à b.

A noter qu'il est amusant de faire partir l'itération de (1, 1), car on obtient toutes les solutions avec a ou b nul, mais aussi des valeurs négatives, et ça donne un cycle.

En fait, si on généralise le problème en p + ab divise a² + b² dans un rapport de q, on observe que l'on peut remplacer a et b par (qa - b, a) qui vérifient la même relation, ce qui permet d'enclencher une itération (source : APMEP 278 n° 450 trouvée par googelisation post résolution, car il a bien fallu que je vérifie si ma solution était originale).

Ma démonstration utilise une approche différente, elle est un peu longue à bien justifier mais elle est très "pure" sous l'angle arithmétique (enfin c'est mon avis) et elle ramène plusieurs résultats : le quotient est un carré, c'est le carré du pgcd de (a, b) et l'itération donnant toutes les valeurs possibles de (a, b).
Elle ne semble pas fonctionner si on généralise le problème comme ci-dessus, mais je pense me pencher davantage dessus.
J'ai promis de la communiquer, je n'oublie pas (flemme etc).

Bonne soirée ou bonne nuit, au choix.

Olympiades internationales 1988 problème n° 6

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 26