Résolution d'une équa diophantienne carrée

Bonjour,

Je souhaiterais savoir comment résoudre l'équation diophantienne : x² - 5y² = 44 ou au moins avoir un algorithme qui me permet d'exhiber les solutions

Avez vous des idées? Je vous remercie d'avance

Réponses

  • Un algorithme très naïf :

    Résoudre $1u-5v=44$, ça, on le fait à la main.
    Puis chercher avec la machine « les » (plutôt « des ») solutions qui sont des couples de carrés.

    Bon, pardon pour cette méthode peu astucieuse....

    Est-on certain qu’il y ait des solutions d’ailleurs ?
  • Voir : ce problème

    En gros ce problème se ramène à l'équation que j'ai écrite en haut.
    Ou plutôt il faut chercher les entiers n tels que $5n^2 + 14n + 1$ soit un carré parfait (2 et 5 par exemple du lien fonctionnent) et en résolvant une équation du second degré j'ai à peu de choses près l'équa diophantienne du sujet

    Sauf que les solutions que je recherche vont très très vite exploser donc il faudrait un algo efficace.
  • Bonjour,

    On cherche $x,y$ comme combinaisons linéaires de $(9\pm 4\sqrt{5})^n.$

    On trouve toutes les solutions.
  • Bonjour, c'est une équation Pell-Fermat, on connaît sa solution générale. Entre autre tu peux voir http://mathafou.free.fr/themes_en/kpell.html
  • Bonjour,

    Voici une voie d'accès à chacun des éléments de l'ensemble $ \mathcal E: = \Big\{ (x,y) \in \N^2 \mid x^2- 5y^2 =44\Big\}.$
    Soient $M = \begin{pmatrix} 9&4\\20 &9 \end{pmatrix}, \quad \mathcal A= \Big\{(7,1)\:(8,2)\: (13, 5) \:(17,7)\: (32,14) \:(43,19) \Big \}.\quad $ Alors: $\quad \boxed{ \mathcal E = \Big\{ a\:M^n \mid a\in \mathcal A, \: n\in \N \Big\}.}$
    Pour chaque $a \in \mathcal A$, les solutions $(x,y)$ contenues dans $\mathcal E_a:=\Big\{ a \:M^n \mid n\in \N \Big\} $ sont ainsi caractérisées:
    $$\begin{array} {|c|c|c|}\hline\text{valeur de}\:a& \text {conditions sur}\:(x,y) \\ \hline (7,1) & xy \equiv 3 \mod 4, \quad x \equiv 7y \mod 11\\\hline (8,2) & x\equiv y \equiv 0 \mod 2, \quad x \equiv 4y\mod 11 \\ \hline (13,5) & xy \equiv 1 \mod 4,\quad x \equiv 7y \mod 11 \\ \hline (17,7) & xy\equiv 3 \mod 4, \quad x \equiv 4y \mod 11 \\ \hline (32,14) & x\equiv y \equiv 0 \mod 2 , \quad x \equiv 7y \mod 11 \\ \hline (43,19) & xy \equiv 1 \mod 4, \quad x \equiv 4y \mod 11 \\ \hline \end{array}$$
    On peut également décrire $ \mathcal E$ de la façon suivante: Soient $ \quad \mathcal S: =\Big \{u \in \Z^{\N} \mid \forall n \in \N ,\:\: u_{n+2} = 18u_{n+1} - u_n \Big\}\:\: $ et
    $ \mathcal B:= \Big \{(7,1,83,37) \:\: (8, 2,112, 50) \:\: (13, 5,217,97)\:\:(17, 7,293,131)\:\: (32, 14,568,254)\:\:(43, 19,767,343) \Big\}.\quad$ Alors
    $$ \mathcal E =\Big\{(u_n,v_n )\mid n\in\N, \: u,v \in \mathcal S,\: (u_0,v_0,u_1,v_1 ) \in \mathcal B \Big\}.$$
  • Bonjour LOU16.

    Je connais ce que tu dis dans ton message (et j'apprécie toujours la rigueur de tes notations), à l'exception du tableau. Pourrais-tu m'expliquer son intérêt ?

    Je ne pense pas que ce soit un critère pratique pour générer les solutions, pas plus qu'un critère pratique pour vérifier si un couple est une solution du système. Est-ce simplement par souci d'exhaustivité ?

    Merci.

    Gilles.
  • Bonjour Gilles
    Le "critère pratique" pour exhiber toutes les solutions est bien entendu "$\mathcal E =\Big \{a M^n \mid a\in \mathcal A, \:\: n\in \N \Big \}$" , ou bien la seconde caractérisation de $\mathcal E$ que j'ai donnée.

    J'ai rajouté ce tableau pour préciser les propriétés que possèdent les $(x,y)$ dans chaque $\mathcal E_a := \Big\{ a\:M^n \mid n \in \N\Big\},$ et montrer que ce qui précédait était en adéquation avec les prédictions de la "théorie des formes quadratiques entières".

    Il permet aussi, d'une part de mettre en évidence l'absence de "redondances" dans $\mathcal E = \{a M^n \mid a\in \mathcal A, n \in \N \},$ c'est-à-dire:
    $a\:M^n = a'\: M^{n'} \implies a=a', \ n=n', \ $ et d'autre part, de s'assurer que toutes les solutions de $\mathcal E$ sont ainsi atteintes, car ladite théorie affirme que chacune de celles-ci est "attachée" à l'une des $4$ solutions de $\: x^2 \equiv 5 \mod 44, $ ou bien l'une des $2$ solutions de $\: x^2\equiv 5 \mod 11 $ .

    Cela dit, pour se convaincre que toutes les solutions sont recensées, le plus simple est de constater que $ \mathcal E \cap \left(\N \times[0;18\sqrt{11}]\right) = \mathcal A.$
  • Merci pour ta réponse.

    Je suppose qu'il s'agit de représenter 44 par la forme quadratique $x^2-5y^2$, dont le discriminant est 20. Je me suis plongé une heure et demi dans Primes of de the form $x^2+ny^2$ de David A. Cox ainsi que dans Théorie des nombres de P. Duverney, néanmoins je n'ai pas réussi à extraire la substantifique moëlle pour faire le lien avec ce que tu affirmes. Je me réserve cela pour une autre fois.
  • Bonjour

    Gilles, n est un entier positif, dans le titre de ton livre. Tu cherches donc des coordonnées entières sur un cercle. Ce qui est exactement pas le problème posé. Puisqu'ici il y a un "moins". On cherche donc des coordonnées entières sur une hyperbole. Ça change tout. Désolé pour la gêne occasionnée.
  • Je n'avais pas vu passer cette question. Il s'agit d'une équation de Fermat- [small]« Pell »[/small], dont on a parlé plusieurs fois.

    Les solutions entières de l'équation $u^2-5v^2=\pm 1$ sont les $u+v \sqrt 5$ qui sont les éléments inversibles, ou unités, de l'anneau $\mathbb Z[\sqrt 5]=\mathbb Z+\mathbb Z\sqrt 5$. Dans cet anneau on pose : $N(x+y \sqrt 5)=x^2-5y^2$, et les unités sont caractérisées par $N(u+v \sqrt 5)= \pm 1$. Je ne développe pas, car on en a déjà beaucoup parlé. Le groupe multiplicatif des unités positives est monogène infini, et le générateur est ici $\omega=2+\sqrt 5$. Les solutions de $u^2-5v^2=1$ sont les $u_n+v_n \sqrt 5=(2+\sqrt 5)^{2n}=(9+4\sqrt 5)^{n}$.

    Pour l'équation proposée $x^2-5y^2=44$, les solutions avec $x$ et $y$ impairs se déduisent à partir d'une solution $(x_0,y_0)$ par $x_n+y_n \sqrt 5=(x_0+y_0 \sqrt 5)(9+4 \sqrt 5)^n$. On peut prendre $(x_0,y_0)=(7,1)$.
    Les solutions de $x^2-5y^2=44$ avec $x$ et $y$ pairs s'obtiennent en posant $x=2z$, $y=2t$, d'où $z^2-5t^2=11$, et les solutions se déduisent encore à partir d'une solution $(z_0,t_0)$ par $z_n+t_n \sqrt 5=(z_0+t_0 \sqrt 5)(9+4 \sqrt 5)^n$. On peut prendre $(z_0,t_0)=(4,1)$.

    J'ai trouvé les idées dans J. V. Uspensky, M. A. Heaslet, Elementary Theory of Numbers, McGraw-Hill, 1939, p.332.
    Bonne soirée.
    Fr. Ch
  • Un camarade me signale en a-parté que mon précédent message ne donne pas toutes les solutions, et je l'en remercie.
    Reprenons l'équation proposée $x^2-5y^2=44$, équation de Fermat- [small]« Pell » [/small] généralisée, dont on cherche les solutions en entiers positifs.
    Le PGCD $ x \wedge y$ de $x$ et $y$ est $ 1$ ou $2$ (car son carré divise $44$).

    $\bullet$ Cherchons d'abord les solutions $(x,y)$ avec $ x \wedge y=1$, appelées « solutions primitives ».
    Pour une telle solution, on a : $ y \wedge 44=1$, et il existe donc $r \in \mathbb N^*$ tel que $x \equiv ry ~~(\mod 44)$.
    Il en résulte : $r^2 \equiv 5 ~~(\mod 44)$. Les racines carrées de $5 ~~(\mod 44)$ sont : $7,15,29,37$.
    Pour chacune de ces valeurs de $r$, on a une solution particulière, dans l'ordre : $(x_0,y_0)=(7,1),(17,7),(13,5),(43,19)$.
    À partir de chacune de ces solutions particulières $(x_0,y_0)$, la solution générale est donnée par : $x_n+y_n \sqrt 5=(x_0+y_0 \sqrt 5)(9+4 \sqrt 5)^n$, comme je l'ai expliqué dans mon précédent message.

    $\bullet$ Les solutions $(x,y)$ avec $ x \wedge y=2$ s'obtiennent en posant $x=2z, y=2t$, ce qui ramène à chercher les solutions de $z^2-5t^2=11$, qui sont alors forcément primitives. Même méthode, on a : $ t \wedge 11=1$, et il existe donc $r \in \mathbb N^*$ tel que $z \equiv rt~~ (\mod 11)$, d'où : $r^2 \equiv 5 \mod 11$. Ici c'est plus simple, les racines carrées de $5 ~~(\mod 11)$ sont : $4$ et $7$, et l'on a les solutions particulières : $ (z_0,t_0)=(4,1),(16,7)$.
    À partir de chacune de ces solutions particulières $(z_0,t_0)$, la solution générale est donnée par : $z_n+t_n \sqrt 5=(z_0+t_0 \sqrt 5)(9+4 \sqrt 5)^n$.

    J'espère que ça va cette fois.
    Bonne journée.
    Fr. Ch.
  • Ça me rappelle le problème des oies sauvages.
    Des oies sauvages volent en formation triangulaire (leur nombre est un nombre triangulaire).
    Version gentille. Un chasseur en vise une mais la rate. Alors, les oies sauvages se répartissent en deux formations triangulaires de même effectif. Quel est leur nombre ?
    Version méchante. Un chasseur en abat une. Alors les oies sauvages restantes se répartissent en deux formations triangulaires de même effectif. Quel était leur nombre au début ?
    Bonne journée.
    Fr. Ch.
    [small]Le ciel était gris de nuages
    Il y volait des oies sauvages
    Qui criaient la mort au passage
    Au-dessus des maisons des quais[/small]
  • Concernant le problème gentil, je trouve que les nombres d'oies constituent la suite $(x_n)$ définie par $x_0=0$, $x_1=3$ et $x_{n+2}=6x_{n+1}-x_n+2$.
  • Et pour le problème méchant je trouve que les nombres d'oies se répartissent en deux suites $(x_n)$ vérifiant la même relation de récurrence que pour le problème gentil avec $(x_0,x_1)=(1,2)$ ou $(x_0,x_1)=(1,6)$.
  • Les suites $(x_n)$ trouvées par Gilles ne représentent pas les nombres d'oies mais les indices des nombres triangulaires représentant les nombres d'oies.

    Pour le premier problème le nombre d'oies est $N_n=t_{x_n}=x_n(x_n+1)/2$ avec comme premières valeurs $0,6,210$. La suite vérifie la récurrence $N_{n+2}=34N_{n+1}-N_n+6$.

    Pour le second problème le nombre d'oies est $N'_n=t_{x'_n}$ avec comme premières valeurs $1,3,91$ ou bien $N''_n=t_{x''_n}$ avec comme premières valeurs $1,21,703$. Les deux suites vérifient la même récurrence $N_{n+2}=34N_{n+1}-N_n-10$.
  • Merci Jandri pour la correction de la coquille qui m'a été aussi signalée en message privé.

    J'étais à la recherche d'une relation de récurrence sur $N_n$, mais je n'y étais pas parvenu. Comment as-tu procédé ? Merci.
  • En posant $X_n=2x_n+1$ j'ai exprimé $X_n$ comme combinaison linéaire de $(3+2\sqrt2)^n$ et $(3-2\sqrt2)^n$ puis j'ai utilisé $N_n=\dfrac{x_n(x_n+1)}2=\dfrac{X_n^2-1}8$.

    Edit : j'ai corrigé car je n'ai pas les mêmes notations que Gilles.
  • Merci Jandri je vais regarder avec ta méthode.

    J'essayais de partir de la relation $X_{n+2} = 6X_{n+1}-X_n$ mais je rencontre un terme du type $X_nX_{n+1}$ qui me bloque :

    $$
    N_{n+2}=\frac{(6X_{n+1}-X_n)^2-1}{8}
    $$
  • Pour le premier problème, en utilisant les relations $X_{n+1}=3X_n+4Y_n$ et $Y_{n+1}=2X_n + 3Y_n$, où $X_n$ et $Y_n$ sont les solutions de $X^2-2Y^2=-1$, on arrive à montrer que $6X_nX_{n+1} = X_{n+1}^2+X_n^2-8$, d'où
    $$
    N_{n+2} = \frac{36X_{n+1}^2-12X_{n+1}X_n+X_n^2-1}{8} = \frac{34(X_{n+1}^2-1)-(X_n^2-1)+48}{8} = 34N_{n+1}-N_n+6.
    $$

    edit : corrigé selon la remarque de jandri ci-dessous
  • C'est très bien (à part une coquille dans la première fraction, c'est $X_{n+1}^2$).

    C'est effectivement assez rapide, en partant de $X_{n+1}=3X_n+4Y_n$, d'obtenir $(X_{n+1}-3X_n)^2=16Y_n^2=8X_n^2+8$ ou encore $6X_nX_{n+1} = X_{n+1}^2+X_n^2-8$.

    J'ai procédé différemment en résolvant $X^2-2Y^2=-1$ par $X_n+Y_n\sqrt2=(1+\sqrt2)(3+2\sqrt2)^n$ (équation de Fermat-Pell).
    On obtient $2X_n=(1+\sqrt2)(3+2\sqrt2)^n+(1-\sqrt2)(3-2\sqrt2)^n$ d'où $4X_n^2=(1+\sqrt2)^2(3+2\sqrt2)^{2n}+(1-\sqrt2)^2(3-2\sqrt2)^{2n}-2$.

    On en déduit que $N_n+\dfrac6{32}=\dfrac{4X_n^2+2}{32}$ est combinaison linéaire de deux suites géométriques de raisons $(3\pm2\sqrt2)^2=17\pm12\sqrt2$ qui vérifient la même relation de récurrence $u_{n+2}=34u_{n+1}-u_n$.
  • Merci pour ton explication, elle est plus éclairante que mon calcul.
Connectez-vous ou Inscrivez-vous pour répondre.