Système de congruence

[invite8ddf47f1]

Bonjour,

Je fais un exercice corrigé où l'on doit résoudre le système suivant :
􏰅 x≡1 [6]
􏰆 x≡2 [7]

Voici la correction avec à côté mes questions :

6 et 7 sont premiers entre eux avec la relation de Bézout (−1) × 6 + (1) x 7 = 1. // OK
x1 = 7 et x2 = −6 sont solutions des systèmes // Comment ça ?
􏰅
On écrit ensuite de
x≡1 [6] et 􏰅x≡0 [6] // Comment on est passé à ça ?
x≡0 [7] et x≡1 [7]


donc x = 1 × 7 + 2 × (−6) = −5 est solution du système étudié dont la solution générale est alors
x = 37 + 42k avec k ∈ Z

D'ou sort le 37 ?


Quelqu'un saurai m'éclaircir un peu cette résolution s'il vous plaît ?
-----

[invite8ab5fa54]

Bonjour ,
Es-tu sûr d'avoir bien recopié l'énoncé et/ou la correction ? Ni 7 ni -6 sont solutions de ce système.

[sylvainc2]

Le 37 vient du fait qu'on te dit que la solution est x=-5 mais en fait c'est -5 mod 42 (42 est le produit des moduli 6 et 7) et effectivement -5 = 37 mod 42.

Mais je n'ai pas très bien compris comment le corrigé en arrive là. Normalement, on utilise le théorème des restes chinois (je pense que ca s'appelle l'algorithme de Gauss pour résoudre le trc). Ca marche comme ceci:

Pour résoudre le système:
x=1 mod 6
x=2 mod 7

1 - On cherche un multiple de 7 (le 2e modulo) qui est congru à 1 mod 6 c.a.d. on cherche x₁ = 7k₁ tel que 7k₁ = 1 mod 6
--> k₁ = 1*7^-1 = 1*1^-1 = 1 mod 6 donc x₁=7*1 = 7 (on ne réduit pas x₁, on le garde tel quel).

2- On cherche un multiple de 6 qui est congru à 2 mod 7: x₂ = 6k₂ tel que 6k₂ = 2 mod 7 --> k₂ = 2*6^-1 = 2*6 =12 = 5 mod 7 (car 6^-1 = 6 mod 7) donc x₂ = 6*5 = 30.

La solution du système est la somme x₁ + x₂ mod 42 donc 7+30 = 37 mod 42.