Système de congruences
dans Arithmétique
Bonjour
Je cherche à résoudre un problème du type suivant.
x congru à y [z]
x congru à c [d]
(avec y, z, c et d des entiers)
J'aimerais connaître la méthode à suivre...
Merci par avance
Je cherche à résoudre un problème du type suivant.
x congru à y [z]
x congru à c [d]
(avec y, z, c et d des entiers)
J'aimerais connaître la méthode à suivre...
Merci par avance
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
si $z$ et $d$ sont premiers entre eux :
1. Trouver une solution particulière $x_0$ à l'aide d'une identité de Bézout.
2. Trouver toutes les solutions par la "méthode des différences" : soit $x$ une solution quelconque du système, écrire le système de congruences vérifié par $x-x_0$, en déduire la "forme" de $x-x_0$ puis l'ensemble de toutes les solutions du système.
Si $d$ et $z$ ne sont pas premiers entre eux, le système admet des solutions si et seulement si $y$ et $c$ sont congrus modulo le pgcd de $d$ et $z$.
Dans ce cas, on montre (méthode de la différence) que l'ensemble des solutions est $x_0 + ppcm(d,z) \mathbb{Z}$ où $x_0$ est une solution du système.
Dans mes souvenirs, c'est bien expliqué dans Thèmes d'arithmétique d'Olivier Bordellès (à confirmer, je n'ai pas le bouquin à proximité pour vérifier).
-- Schnoebelen, Philippe
x = a n + b = c m + d............................ ( c'est à dire x = b [n] et x = d [m], on suppose n et m premiers entre eux)
Je procède de cette façon :
Comme :.................a * n - c * m = d - b
On cherche d'abord a0 tel que ........a0 * n = 1 [m].........c'est à dire l'inverse de n [m].
qui est rapide à trouver.
Ensuite c0 tel que c0 * m = 1 [n] tombe immédiatement puisque c'est (a0*n - 1) / m.
D'où on obtient..................... a0 * n - c0 * m = 1
D'où on tire alors:................. a = (d-b) * a0 [m].......... et........... c = (d-b) * c0 [n]
C'est à peine plus long si n et m ne sont pas premiers entre eux.
On peut aussi voir les choses ainsi:
Soit $p$ et $q$ deux entiers premiers entre eux.
On considère le système : $x \equiv a (p) $ et $x \equiv b (q) $.
On peut alors écrire $x=a+pk$. En injectant dans la deuxième on a alors:$a+pk\equiv b (q) $, soit donc $k\equiv (b-a)p^{-1} (q) $.
L'ensemble des solutions dans $\Z$ est donc $$x_i=a+p(p^{-1}) _q(b-a)+pqi$$ où $i$ parcourt $\Z$.
Ainsi le problème revient à déterminer un inverse modulaire.
Al-Kashi