Système de congruences — Les-mathematiques.net The most powerful custom community solution in the world

Système de congruences

Niko04Niko04
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

Réponses

  • Fin de partieFin de partie
    Si z et d sont premiers entre eux cela facilite le travail.
  • michaelmichael
    Salut,

    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).
  • noix de totosnoix de totos
    Effectivement, si $z$ et $d$ sont premiers entre eux, c'est le théorème chinois. Sinon, je confirme les propos de Michael, mais c'est dans le second livre de Bordellès, Arithmetic Tales (Springer, 2012), que j'ai trouvé cette explication (p. 41, Remark 3).
  • nicolas.patroisnicolas.patrois
    Voici un code en Python qui fait le taf :
    def prod(l):
 p=1
 for e in l:
  p*=e
 return p

def bezout(n,a):
 r,u,rr,uu=a,1,n,0
 while rr:
  q=r//rr
  r,u,rr,uu=rr,uu,r-q*rr,u-q*uu
 return u%n

def pgcd(a,b):
 a,b=max(a,b),min(a,b)
 while a:
  b,a=a,b%a
 return b

def trc(l):
 p=pgcd(l[0][1],l[1][1])
 if (l[0][0]-l[1][0])%p:
  return None
 n=prod([a[1] for a in l])
 q=[n//l[k][1] for k in range(len(l))]
 v=[bezout(l[k][1],q[k]) for k in range(len(l))]
 return sum([l[j][0]*q[j]*v[j] for j in range(len(l))])%n//p
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • nodgimnodgim
    Perso, pour la recherche des solutions de ce système :

    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.
  • michaelmichael
    Merci pour la confirmation, noix de totos. N'ayant jamais lu le deuxième bouquin d'Olivier Bordellès, j'ai vu ça bien fait ailleurs. Probablement dans Arithmétique dans Z et dans K[X] de Mohammed El Amrani. Mais comme je l'ai prêté, impossible de vérifier.
  • Al-KashiAl-Kashi
    Bonjour,

    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
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!