Résolution d'une équa diophantienne carrée
dans Arithmétique
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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
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.
On cherche $x,y$ comme combinaisons linéaires de $(9\pm 4\sqrt{5})^n.$
On trouve toutes les solutions.
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\}.$$
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.
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.$
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.
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.
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
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.
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]
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$.
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.
Edit : j'ai corrigé car je n'ai pas les mêmes notations que Gilles.
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}
$$
$$
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 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$.