Une équation entière
Réponses
-
LOU16,
Mais non, tu n'es pas bouché. Il vaut mieux que je laisse reposer car on risque de se fatiguer. De plus, le terrain que je considère est glissant car il s'agit juste de constatations expérimentales, rien de plus.
Histoire de me contredire (en ce qui concerne laisser reposer), deux choses.
1. J'ai bien vu que tu t'es rétracté sur le why de $x \wedge y = 1$ après avoir écrit que $r_k \wedge m = 1$.
2. Je considère le cas ultra-simple $d = 1$. De sorte que $m \wedge d = 1$ pour tout entier $m \ge 1$. Soit $a$ tel que $a^2 \equiv -1 \bmod m$. Alors les expérimentations de programmation conduisent à l'obtention de $x,y \in \Z$ vérifiant :
$$
x^2 + y^2 = m, \qquad x \wedge y = 1, \qquad x + ay \equiv 0 \bmod m \qquad \qquad (\heartsuit)
$$Pourquoi ``conduisent à l'obtention'' ? Parce que $d \mid m - r_k^2$ vu que $d = 1$.
Par ailleurs, via d'AUTRES considérations, on dispose d'une preuve de $(\heartsuit)$ !
Et toi, quelle est ta position sur $(\heartsuit)$ ? On ne peut pas le déduire de ton post, n'est ce pas ? -
Le $r_k \wedge m =1$ est extraordinaire !! Comme quoi lorsqu'une idée à la c.n s'est insinuée dans le cerveau, il n'est pas facile de l'en déloger.
Pour le cas $d=1$, les choses se passent en effet de manière remarquable car dès lors qu'il existe $a$ tel que $a^2\equiv -1 \mod m$ , alors ton algorithme produira toujours la solution $x=r_k, y=r_{k+1} =t_k, \:\: x\wedge y =1, \:x\equiv \pm ay \mod m. $
Lorsque $m$ n'est divisible par aucun carré d'entier, si l'algorithme produit une solution, alors celle-ci satisfera aussi au cahier des charges.
Pour le cas général, je ne sais pas.
Si "ton" $y$ est égal à $t_k$, alors $(x,y)$ est bien l'unique solution de $x^2+dy^2, \: x\wedge y =1, \:x\equiv \pm ay \mod m.$
Je ne vois par d'argument pour affirmer que quoiqu'il arrive,$\:y = t_k.$ -
Bonjour LOU16
$\bullet$ 1. En fait je n'y crois pas à cette histoire : si $d \mid m - r_k^2$, alors $(m - r_k^2)/d$ est un carré ...etc... Et depuis le départ, j'ai voulu trouver un contre-exemple. Et c'est comme cela que j'ai mis des gardes ``assert ....'' pensant que j'allais en trouver un facilement. Mais je n'en n'ai jamais trouvé !!
Bref, ce n'est forcément intéressant. Je laisse mes gardes, peut-être qu'un jour ... Plus intéressant serait de comprendre comment tu as sorti ta preuve. Car en ce qui concerne ton réseau $\mathcal L$, j'ai suivi les étapes pas à pas sans vraiment comprendre le tout. Mais je pense que j'ai une interprétation de $\mathcal L$ en terme d'un idéal d'un anneau quadratique. Cf le point 4.
Mais peut-être que tu la connais cette interprétation en terme d'idéal ? Je sais que tu sais des choses que tu ne dis pas ``pour simplifier''. Par exemple, à un moment donné, tu as avoué que peut-être, il te faudrait faire intervenir ``une deuxième suite'', en plus de la suite $(t_i)$. C'est comme cela que j'ai REpensé à la suite canonique des coefficients de Bezout $r_i = u_i r_0 + v_i r_1$ où $r_0 = m$ et $r_1 = a$ et fait le rapprochement $t_i = |v_i|$.
Question (vachement indiscrète, ne pas y répondre) : est ce que tu es un cachotier ?
$\bullet$ 2. A propos de $r_k \wedge m = 1$. Encore faut-il amener un contre-exemple. Je t'avais montré un contre-exemple avec $r_i \wedge m = 1$ mais peut-être pas avec $i = k$. Comment je fais pour en trouver un ? Je mets un assert quelque part et je fais des tirages au hasard. Ce qui a fini par me donner :
$$
d = 14, \qquad m = 15, \qquad a = 4
$$On a bien $a^2 \equiv -d \bmod m$. En passant $15 = 1^2 + 14 \times 1^2$, mais c'est autre chose. J'essaie de faire quelque chose de pédagogique (on ne rit pas) en montrant d'abord tous les restes.[color=#000000]> d := 14 ; m := 15 ; a := 4 ; > (a^2 + d) mod m ; 0 > r := m ; rprime := a ; k := 0 ; > while true do > printf format(k), r, rprime ; > if rprime^2 eq 0 then break ; end if ; > r_mod_rprime := r mod rprime ; > r := rprime ; rprime := r_mod_rprime ; > k := k+1 ; > end while ; r0 = 15 r1 = 4 r1 = 4 r2 = 3 r2 = 3 r3 = 1 r3 = 1 r4 = 0 [/color]
Et ceux qui nous concernent réellement :[color=#000000]> r := m ; rprime := a ; k := 0 ; > while true do > printf format(k), r, rprime ; > // "attendre" que r_k^2 (=_ici rprime^2) passe strictement en dessous de m > if rprime^2 lt m then break ; end if ; > r_mod_rprime := r mod rprime ; > r := rprime ; rprime := r_mod_rprime ; > k := k + 1 ; > end while ; r0 = 15 r1 = 4 r1 = 4 r2 = 3 > > rprime ; 3 > m - rprime^2 ; 6 > IsDivisibleBy(m - rprime^2, d) ; false [/color]
On voit ci-dessus que le reste $r_k = 3$ n'est pas premier avec $m = 15$.
En passant, j'ai doublé ma fonction CornacchiaWith.. d'une autre fonction de nom Lou16 (merci) ayant la même sémantique. Lou16 (la fonction) assure en plus un nombre impressionnant de vérifications sur les réduites ...etc.. Avec les fameuses gardes que je voudrais bien qu'elles me donnent un contre-exemple à si $d \mid m - r_k^2$, alors .... Le retour est de la forme $(\text{true}, x,y)$ avec $x^2 + dy^2 = m$ et $x + ay \equiv 0 \bmod m$, si tout s'est bien passé, false sinon.[color=#000000]> d := 14 ; m := 15 ; > Lou16(d, m, a) where a is 4 ; false > Lou16(d, m, a) where a is 1 ; true 1 1 [/color]
$\bullet$ 3. The Euclidean Algorithm Strikes Again. C'est comme cela que dans ma pauvre tête, je nomme le cas $d = -1$ i.e. l'étude $m = x^2 + y^2$ en partant d'une racine carrée de $-1$ modulo $m$. J'attache un vieux devoir à la maison avec le corrigé (et une référence) mais qui est loin de réaliser ce que je sais maintenant. Je me suis aperçu que je n'ai pas les idées claires car je croyais dur comme fer que l'inégalité $a < m/2$ (avec nos notations) était importante. Dans un sens, elle l'est (importante) mais dans un autre sens, non. Clair comme du jus de boudin. Note : la manière dont je m'y prends dans ce devoir n'est pas simple (utilisation des polynômes dits d'Euler).
Encore un exemple pédagogique (sic). Je vais finir par saturer la machine qui héberge avec toutes mes traces d'exécution. Ici je prends $m = 13$ et $a < m/2$ avec $a^2 = -1 \bmod m$. Tous les restes avec $a = 5$ qui vérifie $a < m/2$.[color=#000000]> // a^2 = -1 modulo m i.e. d = -1 > // Exemple : m = 13 (un premier = 1 mod 4), a = +-5 i.e. a=5, a=8 > > m := 13 ; > > a := 5 ; > r := m ; rprime := a ; k := 0 ; > while true do while> // r = r_k, rprime = r_{k+1} while> printf format(k), r, rprime ; while> if rprime^2 eq 0 then break ; end if ; while> r_mod_rprime := r mod rprime ; while> r := rprime ; rprime := r_mod_rprime ; while> k := k+1 ; while> end while ; r0 = 13 r1 = 5 r1 = 5 r2 = 3 r2 = 3 r3 = 2 r3 = 2 r4 = 1 r4 = 1 r5 = 0 [/color]Seulement les restes UTILES.[color=#000000] > r := m ; rprime := a ; k := 0 ; > while true do while> // r = r_k, rprime = r_{k+1} while> printf format(k), r, rprime ; while> // "attendre" que r_k^2 (=_ici rprime^2) passe strictement en dessous de m while> if rprime^2 lt m then break ; end if ; while> r_mod_rprime := r mod rprime ; while> r := rprime ; rprime := r_mod_rprime ; while> k := k + 1 ; while> end while ; r0 = 13 r1 = 5 r1 = 5 r2 = 3 > > rprime ; 3 > x := rprime ; y2 := m - x^2 ; > y2 ; 4 > is_square, y := IsSquare(y2) ; > x, y, x^2 + y^2 = m ; 3 2 13 = 13 [/color]Play again avec $a= -5 \mod 13 = 8$ au lieu de $5$, qui ne vérifie pas $a < m/2$. Tous les restes.[color=#000000]> a := 8 ; > r := m ; rprime := a ; k := 0 ; > while true do while> // r = r_k, rprime = r_{k+1} while> printf format(k), r, rprime ; while> if rprime^2 eq 0 then break ; end if ; while> r_mod_rprime := r mod rprime ; while> r := rprime ; rprime := r_mod_rprime ; while> k := k + 1 ; while> end while ; r0 = 13 r1 = 8 r1 = 8 r2 = 5 r2 = 5 r3 = 3 r3 = 3 r4 = 2 r4 = 2 r5 = 1 r5 = 1 r6 = 0 [/color]Les restes utiles.[color=#000000]> r := m ; rprime := a ; k := 0 ; > while true do while> // r = r_k, rprime = r_{k+1} while> printf format(k), r, rprime ; while> // "attendre" que r_k^2 (=_ici rprime^2) passe strictement en dessous de m while> if rprime^2 lt m then break ; end if ; while> r_mod_rprime := r mod rprime ; while> r := rprime ; rprime := r_mod_rprime ; while> k := k + 1 ; while> end while ; r0 = 13 r1 = 8 r1 = 8 r2 = 5 r2 = 5 r3 = 3 > > rprime ; 3 > x := rprime ; y2 := m - x^2 ; > y2 ; 4 > is_square, y := IsSquare(y2) ; > x, y, x^2 + y^2 = m ; 3 2 13 = 13 [/color]Bilan : me clarifier. Cela m'agace car je passe mon temps à me rendre compte que je ne suis pas aussi clair que je ne le pensais sur tel truc.
$\bullet$ 4. Je vais faire un prochain post sur $m = x^2 + dy^2$ avec une coloration ``théorie des nombres'' (un peu pompeux, ce vocabulaire). -
$\def\A{\Z[\sqrt {-d}]}$Suite avec l'interprétation en théorie des nombres. Je n'ai pas encore regardé la preuve de Cornacchia fournie par H.W. de Lenstra dans l'article de Schoof, Counting points on elliptic curves over finite fields in http://www.numdam.org/article/JTNB_1995__7_1_219_0.pdf
Contexte : $d \ge 1$ un entier, $A = \A$, puis $m, a \in \N^*$ vérifiant $a^2 \equiv -d \bmod m$. Je ne suppose pas encore $d \wedge m = 1$ pour ce que j'en fais.
$\bullet$ 1. Soit $z \in \A$, $z = x+y\sqrt {-d} \ne 0$. Alors $\#(A/Az) = N(z) =_{\rm def} x^2 + dy^2$.
Cela découle de : Soit $M \in M_n(\Z)$, alors le quotient $\Z^n/\text{Im}\, M$ est fini si et seulement si $\det(M) \ne 0$, auquel cas il est de de cardinal $| \det M|$.
On applique cela à la multiplication par $z$ dans la $\Z$-base $(1, \sqrt {-d})$ de $A$
$$
M_z = \left[ \matrix {x & -dy \cr y & x\cr} \right] \quad \text{from}\quad z \times \sqrt {-d} = -dy + x \sqrt {-d}, \qquad
\det(M_z) = x^2 + dy^2
$$
$\bullet$ 2. J'introduis $I = \Z m \oplus \Z (a + \sqrt {-d})$. Lou16 reconnaitra son réseau $\mathcal L$ avec sa base $e_0 = (m,0)$ et $e_1 = (-a, 1)$ sauf que je me suis permis de remplacer $a$ par $-a$.
C'est un idéal de $A$. Il suffit de vérifier que $\sqrt {-d} I \subset I$, ce que l'on fait sur les deux générateurs
$$
m \sqrt {-d} = -a . \underline {m} + m . \underline {(a + \sqrt {-d})} \qquad\qquad
(a + \sqrt {-d}) \sqrt {-d} = -k . \underline {m} + a . \underline {(a + \sqrt {-d})} \qquad \text{avec} \quad a^2 = -d + km
$$
$\bullet$ 3. Le morphisme $\Z \to A/I$ induit un isomorphisme canonique $\Z/m\Z \simeq A/I$. En particulier $A/I$ est de cardinal $m$.
Le morphisme est clairement surjectif car $\sqrt {-d} \equiv -a \bmod I$ et son noyau est $m\Z$ (facile).
$\bullet$ 4. Si on regarde $I$ uniquement comme $\Z$-module, c'est le réseau dont j'ai déjà parlé à propos de l'algorithme de Gauss sur la recherche de vecteurs couts en dimension 2 (le monde est petit) et Lou16 aussi (modulo $\pm a$). Il est défini par :
$$
I = \{ (x,y) \mid x - ay \equiv 0 \mod m \}
$$Cela se voit en écrivant $x + y \sqrt {-d}$ sur la $\Z$-base de $I$
$$
x + y\sqrt {-d} = u m +v(a + \sqrt {-d}) \quad \Longleftrightarrow \quad x = um + va,\ y = v
\quad \Longleftrightarrow \quad x = um + ay
$$Où l'on voit que $x + y\sqrt {-d} \in I$ si et seulement si il existe $u \in \Z$ tel que $x- ay = um$.
$\bullet$ 5. SI l'idéal $I$ est principal, $I = Az$, alors $N(z) = x^2 + dy^2 = m$. En effet, $A/I$ est de cardinal $m$ et de cardinal $N(z)$.
Et bien entendu, $x - ay \equiv 0 \bmod m$. Et $x \wedge y = 1$ puisque $x + y \sqrt {-d} \mid a + \sqrt {-d}$.
Réciproquement, si $x,y$ satisfont $x - ay \equiv 0 \bmod m$ et $x^2 + dy^2 = m$, alors $z := x + y\sqrt {-d}$ est un générateur de $I$.
Justification : $z \in I$ grâce à la première congruence. Et comme $Az \subset I$ et que ces deux idéaux ont même cardinal résiduel, ils sont égaux. -
$\def\mat#1#2#3#4{\left[\matrix {#1 & #2 \cr#3 \cr}\right]}\def\vect#1#2{\left[\matrix {#1\cr#2\cr}\right]}$J'essaie de me clarifier et par conséquent je continue. Je donne deux énoncés ; en aucun cas, ci-dessous, je ne suppose $d \wedge m = 1$.
I. Données : $(d,m) \in \N^* \times \N^*$. Soit $(x_0, y_0) \in \Z \times \Z$ une solution PRIMITIVE (i.e. $x_0 \wedge y_0 = 1$) de $x^2 + dy^2 = m$. Alors $y_0$ est inversible modulo $m$ et en notant $a = -x_0y_0^{-1}$ (où $y_0^{-1} \in \Z$ désigne un inverse de $y_0$ modulo $m$), on a :
$$
a^2 \equiv -d \bmod m, \qquad \qquad x_0 - a y_0 \equiv 0 \bmod m
$$
II. Données : $(d,m,a) \in \N^* \times \N^* \times \N^*$ vérifiant $a^2 \equiv -d \bmod m$. Alors toute solution $(x_0, y_0) \in \Z \times \Z$ de
$$
x^2 + dy^2 = m, \qquad x_0 - a y_0 \equiv 0 \bmod m \qquad\quad \text{est primitive}
$$
$\blacktriangleright$ Justification de I. On a $x_0^2 \in \Z y_0 + \Z m$ et $y_0 \in \Z y_0 + \Z m$. On en déduit que $\gcd(x_0^2, y_0) \in \Z y_0 + \Z m$. Or le pgcd est 1 pour hypothèse. Bilan : $1 \in \Z y_0 + \Z m$. Le reste est immédiat.
$\blacktriangleright$ Justification de II. Je vais d'une part faire une allusion à mon post précédent dans lequel intervient l'idéal $I =\Z m + (a + \sqrt {-d})\Z$ de $A := \Z[\sqrt {-d}]$ et d'autre part je vais expliciter quelque chose qui permet de s'en passer.
En notant $z_0 = x_0 + y_0 \sqrt {-d}$, j'ai dit que $I = Az_0$ en utilisant le fait que $Az_0 \subset I$ et que ces deux idéaux ont même cardinal résiduel $m$ provoquant leur égalité. Une fois obtenu cette égalité d'idéaux, on dit que $x_0 + y_0 \sqrt {-d} \mid a + \sqrt {-d}$ d'où $x_0 \wedge y_0 = 1$.
Ici, je vais expliciter un certificat du fait que $x_0 \wedge y_0 = 1$ via une identité matricielle générale sur les éléments de $I$.
Soit $x + y \sqrt {-d} \in I$. Ce qui signifie tout simplement que $x \equiv ay \bmod m$. Je dis qu'il existe une matrice $2 \times 2$ avec des $* \in \Z$ vérifiant
$$
\mat{x}{-dy}{y}{x} = \mat{m}{a}{0}{1} \mat{*}{*}{*}{*} \qquad \text{disons} \qquad
\mat{x}{-dy}{y}{x} = \mat{m}{a}{0}{1} \mat{*}{*}{y}{x}
$$Signification du disons : l'égalité de gauche détermine les deux $*$ du bas.
D'où vient l'existence ? En termes de $\Z$-module, une $\Z$ base de $I$ est $\vect{m}{0}$, $\vect{a}{1}$. Le vecteur $v_1 := \vect{x}{y}$ appartient à $I$ et comme $I$ est un idéal, il en est de même de $v_2 := \vect{-dy}{x} \leftrightarrow (x + y \sqrt {-d}) \sqrt {-d}$. Ce n'est pas rien le fait que $I$ soit un idéal. Donc les deux vecteurs $v_1, v_2$ s'expriment sur la $\Z$-base de $I$ d'où l'existence de la matrice avec des $* \in \Z$.
MAIS on peut défaire tout ce qu'il y a derrière ce discours et obtenir les $*$. Pour cela, on écrit $x = mq + ay$ (provenant de $x \equiv ay \bmod m$) et $d = -a^2 + km$ (provenant de $a^2 \equiv -d \bmod m$), et en croyant à tout ce que l'on a fait, on tombe sur :
$$
\mat{x}{-dy}{y}{x} = \mat{m}{a}{0}{1} \mat{q}{-qa - yk}{y}{x}
$$Et la chute consiste à prendre le déterminant dans l'égalité matricielle ci-dessus pour obtenir
$$
x^2 + dy^2 = m \times \left|\matrix {* & * \cr y & x\cr}\right|
\qquad \text{a fortiori si } x^2 + dy^2 = m \qquad
\fbox {$\quad \left|\matrix {* & * \cr y & x\cr}\right| = 1\quad$}
$$A droite, en encadré, un CERTIFICAT du fait que $x \wedge y = 1$ lorsque $x^2 + dy^2 = m$ (et $x \equiv ay \bmod m$).
Dans l'article de Basilla, https://projecteuclid.org/download/pdf_1/euclid.pja/1116442240, qui ne suppose pas $d \wedge m = 1$, des choses absolument PAS claires concernant le statut des solutions primitives. Certes, la question est abordée PAR ENDROITS, mais pas dans la proposition 4. -
$\def\Ideal{\text{Ideal}}\def\SL{\text{SL}_2(\Z)}\def\Disc{\text{Disc}}\def\mat#1#2#3#4{\left[\matrix {#1 & #2 \cr#3 \cr}\right]}\def\vect#1#2{\left[\matrix {#1\cr#2\cr}\right]}$Hello. Je continue, histoire d'y voir encore plus clair. On oublie tout ou presque mais on retient l'obsession suivante. Etudier
$$
x^2 + dy^2 = m, \qquad x - ay \equiv m, \qquad \fbox {$a^2 + d = mh$}
$$Un petit nouveau, c'est $h$, la relation encadrée certifiant que $a^2 + d \equiv 0 \bmod m$.
$\bullet$ 1. J'introduis une forme quadratique $Q$
$$
Q = (m, 2a, h) = mX^2 + 2aXY + hY^2, \qquad \Disc(Q) = (2a)^2 - 4mh = 4(a^2 - mh) = -4d = \Disc(\Z[\sqrt {-d}])
$$Avec le coup de la décomposition canonique du trinôme qui suit. Mérite d'être encadré même si c'est du niveau des petites classes
$$
\fbox{$mQ(X,Y) = (mX + aY)^2 + dY^2$} \qquad \qquad \qquad \qquad mX + aY \leftrightarrow x, \qquad Y \leftrightarrow y
$$A droite : $\leftrightarrow$ j'appelle cela un rapprochement, cela ne veut rien dire.
$\bullet$ 2. En tout cas, si $Q$ représente 1 i.e. $1 = Q(X_0, Y_0)$ pour un certain couple $(X_0, Y_0) \in \Z\times \Z$, on obtiendra via le rapprochement un $(x_0, y_0) \in \Z \times \Z$ tel que $x_0 ^2 + dy_0^2 = m$ et $x_0 \equiv ay_0 \bmod m$.
Et réciproquement : si on a un couple $(x_0, y_0) \in \Z \times \Z$ tel que $x_0 ^2 + dy_0^2 = m$ et $x_0 \equiv ay_0 \bmod m$, cela sera facile d'obtenir $(X_0,Y_0)$ entier tel que $Q(X_0, Y_0) = 1$.
$\bullet$ 3. Eh bien, il n'y a plus qu'à se demander si $Q$ représente 1. Et cela tombe bien, car il y a un gars qui s'appelle Gauss et qui a étudié cela en long en large et en travers. C'est la théorie des formes binaires de Gauss, précurseur, en terrain quadratique, de la théorie des idéaux en théorie des nombres (Dedekind), groupe des classes d'idéaux versus classes de formes quadratiques modulo $\SL$ ...etc...
Ce n'est pas difficile de voir que $Q$ représente 1 si et seulement si $Q$ est $\SL$-équivalente à $X^2 + dY^2$ (tiens, tiens), ce qui signifie qu'il existe $T \in \SL$ tel que, au sens de l'action à droite, $Q \star T = X^2 + dY^2$ i.e.
$$
Q(\alpha X + \beta Y, \gamma X + \delta Y) = X^2 + dY^2, \qquad T = \mat{\alpha}{\beta}{\gamma}{\delta} \in \SL
$$Bon, là je dois avouer que j'ai la trouille entre la gauche et la droite, lignes versus colonnes, surtout que mon logiciel travaille parfois à l'envers de mézigue.
$\bullet$ 4. Et Gauss, qui était un mathématicien effectif, a mis au point une notion de forme quadratique réduite et de réduction de formes quadratiques. Tout cela basé sur des choses extrêmement simples : la division euclidienne. Tiens, tiens.
$\bullet$ 5. Un rapport avec l'idéal $I$ de $\Z[\sqrt {-d}]$ des posts précédents ? Oui, c'est PAREIL. A un petit quelque chose près sur le coefficient central $\pm a$ :
$$
I = \Ideal(m, -2a, h) \qquad \quad \overline I = \Ideal(m, 2a, h)
$$Là, je suis obligé de me coucher quelque chose à cause d'une définition imposée par le demi-plan de Poincaré, en changeant les notations. Forme quadratique $(a,b,c)$ de discriminant non carré et en pensant à $aX^2 + bX + c$ et $(aX)^2 + b(aX) + ac$. Et surtout en spécifiant $+ \sqrt {b^2 - 4ac}$ et pas $- \sqrt {b^2 - 4ac}$.
$$
\Ideal(a, b, c) = a \Z \oplus {-b + \sqrt {b^2 - 4ac} \over 2}\Z, \qquad\qquad \text{idéal de } \ \Z\left[ \sqrt {b^2 - 4ac} \right]
$$$\bullet$ Un petit exemple.[color=#000000]> d := 3 ; a := 45 ; m := 13^2 ; h := 12 ; > a^2 + d eq m*h ; true > > Qminus4d := BinaryQuadraticForms(-4*d) ; > Qminus4d ; Binary quadratic forms of discriminant -12 > Q := Qminus4d![m, 2*a, h] ; > Q ; <169,90,12> > > QXY<X,Y> := QuadraticForm(Lattice(Q)) ; > QXY ; 169*X^2 + 90*X*Y + 12*Y^2 > // Forme canonique du trinome > (m*X + a*Y)^2 + d*Y^2 eq m*QXY ; true [/color]
Réduction de Gauss avec obtention de la matrice $T$ qui fait passer (à droite) la forme truc sur la forme machin[color=#000000]> // Gauss-reduction > Qred, T := ReducedForm(Q) ; > Qred ; <1,0,3> > T ; [-1 -3] [ 4 11] > Q*T eq Qred ; true [/color]
Pas intérêt à me gourrer de sens (c'est ma hantise, bis)[color=#000000]> QredX1Y1<X1,Y1> := QuadraticForm(Lattice(Qred)) ; > QredX1Y1 ; X1^2 + 3*Y1^2 > > alpha, beta, gamma, delta := Explode(Eltseq(T)) ; > Evaluate(QXY, [alpha*X1 + beta*Y1, gamma*X1 + delta*Y1]) ; X1^2 + 3*Y1^2 [/color]
Le premier Graal : piocher dans la matrice $T$, ici les colonnes, un certificat du fait que $Q$ représente 1[color=#000000]> Evaluate(QXY, [alpha, gamma]) ; 1 [/color]
Le second Graal $x^2 + dy^2 = m$ ici. $x^2 + 3y^2 = m$[color=#000000]> y := gamma ; > x := m*alpha + a*y ; > // sur que x - ay = 0 modulo m > x ; 11 > y ; 4 > x^2 + d*y^2 eq m ; true [/color]
A noter que j'ai pris $d = 3$ pour être dans le sujet du fil. Merci à Gauss. -
Hello
Je me doutais bien qu'il restait des choses à dire dans cette histoire de $x^2 + dy^2 = m$ concernant les relations entre les divers restes d'une certaine suite de divisions euclidiennes. Ce qui m'a inspiré c'est la lecture d'un petit papier de Peter Wilker, An efficient Algorithmic Solution of the Diophantine Equation $u^2 + 5v^2 = m$, Math. Comp. vol 35, num. 152, Oct 1980, pages 1347-1352 http://ftp.math.utah.edu/pub/tex/bib/toc/mathcomp1980.html#35(152):October:1980
Ici je fais simple avec $p = x^2 + 3y^2$ où $p$ est un premier vérifiant $p \equiv 1 \bmod 3$. Il s'agit d'attraper $(x,y)$. On sait depuis un moment sur ce fil qu'il faut considérer une racine carrée $a$ de $-3$ modulo $p$ et la remonter dans l'intervalle $[2, p-1]$. Et ensuite, réaliser les divisions euclidiennes en partant de $r_0 = p$ et $r_1 = a$ et attendre le reste $r_k$ passant en dessous de $\sqrt p$ :
$$
r_k^2 < p \le r_{k-1}^2
$$[color=#000000]> p := 1759 ; > p ; 1759 > ok, a := IsSquare(GF(p)!-d) ; > a ; 1017 r0 = 1759 r1 = 1017 r1 = 1017 r2 = 742 r2 = 742 r3 = 275 r3 = 275 r4 = 192 r4 = 192 r5 = 83 r5 = 83 r6 = 26 [/color]
Ci-dessus, je suis passé en dessous de $\sqrt p$ avec le reste 26
On a vu aussi que $p = r_k^2 + 3t_k^2$ avec les notations de LOU16. Mais ce qui n'était pas dit, c'est que $t_k$, on l'attrape comme une combinaison linéaire ad-hoc de $r_{k-1}$ et $r_{k+1}$.
Il faut donc que je pousse un peu de manière à mettre au centre du jeu les 3 restes $\fbox {$R = (r_{k-1}, r_k, r_{k+1})$}$[color=#000000]r5 = 83 r6 = 26 r6 = 26 r7 = 5 > R ; [ 83, 26, 5 ] [/color]
Et ici, la combinaison linéaire ad-hoc, c'est la suivante
$$
y = {2r_{k-1} + r_{k+1} \over 9} \qquad \qquad x = r_k,\ y \quad \text{ satisfont }\quad p = x^2 + 3y^2
$$[color=#000000]> k := 2 ; // re-centrer par rapport au triplet > x := R[k] ; > x ; 26 > y := ExactQuotient(2*R[k-1] + R[k+1], 9) ; > y ; 19 > p = x^2 + 3*y^2 ; 1759 = 1759 [/color]
Et en fait, les relations linéaires ad-hoc, il y en a 5 types (j'en ai un peu bavé pour mettre la main dessus). Ici, j'avais choisi $p$ de type 4[color=#000000]// p = 1 mod 3 a^2 = -3 mod p, divisions euclidiennes (p,a) r_k^2 < p <= r_{k-1}^2 // p = x^2 + 3y^2 avec x = r_k et y comme combinaison lineaire de r_{k-1} et r_{k+1} // selon 5 types // // Type 1 2 3 4 5 // // r_{k-1} r_{k+1} r_{k-1} + r_{k+1} 2*r_{k-1} + r_{k+1} r_{k-1} + 2*r_{k+1} // y = -------- -------- ----------------- ----------------- ------------------- // 3 3 6 9 9 [/color] -
Salut Claude,
J'ai du mal à savoir ce que vous supposez sur $d$ et $m$ dans ce fil.
J'ai quand même calculé quelques symboles de Hilbert qui deviennent plutôt agréables quand $d$ et $m$ sont premiers entre eux... -
Salut Gai-Requin
En plein dans le mille quand tu dis ``j'ai du mal à savoir ce que vous supposez sur $d, m$ ..''. Car c'est un véritable b.rdel. Je ne parle pas dans ce fil, car, comme tu le sais, quand j'interviens c'est nécessairement le grand b.rdel, ce n'est pas un scoop.
Je parle de la littérature, des auteurs. En général, l'auteur X annonce une méthode plus simple que Y,Z (j'ai rarement vu un auteur annoncer qu'il fait moins simple que ... encore que cela arrive) mais dans la réalité X ne réalise pas de véritables comparaisons avec Y,Z. Et même que parfois, le résultat n'est pas de même nature. Je ne vais pas citer des noms.
Bref, j'ai essayé de m'y retrouver dans tout ce bazard. Et il me semble, quand je suis intervenu, j'ai essayé de donner des CONTEXTES précis. Mais parfois VARIABLES. La plupart du temps, il y a une quantité additionnelle $a$ qui vérifie $a^2 + d \equiv 0 \bmod m$. Et même $h$ avec $a^2 + d = mh$.
En passant, j'ai dû affronter une histoire ``effective/explicite'' concernant l'aspect primitif des solutions de $(x,y)$ de $x^2 + dy^2 = m$ et $x \equiv ay \bmod m$. Je m'en souviens bien car j'en ai bavé.
PARFOIS, c'est important de supposer $m \wedge d = 1$, d'autres fois, non. Bref, j'ai continué à travailler sur le sujet, dans mon coin. Si tu regardes bien mes posts, ils commencent souvent par quelque chose du genre ``Pour me clarifier ...etc..''. Est ce que cela se clarifie dans ma tête ? Oui. Est ce que c'est complètement clair ? NON.
Peut-être que le point de vue qui pourrait t'intéresser (et que tu connais pas mal) est celui de l'anneau quadratique imaginaire $\Z[\sqrt {-d}]$ et d'un certain idéal $I$ attaché à $(m,d,a)$. Cet idéal étant grosso-modo pareil que la forme quadratique $Q = (m, 2a, h)$ de discriminant $-4d$.
Note : il y a des choses surprenantes à la fin de l'article $u^2 + 5v^2 = m$ que j'ai cité dans mon dernier. Le corps $\Q(\sqrt {-5})$, de discriminant $-20$, possède un groupe de classes d'ordre $h=2$. Il y en a exactement 13 de cette nature (résultat de Stark dans les années 1975, on a fait beaucoup plus depuis avec des $h$ de plus en plus grands). Les voici ces 13 corps. Je les fournis par leurs discriminants[color=#000000]> SomeD := [D : D in [-2*10^2 .. -3] | IsFundamentalDiscriminant(D)] ; > #SomeD ; 62 > [D : D in SomeD | ClassNumber(D) eq 2] ; [ -187, -148, -123, -115, -91, -88, -52, -51, -40, -35, -24, -20, -15 ] > #[D : D in SomeD | ClassNumber(D) eq 2] ; 13 [/color]
Note : j'ai observé pas mal d'autres choses dont je ne dis rien dans ce fil. De temps en temps, je fais un post ce qui ME permet d'avoir un truc un peu près propre. -
J'ai révisé $\mathbb Z[\sqrt{-5}]$ et le fait que $h=2$ arrange pas mal les choses.
Les formes réduites de discriminant $-20$ sont $x^2+5y^2$ et $2x^2+2xy+3y^2$.
Soit $p$ un premier différent de $2$ et $5$.
Je trouve que $p$ est représentable par $x^2+5y^2$ ssi $p\equiv 1,9\bmod 20$.
Et $p$ est représentable par $2x^2+2xy+3y^2$ ssi $p\equiv 3,7\bmod 20$.
De plus, il y a quatre représentations dans chaque cas.
C'est peut-être dans le papier de Peter Wilker que je n'ai pas réussi à trouver, sans trop chercher non plus... -
D'autres précisions où, pour $p$ premier différent de $2$ et $5$, je note $\mathfrak p$ un idéal premier dans $\mathbb Z[\sqrt{-5}]$ au-dessus de $p$.
1) Si $p\equiv 1,9\bmod 20$, alors $p$ est décomposé et $\mathfrak p$ est principal.
2) Si $p\equiv 3,7\bmod 20$, alors $p$ est décomposé et $\mathfrak p$ n'est pas principal.
3) Si $p\equiv 11,13,17,19\bmod 20$, alors $p$ est inerte.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 16
+14 Invités