Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
230 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

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

Envoyé par noobey 
Résolution d'une équa diophantienne carrée
le mois dernier
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
Dom
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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 ?
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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.



Edité 1 fois. La dernière correction date de le mois dernier et a été effectuée par noobey.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
avatar
Bonjour,

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

On trouve toutes les solutions.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
avatar
Bonjour, c'est une équation Pell-Fermat, on connaît sa solution générale. Entre autre tu peux voir [mathafou.free.fr]



Edité 1 fois. La dernière correction date de le mois dernier et a été effectuée par AD.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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\}.$$



Edité 9 fois. La dernière correction date de le mois dernier et a été effectuée par LOU16.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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.$



Edité 8 fois. La dernière correction date de le mois dernier et a été effectuée par LOU16.
Re: Résolution d'une équa diophantienne carrée
le mois dernier
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.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
avatar
Je n'avais pas vu passer cette question. Il s'agit d'une équation de Fermat- « Pell », 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



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Chaurien.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
avatar
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- « Pell » 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.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Chaurien.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
avatar
Ç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.
Le ciel était gris de nuages
Il y volait des oies sauvages
Qui criaient la mort au passage
Au-dessus des maisons des quais
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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$.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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)$.



Edité 2 fois. La dernière correction date de il y a six semaines et a été effectuée par Gilles.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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$.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par jandri.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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}
$$



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Gilles.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par Gilles.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
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$.
Re: Résolution d'une équa diophantienne carrée
il y a six semaines
Merci pour ton explication, elle est plus éclairante que mon calcul.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 823, Messages: 1 500 855, Utilisateurs: 28 322.
Notre dernier utilisateur inscrit elhor_abdelali.


Ce forum
Discussions: 5 598, Messages: 67 775.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page