sage: def test(N):
....: for x in range(1,N+1):
....: for y in range(1,x+1):
....: if (x^2+y^2+1)%(x*y)==0:
....: print (x,y,(x^2+y^2+1)/x/y)
....:
sage: test(1000)
(1, 1, 3)
(2, 1, 3)
(5, 2, 3)
(13, 5, 3)
(34, 13, 3)
(89, 34, 3)
(233, 89, 3)
(610, 233, 3)
Edit 1. Cela suggère que tous les nombres qui apparaissent sont des nombres de Fibonacci, que pour $x$ donné il semble exister un unique $y<x$ pour lequel $xy\mid x^2+y^2+1$ et que ce $x$ est le $y$ du couple suivant.
Edit 2. En regardant les nombres de Fibonacci de plus près, on constate que ce sont ceux d'indice impair. D'où la conjecture induite par la manipulation :
$F_{2k+1}^2+F_{2k-1}^2+1=3F_{2k+1}F_{2k-1}$ ;
les seuls couples $(x,y)$ tels que $x>y$ et $xy\mid x^2+y^2+1$ sont les $(F_{2k+1},F_{2k-1})$.
Edit 3.
sage: def t(k):
....: f,g = fibonacci(2*k-1),fibonacci(2*k+1)
....: return f^2+g^2+1-3*f*g
....:
sage: all(t(k)==0 for k in range(10000))
True
Bonjour,
Soit $n\in\Bbb N^*$. On observe que si $x^2+y^2+1=nxy$, alors $(nx-y)^2+x^2+1=n(nx-y)x$ (calcul...) et $nx-y>0$. De plus, si $x<y$, alors $nx = \frac{x^2+y^2+1}{y} \leqslant \frac{2y^2+1}{y} <2y$ (*) donc $0<nx-y<y$. Ainsi, la transformation $(x,y)\mapsto (nx-y,x)$ envoie une solution de $X^2+Y^2+1=nXY$ dont les 2 composantes sont distinctes sur une autre solution de composante maximale strictement plus petite (i.e. $\max(nx-y,x)<\max(x,y)$, mais les composantes de la nouvelle solution ne sont plus forcément distinctes).
Maintenant, on prend $(x,y)\neq (1,1)$ tel que $ n :=\frac{x^2+y^2+1}{xy} \in\Bbb N$. Si $x=y$, alors $\frac1{xy} = n- \frac{x^2+y^2}{xy}=n-2\in \Bbb Z$, donc $x=y=1$. Vu l'hypothèse $(x,y)\neq (1,1)$, on a donc $x\neq y$. Comme le processus du paragraphe précédent ne s'arrête que quand on tombe sur une solution de $X^2+Y^2+1=nXY$ dont les 2 composantes sont identiques, il existe $t\in\Bbb N^*$ tel que $t^2+t^2+1 = nt\cdot t$. Donc $t$ divise $1$, puis $t=1$. D'où $\fbox{$n=3$}$.
PS: La transformation $(x,y) \mapsto (3x-y,x)$ envoie justement $(F_{2k-1},F_{2k+1})$ sur $(F_{2k-3},F_{2k-1})$. Et la preuve précédente tournée à l'envers confirme que les solutions sont toutes de la forme $(F_{2k-1},F_{2k+1})$, comme conjecturé par Math Coss (que je remercie car son message m'a aidé à trouver cette preuve).
(*) Edit: J'ai écrit l'inégalité dans le mauvais sens. La personne qui me l'a signalé m'a aussi proposé une façon de le rattraper : $$nx-2y = \frac{x^2+y^2+1}{y}-2y\leqslant \frac{x^2+1-y^2}{y}\leqslant \frac{(y-1)^2+1-y^2}{y}\leqslant 2\frac{1-y}{y}<0$$ sauf exceptions faciles à traiter.
Et d'où te vient l'idée de la première transformation $(x,y)\mapsto (nx-y,x)$ ?
A posteriori on peut chercher une relation de récurrence entre $(F_{2k-1},F_{2k+1})$ et $(F_{2k+1},F_{2k+3})$, et de là remplacer le $3$ qui apparaît opportunément par $n$ parce qu'on a en tête l'idée de descente qui est classique pour les équations de Pell-Fermat...
Je propose une rédaction peut-être un peu plus fluide de la solution de Calli, qui limite les montées-descentes.
Soit $n$ un entier naturel non nul et soit $(x,y)\in\Z^2$ une solution entière de $x^2+y^2+1=nxy$.
On a d'abord $xy>0$: quitte à changer les deux signes, on suppose désormais $x$ et $y$ strictement positifs. Ensuite, si $x=y$, alors $(n-2)x^2=1$, si bien que $n=3$ et $x=1$.
On suppose désormais que $x<y$. Considérons $(nx-y,x)$. On vérifie que \[(nx-y)^2+x^2+1=n(nx-y)x,\] de sorte que $(nx-y,x)$ est une solution entière (en particulier $nx-y>0$). Montrons que $nx-y\le x$: en effet, \begin{align*}
nx-y\le x&\iff nxy-y^2\le xy\\
&\iff x^2+1\le xy\\
&\iff 1\le x(y-x).
\end{align*}S'agissant d'entiers tels que $0<x<y$, l'inégalité est satisfaite. De plus, il y a égalité SSI $x=1$ et $y-x=1$. Dans ce cas, $(x,y)=(1,2)$ et, en reportant, $n=3$.
Partant d'une solution $(x,y)$ avec $0<x<y$, on produit une suite finie ou infinie de la façon suivante. On part de $(x_0,y_0)=(x,y)$. Pour $k$ entier naturel, supposons avoir construit $(x_0,y_0),\dots,(x_k,y_k)$. Si $x_k=y_k$, le processus s'arrête. Sinon, on pose $(x_{k+1},y_{k+1})=(nx_k-y_k,x_k)$. On vient de montrer que \[y_{k+1}\le x_{k+1},\] et que l'inégalité est stricte, c'est-à-dire que $y_{k+1}<y_k$, sauf si $(x_k,y_k)=(1,2)$.
Comme toute suite décroissante d'entiers stationne, il existe donc un indice pour lequel $(x_k,y_k)=(1,2)=(F_1,F_3)$. On en déduit en particulier que $n=3$ et, vu que \[
x_{j-1}=y_j=-x_{j+1}+3y_{j+1}=-x_{j+1}+3x_j
\]pour tout $j\ge1$, ce qui est la relation de récurrence des nombres de Fibonacci d'indice impair, on peut conclure.
Très très joli. C'est un problème à double détente, car la première étape consiste à prouver que le quotient est nécessairement $3$. C'est tout à fait inattendu et l'approche initiale par la programmation et la conjecture est très précieuse.
Une fois qu'on a montré que l'équation se ramène à : $x^2+y^2+1=3xy$, on se retrouve dans le contexte de l’équation de Fermat-[size=x-small]« Pell »[/size]. En posant $t:=x-2y$, cette équation s'écrit : $t^2+ty-y^2=-1$. C'est $N(t+y \alpha) =-1$ dans l'anneau $\mathbb Z[\alpha]$, avec $\alpha =\frac{1+\sqrt 5}2$ (Nombre d'Or). Dans le groupe des unités de cet anneau, on a : $t+y \alpha=\alpha ^{2k+1}=F_{2k}+F_{2k+1} \alpha$. D'où : $y=F_{2k+1}$, $x=F_{2k}+2F_{2k+1}=F_{2k+3}$.
Problème remarquable, dont j'aimerais connaître l'origine.
Ce vieux Fibonacci (v. 1175 - v. 1250) apparaît là où on ne l'attendait pas. C'est le père tutélaire du renouveau des mathématiques européennes, autrement dit des mathématiques tout court.
Bonne après-midi.
Fr. Ch.
Et d'où te vient l'idée de la première transformation $(x,y)\mapsto (nx-y,x)$ ? [...]
Mais de ton premier message ! Tu m'as servi sur un plateau la forme des solutions, et notamment le fait qu'elle se suivent dans une suite logique avec une formule pour passer de solution en solution ($F_{2k-3} = 3F_{2k-1}-F_{2k+1}$, ça n'est pas dur à trouver). Après il fallait penser au raisonnement consistant à descendre de solution en solution, qui ne m'est pas venu des équations de Pell-Fermat car je les connais très mal (*), mais j'avais déjà vu quelque chose de similaire au bac de spé maths. Et puis on fait passer $X^2+Y^2+1=nXY$ dans la transformation $(x,y)\mapsto (3x-y,x)$ $-$ ce qui n'est pas concluant $-$ puis dans $(x,y)\mapsto (ax-y,x)$ pour voir que c'est $a=n$ qui fonctionne.
(*) Edit: Je me suis rendu compte en écrivant ça que je ne connaissais même pas la définition d'une équation de Pell-Fermat. Juste le nom, que c'est de l'arithmétique et qu'il y a des carrés. Je suis allé voir quand même.
Réponses
Edit 2. En regardant les nombres de Fibonacci de plus près, on constate que ce sont ceux d'indice impair. D'où la conjecture induite par la manipulation :
- $F_{2k+1}^2+F_{2k-1}^2+1=3F_{2k+1}F_{2k-1}$ ;
- les seuls couples $(x,y)$ tels que $x>y$ et $xy\mid x^2+y^2+1$ sont les $(F_{2k+1},F_{2k-1})$.
Edit 3.Soit $n\in\Bbb N^*$. On observe que si $x^2+y^2+1=nxy$, alors $(nx-y)^2+x^2+1=n(nx-y)x$ (calcul...) et $nx-y>0$. De plus, si $x<y$, alors $nx = \frac{x^2+y^2+1}{y} \leqslant \frac{2y^2+1}{y} <2y$ (*) donc $0<nx-y<y$. Ainsi, la transformation $(x,y)\mapsto (nx-y,x)$ envoie une solution de $X^2+Y^2+1=nXY$ dont les 2 composantes sont distinctes sur une autre solution de composante maximale strictement plus petite (i.e. $\max(nx-y,x)<\max(x,y)$, mais les composantes de la nouvelle solution ne sont plus forcément distinctes).
Maintenant, on prend $(x,y)\neq (1,1)$ tel que $ n :=\frac{x^2+y^2+1}{xy} \in\Bbb N$. Si $x=y$, alors $\frac1{xy} = n- \frac{x^2+y^2}{xy}=n-2\in \Bbb Z$, donc $x=y=1$. Vu l'hypothèse $(x,y)\neq (1,1)$, on a donc $x\neq y$. Comme le processus du paragraphe précédent ne s'arrête que quand on tombe sur une solution de $X^2+Y^2+1=nXY$ dont les 2 composantes sont identiques, il existe $t\in\Bbb N^*$ tel que $t^2+t^2+1 = nt\cdot t$. Donc $t$ divise $1$, puis $t=1$. D'où $\fbox{$n=3$}$.
PS: La transformation $(x,y) \mapsto (3x-y,x)$ envoie justement $(F_{2k-1},F_{2k+1})$ sur $(F_{2k-3},F_{2k-1})$. Et la preuve précédente tournée à l'envers confirme que les solutions sont toutes de la forme $(F_{2k-1},F_{2k+1})$, comme conjecturé par Math Coss (que je remercie car son message m'a aidé à trouver cette preuve).
(*) Edit: J'ai écrit l'inégalité dans le mauvais sens. La personne qui me l'a signalé m'a aussi proposé une façon de le rattraper : $$nx-2y = \frac{x^2+y^2+1}{y}-2y\leqslant \frac{x^2+1-y^2}{y}\leqslant \frac{(y-1)^2+1-y^2}{y}\leqslant 2\frac{1-y}{y}<0$$ sauf exceptions faciles à traiter.
A posteriori on peut chercher une relation de récurrence entre $(F_{2k-1},F_{2k+1})$ et $(F_{2k+1},F_{2k+3})$, et de là remplacer le $3$ qui apparaît opportunément par $n$ parce qu'on a en tête l'idée de descente qui est classique pour les équations de Pell-Fermat...
C'est toute de même bien futé, chapeau !
Soit $n$ un entier naturel non nul et soit $(x,y)\in\Z^2$ une solution entière de $x^2+y^2+1=nxy$.
On a d'abord $xy>0$: quitte à changer les deux signes, on suppose désormais $x$ et $y$ strictement positifs. Ensuite, si $x=y$, alors $(n-2)x^2=1$, si bien que $n=3$ et $x=1$.
On suppose désormais que $x<y$. Considérons $(nx-y,x)$. On vérifie que \[(nx-y)^2+x^2+1=n(nx-y)x,\] de sorte que $(nx-y,x)$ est une solution entière (en particulier $nx-y>0$). Montrons que $nx-y\le x$: en effet, \begin{align*}
nx-y\le x&\iff nxy-y^2\le xy\\
&\iff x^2+1\le xy\\
&\iff 1\le x(y-x).
\end{align*}S'agissant d'entiers tels que $0<x<y$, l'inégalité est satisfaite. De plus, il y a égalité SSI $x=1$ et $y-x=1$. Dans ce cas, $(x,y)=(1,2)$ et, en reportant, $n=3$.
Partant d'une solution $(x,y)$ avec $0<x<y$, on produit une suite finie ou infinie de la façon suivante. On part de $(x_0,y_0)=(x,y)$. Pour $k$ entier naturel, supposons avoir construit $(x_0,y_0),\dots,(x_k,y_k)$. Si $x_k=y_k$, le processus s'arrête. Sinon, on pose $(x_{k+1},y_{k+1})=(nx_k-y_k,x_k)$. On vient de montrer que \[y_{k+1}\le x_{k+1},\] et que l'inégalité est stricte, c'est-à-dire que $y_{k+1}<y_k$, sauf si $(x_k,y_k)=(1,2)$.
Comme toute suite décroissante d'entiers stationne, il existe donc un indice pour lequel $(x_k,y_k)=(1,2)=(F_1,F_3)$. On en déduit en particulier que $n=3$ et, vu que \[
x_{j-1}=y_j=-x_{j+1}+3y_{j+1}=-x_{j+1}+3x_j
\]pour tout $j\ge1$, ce qui est la relation de récurrence des nombres de Fibonacci d'indice impair, on peut conclure.
Une fois qu'on a montré que l'équation se ramène à : $x^2+y^2+1=3xy$, on se retrouve dans le contexte de l’équation de Fermat-[size=x-small]« Pell »[/size]. En posant $t:=x-2y$, cette équation s'écrit : $t^2+ty-y^2=-1$. C'est $N(t+y \alpha) =-1$ dans l'anneau $\mathbb Z[\alpha]$, avec $\alpha =\frac{1+\sqrt 5}2$ (Nombre d'Or). Dans le groupe des unités de cet anneau, on a : $t+y \alpha=\alpha ^{2k+1}=F_{2k}+F_{2k+1} \alpha$. D'où : $y=F_{2k+1}$, $x=F_{2k}+2F_{2k+1}=F_{2k+3}$.
Problème remarquable, dont j'aimerais connaître l'origine.
Ce vieux Fibonacci (v. 1175 - v. 1250) apparaît là où on ne l'attendait pas. C'est le père tutélaire du renouveau des mathématiques européennes, autrement dit des mathématiques tout court.
Bonne après-midi.
Fr. Ch.
Mais de ton premier message ! Tu m'as servi sur un plateau la forme des solutions, et notamment le fait qu'elle se suivent dans une suite logique avec une formule pour passer de solution en solution ($F_{2k-3} = 3F_{2k-1}-F_{2k+1}$, ça n'est pas dur à trouver). Après il fallait penser au raisonnement consistant à descendre de solution en solution, qui ne m'est pas venu des équations de Pell-Fermat car je les connais très mal (*), mais j'avais déjà vu quelque chose de similaire au bac de spé maths. Et puis on fait passer $X^2+Y^2+1=nXY$ dans la transformation $(x,y)\mapsto (3x-y,x)$ $-$ ce qui n'est pas concluant $-$ puis dans $(x,y)\mapsto (ax-y,x)$ pour voir que c'est $a=n$ qui fonctionne.
(*) Edit: Je me suis rendu compte en écrivant ça que je ne connaissais même pas la définition d'une équation de Pell-Fermat. Juste le nom, que c'est de l'arithmétique et qu'il y a des carrés. Je suis allé voir quand même.