Resolution d'equation modulaire

[leon1789]

d'où x = 7 * -8 + 36k x = -56 + 36k

Je vois pas où est l'erreur.
Peux tu m'aider ???

L'erreur était juste après en fait :
x = -56 + 36k x = 16 mod 36 (et non 10 mod 36 ) :zen:

[juve1897]

MERCIII.

Purée une erreur de calcul toute bête.

donc si je comprends bien, il suffit en fait de choisir une solution parmi l'ensemble des solutions possibles de chaque équation et de faire le th. du reste chinois.

Mais si je choisis d'autre solution par ex.


je trouverai une autre solution ??? (je pense que oui)
Comment dans ce cas obtenir toutes les solutions sans calculer toutes les combinaisons possibles ???

[juve1897]

Dans ce cas... Mais sans vouloir jouer les rabat-joie, il ne me semble pas qu'il existe de méthode générale pour trouver des solutions d'équations polynomiales dans , même pour le second degré et pour : il faut disposer d'un algorithme de calcul de racine carrée ce qui n'est pas complètement évident.

Pardon d'avoir interféré, mais je maintiens ce que je répondrais à la question de départ :lol3:

MErci pour tes precisions.

Donc si je comprends ton raisonnement, si j'ai affaire à un petit nombre (tout est relatif) le mieux reste de tester toutes les solutions possibles.

Par ex

je teste avec {0,1,2,3,4,5,6,7,8,9,10,11} jusqu'à ce que je trouve une solution (ou non)

C'est bien ça ???

[leon1789]

MERCIII.

Purée une erreur de calcul toute bête.

donc si je comprends bien, il suffit en fait de choisir une solution parmi l'ensemble des solutions possibles de chaque équation et de faire le th. du reste chinois.

Mais si je choisis d'autre solution par ex.


je trouverai une autre solution ??? (je pense que oui)
Comment dans ce cas obtenir toutes les solutions sans calculer toutes les combinaisons possibles ???

Tu as compris, c'est ok.
Oui, il y a 2 solutions mod 4, et 2 mod 9, donc 2x2 mod 4x9 :
Pour chaque couple de solutions, on sait qu'il y a une (et une seule) solution qui les chapote modulo 36. C'est le théorème chinois.

[juve1897]

Tu as compris, c'est ok.
Oui, il y a 2 solutions mod 4, et 2 mod 9, donc 2x2 mod 4x9 :
Pour chaque couple de solutions, on sait qu'il y a une (et une seule) solution qui les chapote modulo 36. C'est le théorème chinois.

Oui mais dans ce cas si il y'avait 4 solutions pour l'eq 1 et 6 solutions pour la 2, j'aurais du calculer avec tous les couples possible pour avoir TOUTES les solutions de l'eqaution ???

[leon1789]

Oui mais dans ce cas si il y'avait 4 solutions pour l'eq 1 et 6 solutions pour la 2, j'aurais du calculer avec tous les couples possible pour avoir TOUTES les solutions de l'eqaution ???

Oui... Certes, c'est pas terrible.
Il y a peut-être un truc intelligent à faire dans ce cas. Mais je ne sais pas quoi. Et cela m'intéresserait.

[juve1897]

Oui... Certes, c'est pas terrible.
Il y a peut-être un truc intelligent à faire dans ce cas. Mais je ne sais pas quoi. Et cela m'intéresserait.

oui moi aussi, car justement dans cet exo, on demandait de trouver TOUTES les solutions de l'équation. C'est assez long si l'on a plusieurs couple à tester.

Et encore là nous avons seulement des couples, nous aurions pu avoir un triplet ou un quadruplet ...

Mais la méthode précédemment donnée (méthode brute) prend elle aussi un certain temps (tester 36 valeurs !!)

[Doraki]

si x = a mod A et x = b mod B (A et B premiers entre eux)
et si tu connais C l'inverse de B modulo A, tu as BC qui vaut 0 modulo B et 1 modulo A.
Après c'est facile de calculer une solution modulo AB en prenant
x = b*(1-BC) + a*BC.
Il faut calculer pour chaque couple, mais c'est rapide.

C'est toujours avantageux de regarder les solutions dans Z/9Z et Z/4Z (13 cas plus petits à tester au lieu de 36 à faire modulo 36) surtout si l'équation est compliquée.

[leon1789]

Mais la méthode précédemment donnée (méthode brute) prend elle aussi un certain temps (tester 36 valeurs !!)

36 valeurs car une seule variable, mais avec deux ou trois variables, ce serait 36^2 couples ou 36^3 triplets...

[leon1789]

si x = a mod A et x = b mod B (A et B premiers entre eux)
et si tu connais C l'inverse de B modulo A, tu as BC qui vaut 0 modulo B et 1 modulo A.
Après c'est facile de calculer une solution modulo AB en prenant
x = b*(1-BC) + a*BC.
Il faut calculer pour chaque couple, mais c'est rapide.

oui, c'est le théorème chinois :zen:

[juve1897]

Et ben dit donc alors !

Mais mon prof nous a dit que dans la plus part des cas les équations (modulaires) de degrés supérieur à 2 ont rarement des solutions .

Donc je vais continuer à faire ma methode de reste chinois.

Par contre si le n est premier, sommes nous obligés dans ce cas de tester toutes les valeurs ???

[leon1789]

Par contre si le n est premier, sommes nous obligés dans ce cas de tester toutes les valeurs ???

ben je ne sais pas, pour moi ça dépend des équations...

[juve1897]

Ben j'essayerai de voir dans ce cas là.

Merci pour ton aide en tous cas ;)

[busard_des_roseaux]

bjr,


pour les équations du second degré, vous pouvez toujours calculer
le discriminant et regarder par la formule de réciprocité quadratique (Gauss) si est un carré.

après on factorise (on peut faire des multiplications dans l'anneau Z/nZ)

si n est premier, Z/nZ est un corps, on trouve les solutions.

si n n'est pas premier, comme on doit résoudre une équation produit,
on rajoute les diviseurs de zéro

par ex, dans

pour les équations de degré 3 et 4 , on doit pouvoir s'inspirer
des formules de Cardan et Ferrari.
regarder si est un cube (modulo n).

[leon1789]

busard_des_roseaux,
pour espérer appliquer les formules classiques, il faut absolument une caractéristique distincte de 2 et que le coefficient du x^2 soit inversible.
Et même si le est un carré, il reste à trouver toutes les racines carrées de ...

Pour les équations de degré 3 ou 4, c'est pas mieux...