Nombre de solutions entière d'une équation elliptique

[Dlzlogic]

Bonjour chan,
Non, je trouve pas comme toi.
Sous entendu 6 solutions, c'est 6 solutions pour les couples (x,y) différents donnant le même valeur de p.
Je reste avec des nombres positifs, y compris 0.
Mais naturellement, si on accepte les nombres négatifs ... ?

[chan79]

Bonjour chan,
Non, je trouve pas comme toi.
Sous entendu 6 solutions, c'est 6 solutions pour les couples (x,y) différents donnant le même valeur de p.
Je reste avec des nombres positifs, y compris 0.
Mais naturellement, si on accepte les nombres négatifs ... ?

A priori, on prend aussi les négatifs
donc, si on veut trouver p pour qu'il y ait 6 solutions,
pour p=16, j'ai bien 6 solutions: (-2,-1),(-2,1), (0,-2),(0,2),(2,-1),(2,1)

[Doraki]

Ds ta réponse, je ne comprends pas au final avec tes v(2)...
: as tu toutes les solutions pour tous les p ?
ou as tu seulement un "si, alors...", qui te permets de ne couvrir seulement et d ene répondre qu'une partie des valeurs possibles de p ?

ce que tu appelles p je l'ai appelé N, parceque d'habitude p ça désigne un nombre premier et j'ai besoin de parler de nombres premiers.

[Dlzlogic]

A priori, on prend aussi les négatifs
donc, si on veut trouver p pour qu'il y ait 6 solutions,
pour p=16, j'ai bien 6 solutions: (-2,-1),(-2,1), (0,-2),(0,2),(2,-1),(2,1)

Ok, comme je n'avais pris que les positifs, ça ne m'en fait que 2 différentes.
Je fais le calcul pour 12, et je te dis.

C'est drôle, pour 112 je n'ai que 11 solutions, mais comme j'imprime pas la première, 'en fait, ça doit correspondre aux plus petits x et Y.
Trouvé X1=-6 Y1=-1 X2=-4 Y2=4 P=112
Trouvé X1=-6 Y1=-1 X2=-2 Y2=5 P=112
Trouvé X1=-6 Y1=-1 X2=2 Y2=5 P=112
Trouvé X1=-6 Y1=-1 X2=4 Y2=4 P=112
Trouvé X1=-6 Y1=-1 X2=6 Y2=1 P=112
on a 6 solutions pour p=112
Trouvé X1=-6 Y1=1 X2=-4 Y2=4 P=112
Trouvé X1=-6 Y1=1 X2=-2 Y2=5 P=112
Trouvé X1=-6 Y1=1 X2=2 Y2=5 P=112
Trouvé X1=-6 Y1=1 X2=4 Y2=4 P=112
on a 5 solutions pour p=112
Manque probablement X2 = 2 ; Y2 =-5 et X2 = -2 ; Y2 =-2
La douzième est peut-être X2=-6 ; Y2=1 (déjà vue).
Mais je sais pas si c'est très intéressant d'avoir les nombres négatifs.
En fait, je suis pas du tout sûr du décompte exact.

Mais ce serait un bon exercice à proposer à des élèves.

[leon1789]

Super Doraki !

Si N = 0 mod 16, il y a 6*P solutions
Si N = 4 mod 16, il y a 2*P solutions
Si N = 1 mod 4 il y a 0 solutions.
Si N = 3 mod 4 il y a 2*P solutions

Pour compléter, quelques cas faciles :

Si N = 2 mod 4 il n'y a pas non plus de solution.
Si N = 8 mod 16, il n'y pas de solution.

si N = 12 mod 16 ?

[lapras]

les éléments de la forme x avec x congru à 1+2j ou 3+2j mod 4 (là il va falloir faire gaffe).

Je vois mal comment tu détermines si parmi les solutions dans Z(j) il y en a une (ou pas) qui est congru à un certain machin. C'est toute la difficulté du problème il me semble.

[chan79]

Ok, comme je n'avais pris que les positifs, ça ne m'en fait que 2 différentes.
Je fais le calcul pour 12, et je te dis.

C'est drôle, pour 112 je n'ai que 11 solutions, mais comme j'imprime pas la première, 'en fait, ça doit correspondre aux plus petits x et Y.
Trouvé X1=-6 Y1=-1 X2=-4 Y2=4 P=112
Trouvé X1=-6 Y1=-1 X2=-2 Y2=5 P=112
Trouvé X1=-6 Y1=-1 X2=2 Y2=5 P=112
Trouvé X1=-6 Y1=-1 X2=4 Y2=4 P=112
Trouvé X1=-6 Y1=-1 X2=6 Y2=1 P=112
on a 6 solutions pour p=112
Trouvé X1=-6 Y1=1 X2=-4 Y2=4 P=112
Trouvé X1=-6 Y1=1 X2=-2 Y2=5 P=112
Trouvé X1=-6 Y1=1 X2=2 Y2=5 P=112
Trouvé X1=-6 Y1=1 X2=4 Y2=4 P=112
on a 5 solutions pour p=112
Manque probablement X2 = 2 ; Y2 =-5 et X2 = -2 ; Y2 =-2
La douzième est peut-être X2=-6 ; Y2=1 (déjà vue).
Mais je sais pas si c'est très intéressant d'avoir les nombres négatifs.
En fait, je suis pas du tout sûr du décompte exact.

Mais ce serait un bon exercice à proposer à des élèves.

J'ai trouvé que la plus petite valeur de p pour laquelle on a 12 solutions est 112.
Ces solutions sont:
(-6,-1), (-6,1), (-4,-4), (-4,4), (-2,-5), (-2,5), (2,-5), (2,5), (4,-4), (4,4), (6,-1),(6,1)

Sinon, on a 16 solutions avec p=3367
Bon, je vais essayer de lire les autres réponses de cette discussion.
J'avais compris que le nombre de solutions z étant donné, il fallait calculer p, en tous cas la plus petite valeur, si elle existe.

[Doraki]

Pour compléter, quelques cas faciles :

Si N = 2 mod 4 il n'y a pas non plus de solution.
Si N = 8 mod 16, il n'y pas de solution.

si N = 12 mod 16 ?

Ces cas-là sont éliminés par la condition juste avant qui dit que la décomposition en facteurs copremiers de N doit faire intervenir que des nombres conrgus à 0 ou 1 mod 3.

Je vois mal comment tu détermines si parmi les solutions dans Z(j) il y en a une (ou pas) qui est congru à un certain machin. C'est toute la difficulté du problème il me semble.

Quand tu regardes modulo U (le groupe des inversibles), il faut fabriquer un produit qui tombe dans la deuxième classe de (Z[j]/(4))*/U. Une fois qu'il y est il y a 2 inversibles qui vont faire marcher la congruence (comme dans le cas précédent).

Là soit tu devines que lorsque p=1 mod 3, l'idéal premier correspondant est dans cette classe p = 3 mod 4, soit tu connais ta théorie des corps de classes et tu dis qu'il tombe dedans il ne se décompose pas dans l'extension abélienne correspondante, à savoir Z[j,i] ; qui est abélienne sur Q, donc correspond à un condition modulaire sur p (le générateur positif de l'idéal (p) de Z), et on retombe sur p = 3 mod 4. (on a pas toujours la chance d'avoir l'extension correspondante qui soit abélienne sur Q)

Donc on veut un nombre impair de premiers congrus à 3 mod 4, ce qui revient à demander à ce que N soit congru à 3 mod 4 (puisque les autres facteurs premiers doivent de toute façon apparaître par paires).

Et rétrospectivement, c'est totalement immédiat de montrer que 4x²+3y² est congru à 0 ou 3 mod 4, donc on a pas fait n'importe quoi. Et du coup j'me demande si tout ça était bien nécessaire.

[lapras]

Ok je suis a peu près convaincu, mais c'est donc un gros coup de chance qu'on ait cette extension abélienne, d'où mes doutes sur l'existence d'une caractérisation "simple" dans ce cas.

[leon1789]

Ces cas-là sont éliminés par la condition juste avant qui dit que la décomposition en facteurs copremiers de N doit faire intervenir que des nombres congrus à 0 ou 1 mod 3.

Intervient aussi les nombres premiers = 2 mod 3 aussi, lorsqu'ils ont une valuation paire, non ?
Lorsque N=12 mod 16, il peut y a avoir des solutions :

[Doraki]

Ah oui t'as raison, je l'avais oublié dans le cas v(2) = 2, il est pareil que le cas N = 4 mod 16. En fait j'voulais dire N = 4 mod 8 ^^'

[Doraki]

Ok je suis a peu près convaincu, mais c'est donc un gros coup de chance qu'on ait cette extension abélienne, d'où mes doutes sur l'existence d'une caractérisation "simple" dans ce cas.

Bon en fait là vu que l'extension est de degré 2, et que tous les groupes d'ordre 4 sont abéliens, ça va. Mais oui si tu commences à prendre des réseaux moins denses, on perd ce genre de caractérisation.

[leon1789]

Bon finalement,
On décompose N en facteurs premiers, on appelle v(p) l'exposant de p dans la factorisation de N.
On calcule P = produit pour p=1 mod 3 des 1+v(p)

Si il y a un p=2 mod 3 avec v(p) impair, il y a 0 solutions.
Si N = 0 mod 16, il y a 6*P solutions
Si N = 4 mod 8, il y a 2*P solutions
Si N = 1 mod 4 il y a 0 solutions.
Si N = 3 mod 4 il y a 2*P solutions

Non seulement, ta preuve permet de dénombrer les solutions, mais elle permet de toutes les calculer explicitement (et de manière très rapide, même si N est énorme : il faut quand même le factoriser, ce qui pose problème si N a 50 ou 100 chiffres par exemple). Il faut juste obtenir un générateur de chaque idéal maximal de Z[j] contenant p lorsque p = 1 mod 3 et cela se fait très bien en obtenant une racine carrée de -3 dans Z/pZ.

Par exemple : résoudre

On factorise la constante
les deux nombres premiers impairs sont congrus à 1 mod 3.
La conclusion de Doraki est qu'il existe 6 * (2*2) = 24 solutions.

Celles-ci sont (je laisse les signes pour des raisons d'homogénéité)
[-607624846930, -159139840859],
[-607624846930, 159139840859],
[-549755813890, 274877906941],
[-549755813890, -274877906941],
[-549755813886, -274877906947],
[-549755813886, 274877906947],
[-462952264324, -376148714768],
[-462952264324, 376148714768],
[-144672582606, -535288555627],
[-144672582606, 535288555627],
[-4, 549755813888],
[-4, -549755813888],
[4, 549755813888],
[4, -549755813888],
[144672582606, 535288555627],
[144672582606, -535288555627],
[462952264324, 376148714768],
[462952264324, -376148714768],
[549755813886, -274877906947],
[549755813886, 274877906947],
[549755813890, -274877906941],
[549755813890, 274877906941],
[607624846930, 159139840859],
[607624846930, -159139840859]

obtenues en 172 millisecondes (avec un logiciel de calcul vieux de 15 ans et un programme pas du tout optimisé).

[leon1789]

Bon finalement,
On décompose N en facteurs premiers, on appelle v(p) l'exposant de p dans la factorisation de N.
On calcule P = produit pour p=1 mod 3 des 1+v(p)

Si il y a un p=2 mod 3 avec v(p) impair, il y a 0 solutions.
Si N = 0 mod 16, il y a 6*P solutions
Si N = 4 mod 8, il y a 2*P solutions
Si N = 1 mod 4 il y a 0 solutions.
Si N = 3 mod 4 il y a 2*P solutions

Non seulement, ta preuve permet de dénombrer les solutions, mais elle permet de toutes les calculer explicitement (et de manière très rapide, même si N est énorme : il faut quand même le factoriser, ce qui pose problème si N a 50 ou 100 chiffres par exemple). Il faut juste obtenir un générateur de chaque idéal maximal de Z[j] contenant p lorsque p = 1 mod 3 et cela se fait très bien en obtenant une racine carrée de -3 dans Z/pZ.

Par exemple : résoudre

On factorise la constante
les deux nombres premiers impairs sont congrus à 1 mod 3.
La conclusion de Doraki est qu'il existe 6 * (2*2) = 24 solutions.

Celles-ci sont (je laisse les signes dans [x,y] pour des raisons d'homogénéité)
[-607624846930, -159139840859],
[-607624846930, 159139840859],
[-549755813890, 274877906941],
[-549755813890, -274877906941],
[-549755813886, -274877906947],
[-549755813886, 274877906947],
[-462952264324, -376148714768],
[-462952264324, 376148714768],
[-144672582606, -535288555627],
[-144672582606, 535288555627],
[-4, 549755813888],
[-4, -549755813888],
[4, 549755813888],
[4, -549755813888],
[144672582606, 535288555627],
[144672582606, -535288555627],
[462952264324, 376148714768],
[462952264324, -376148714768],
[549755813886, -274877906947],
[549755813886, 274877906947],
[549755813890, -274877906941],
[549755813890, 274877906941],
[607624846930, 159139840859],
[607624846930, -159139840859]

obtenues en 172 millisecondes (avec un logiciel de calcul vieux de 15 ans et un programme pas du tout optimisé).

[Doraki]

Maintenant recommence en prenant N = 50!²

[leon1789]

Maintenant recommence en prenant N = 50!²

N se factorise facilement mais ça chauffe ... :lol3:

Pour calculer une solution, pas de souci, en 281 millisecondes
[x = 12334217582993561649914990165969117089989994620125184000000000000,
y = 10823796643606915361440302709464082735415869688512512000000000000]

Mais pour toutes les solutions, c'est horrible : ce qui coûte, c'est les multiplications dans Z[j] :
'y en a des centaines de millions, et avec des coefficients à 50 ou 100 chiffres !

[leon1789]

Maintenant recommence en prenant N = 50!²

N se factorise facilement mais ça chauffe ... :lol3:

Pour calculer une solution, pas de souci (en 281 millisecondes) :

,



Mais pour calculer toutes les solutions, c'est effectivement horrible ! Certes, elles sont nombreuses, mais ce n'est pas tellement leur nombre qui est problématique. Ce qui coûte, c'est les multiplications dans Z[j] : 'y en a des centaines de millions, et avec des coefficients à 50 ou 100 chiffres !

[Dacu]

Bonjour,

j'ai un problème que j'aimerais arriver à résoudre mais je sèche totalement.

Malheureusement je suis informaticien et pas mathématicien et vu la nature du problème une solution "brutte force" est peu envisageable dans le cas présent.

J'ai une équation de la forme:
3 x^2 + 4 y^ 2 = p

La première question est, comment trouver efficacement l'ensemble des x et y qui satisfont cette équation (p sera un grand nombre ~10^20) (x et y devant être des entiers) ?

Mais la vraie question n'est pas celle là.

Le problème est de trouver une valeur de p pour laquelle on a exactement z réponses possibles à cette équation.

J'avoue que je ne sais absolument pas comment le faire mathématiquement (ni le programmer efficacement d'ailleurs).

Merci pour toutes les indications que vous pourriez me donner.
JK

Bonsoir!
On peut montrer facilement que et .L'équation peut être écrite .
Pour chaque valeur de nous recherchons l'intervalle dans lequel les valeurs de peuvent être , conformément aux conditions imposées.Je pense que vous pouvez faire program de calcul basé sur le raisonnement suivant :
1.- Pour il est nécessaire ce qui signifie que et donc et .
2.- Pour il est nécessaire ce qui signifie que et donc et .
Et ainsi de suite....
Cordialement!

[Doraki]

Mais pour calculer toutes les solutions, c'est effectivement horrible ! Certes, elles sont nombreuses, mais ce n'est pas tellement leur nombre qui est problématique. Ce qui coûte, c'est les multiplications dans Z[j] : 'y en a des centaines de millions, et avec des coefficients à 50 ou 100 chiffres !

Au début j'voulais faire sournoisement exploser le nombre de solutions, mais un truc comme 1000!² ça commençait à faire un N un peu gros. 50!² en comparaison, ça devrait aller.
Là je pense que tu as un peu d'optimisation à faire.

(enfin ceci dit moi j'ai rien programmé de mon coté, je sais pas combien il y a de solutions etc)

[leon1789]

Au début j'voulais faire sournoisement exploser le nombre de solutions, mais un truc comme 1000!² ça commençait à faire un N un peu gros.

:doh: N = 1000!² , pour une explosion :ptdr: ça fait plus de 5000 chiffres :

50!² en comparaison, ça devrait aller.
Là je pense que tu as un peu d'optimisation à faire.

J'ai essayé de voir des petits trucs, sans faire trop d'effort (on va pas le vendre, hein). Ca finit par donner le résultat. Pour donner une idée de l'explosion du temps de calcul :
si N = 30!^2 , alors les 810 solutions sont calculées en 0.2 seconde ;
si N = 40!^2 , alors les 20790 solutions sont calculées en 17 secondes ;
si N = 50!^2 , alors les 96390 solutions sont calculées en 345 secondes.