Forum de mathématiques - Bibm@th.net

fadara

Membre

Inscription : 03-12-2009

Messages : 23

Systèmes de congruences

Bonsoir,
J'ai besoin d'aide sur un exercice.
Soient a, b, c, d, e, f et m des entiers avec [tex]m > 0[/tex] tels que [tex]pgcd(\Delta , m) = 1  avec   \Delta = ad - bc[/tex]
Montrer que le système de congruences
[tex]ax + by \equiv e[m][/tex]
[tex]cx + dy \equiv f[m][/tex]
admet une unique solution
[tex]x \equiv \overline{\Delta}(de -bf)[m][/tex]
[tex]y \equiv \overline{\Delta}(af - ce)[m][/tex]
Je dois d'abord montrer qu'une solution du système est sous la forme donnée et pour montrer l'unicité, je prends 2 couples de solutions [tex](x, y)  et  (x', y')[/tex] et je montre qu'ils sont égaux.
J'ai besoin d'aide pour le faire.
Merci

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Systèmes de congruences

Bonjour Fadara,

  J'imagine que [tex]\bar\Delta[/tex] est l'inverse de [tex]\Delta[/tex] modulo m....
Vérifier que ce que l'on te donne est effectivement une solution ne pose pas de problèmes particuliers.
Il suffit simplement de remplacer x et y par les valeurs données, il y a les bonnes simplifications qui se produisent, etc.... Si tu n'y arrives pas, écris nous le début de tes calculs et là où tu bloques.

Pour l'unicité, tu peux simplement résoudre le système pratiquement comme si c'était un système usuel.
Imaginons que x et y sont solutions, alors on multiplie par d la première ligne et par b la seconde, et on fait la différence. On trouve :

[tex](ad-bc)x=de-bf[m][/tex]
Et puis tu multiplies par l'inverse de ad-bc, et tu trouves que x a forcément la valeur voulue.

Fred.

fadara

Membre

Inscription : 03-12-2009

Messages : 23

Re : Systèmes de congruences

Bonsoir,
Excusez moi pour le long laps de temps avant mon post
Pour la résolution du système, en suivant tes conseils
En multipliant la 1ere ligne par d et la seconde par b, j'obtiens
[tex]dax - bcx \equiv (ed - bf)[m][/tex]
[tex](ad - bc)x \equiv (ed - bf)[m][/tex]
[tex]\Delta x \equiv (ed - bf)[m][/tex]
Comme [tex]\Delta[/tex] est inversible, je peux écrire
[tex]\Delta\overline{\Delta}x \equiv \overline{\Delta}(ed - bf)[m][/tex]
Ce qui me donne [tex]x \equiv \overline{\Delta}(ed - bf)[m][/tex]
J'ai fais la même chose en multipliant la 1ère équation par c et la seconde par a pour obtenir y

Pour vérifier s'ils sont vraiment solution
[tex]ax + by \equiv [/tex] [tex]a(\overline{\Delta}(ed - bf)) + b((\overline{\Delta}(af - ec))[/tex]
              [tex]\equiv \overline{\Delta}(aed - abf + baf - bec)[/tex]
              [tex]\equiv \overline{\Delta}(e(ad - bc))[/tex]
              [tex]\equiv \Delta\overline{\Delta}e[/tex]
              [tex]\equiv e[m][/tex]

La même chose avec la seconde équation

Merci

Dernière modification par fadara (19-01-2010 03:09:07)