Equation (arithmétique)

[g_h]

Bonjour,

Imaginons que je doive résoudre l'équation (au hasard

x² = 15 mod 77 (on calcule assez vite que 15 est bien un carré mod 77)

cette équation équivaut au système x² = 15 mod 7 et x² = 15 mod 11

donc au final, on résout un système chinois, et je trouve +/-13 et +/-57 comme solutions (modulo 77)

Je me demandais alors : si on doit résoudre :
x² = m mod n
si m est un carré modulo n, on a bien des solutions, et ma question porte sur le nombre de solutions : combien y en a-t-il ?
Si j'ai bien compris, la parité de n nous pourrit un peu le boulot, donc dans un premier temps, on suppose que n est impair.
Si n est un produit de k facteurs p_i^a_i avec p premier, j'ai l'impression qu'il y a 2[exp]k[exp] solutions... est-ce vraiment le cas en toute généralité ?

J'ai juste peur de me mélanger un peu les pinceaux (peut-on trouver 2 fois la même solution en résolvant l'équation ?), mais un "oui" ou "non" me suffira amplement si la raison est trop longue pour être détaillée (même si j'ai bien l'impression que c'est oui et que c'est évident... !)

Merci !
-----

[invite986312212]

salut,

la question que tu poses est classique et son traitement par Gauss est resté célèbre. Tu trouveras des éléments ici: http://fr.wikipedia.org/wiki/Loi_de_...A9_quadratique

[invite642cafc1]

La question semble plus poser sur le nombre de solutions à une équation quadratique x²=m (mod q) que sur la résolubilité de celle-ci.
Le théorème le plus utile ici est : soit où les p_i sont des premiers distincts alors, en posant le morphisme est un isomorphisme (avec l'abus de notation où désigne la classe dans divers quotients mais je pense que cela reste compréhensible).
Que ce soit un morphisme est aisé, comme ce sont des anneaux finis il suffit de montrer que c'est injectif ce qui revient à montrer que le noyau est réduit à {e} ce qui revient simplement à si un nombre est divisible par des facteurs premiers entre eux alors il est divisible par leur produit.
Ainsi, il y a une bijection entre l'ensemble des solutions à la 1ère équation et le produit de l'ensemble des solutions. La réponse est donc oui à la question posée (supposant qu'il y a au moins une solution).
La réponse comporte plus de cas si 2 est dans la décomposition mais le principe du calcul du nombre de solutions simplement le nombre de solutions à la "sous-équation" x²=m (mod 2 puissance truc) n'est pas en général 2 (on suppose là encore qu'il y a au moins une solution).

[invite642cafc1]

Oups, je ne sais pas pourquoi je n'ai considéré que le cas où m est premier avec q.
Ce qui reste vrai est que si S est l'ensemble des solutions de x²=m (mod q) et Si l'ensemble des solutions de l'équation induite x²=m (mod qi) alors le morphisme f définit une bijection entre S et le produit ensembliste des Si.
Par exemple 10 est un carré modulo 15=3x5. L'équation x²=10 (mod 3) i.e. x²=1 (mod 3) a deux solutions les classes de 1 et de 2. L'équation x²=10 (mod 5) i.e. x²=0 mod 5 a une unique solution les multiples de 5. L'équation x²=10 (mod 15) admet 2=2x1 solutions, les classes modulo 15 de 5 et de 10, et non 4.

[A voir en vidéo sur Futura]