Répondre à la discussion
Affichage des résultats 1 à 8 sur 8

Théorême des restes chinois



  1. #1
    Brumaire

    Théorême des restes chinois


    ------

    Bonjour,

    J'ai la définition suivante du théorêmes des restes chinois:

    Théorème : Prenons m1, ..., mn des entiers supérieurs à 2 deux à deux premiers entre eux, et a1,...,an des entiers. Le système d'équations :
    x=a1 mod m1
    ...
    x=an mod mn
    admet une unique solution modulo M=m1×...×mn donnée par la formule :
    x=a1M1y1+...+anMnyn mod M
    où Mi=M/mi, et yi=Mi-1 mod mi pour i compris entre 1 et n.

    Maintenant, j'essaie de l'appliquer pour résoudre un système de congruences:

    x =^ 1 mod 3
    x =^ 2 mod 4
    x =^ 3 mod 5
    x =^ 4 mod 7
    3, 4, 5 et 7 sont bien deux à deux premiers
    On a une solution x = (1*M_1*y_1)+(2*M_2*y_2)+ (3*M_3*y_3)+(4*M_4*y_4) mod 420
    Maintenant je cherche à déterminer M_1, M_2, M_3, M_4
    En principe M_1 = M/m_1 = 420/m_1.

    m_1 est-il égal à 3 ? m_2 = 4? m_3 = 5? m_4 = 7?
    Si tel est le cas, faudrait-il appliquer l'algorithme d'Euclide à M_1 et 3??? (M_1 et 3 sont alors premiers entre eux)

    Cela me ferait plaisir d'avoir plus d'explications...J'ai l'impression d'avoir mal compris le principe de ce théorême.
    Merci d'avance,

    -----

  2. Publicité
  3. #2
    Antikhippe

    Re : Théorême des restes chinois

    Salut,

    Est-ce-que t'as le Soulami, par hasard ?

    Parce que là-dedans, c'est très bien expliqué...

  4. #3
    Brumaire

    Re : Théorême des restes chinois

    Non, je ne l'ai pas. Pourrais-tu éventuellement me scanner la page en question ou m'expliquer rapidement comment procéder pour que tout le monde en profite?

  5. #4
    Antikhippe

    Re : Théorême des restes chinois

    Aïe... Le problème, c'est que mon scanner est en panne et de toutes façons, j'ai prété le livre à un ami...

    Je ne me souviens plus de grand chose sur ce théorème...

    Je vais voir ce que je peux faire.

  6. A voir en vidéo sur Futura
  7. #5
    Antikhippe

    Re : Théorême des restes chinois

    Voici un exemple :

    Soit le système :
    x 0 [3]
    x 1 [5]
    x 7 [8]

    Toutes les solutions de ce système sont congrues à 111 modulo 120.

  8. #6
    GuYem

    Re : Théorême des restes chinois

    Dans le théroème des restes chinois, les coefficients cherchés sont souvent donnés par la relation de Bezout, écrite autant de fois que nécessaire entre tous les couples de nombres premiers entre eux que l'on te donne.
    Si tu veux les calculer effectivement, il faudra faire du Euclide en effet; comme à chaque fois que tu veux trouver les fameux coeff de Bezout.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  9. Publicité
  10. #7
    evariste_galois

    Re : Théorême des restes chinois

    Le thorème chinois peut s'énoncer d'une autre manière, peut-être plus claire (quoique !).

    Notons Z/nZ l'ensemble des classes d'équivalence pour la relation de congruence modulo n.

    Si a et b sont premiers entre eux, alors il existe un isomorphisme f: Z/abZ->Z/aZ X Z/bZ (X représente le produit cartésien de deux ensembles).

    Plus génèralement, soient a1, a2, ..., an n entiers premiers entre eux deux à deux, alors il existe un isomorphisme f: Z/aZ-> Z/a1Z X Z/a2Z X .... XZ/anZ , ou a=a1*a2*...*an .
    "Au train où vont les choses, les choses où vont les trains ne seront plus des gares."

  11. #8
    Brumaire

    Re : Théorême des restes chinois

    Merci pour les explications complémentaires. Finalement, avec de l'ordre, de la méthode et du calme, ca ne coupait pas la queue aux grenouilles, comme on dit dans ma famille!

Discussions similaires

  1. Théorème chinois & un peu d'arithmétique
    Par MiMoiMolette dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 26/10/2007, 13h28
  2. Théorème des restes chinois
    Par invite43219988 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 21/10/2007, 12h21
  3. Théorème chinois des restes
    Par Cieletmer dans le forum Mathématiques du collège et du lycée
    Réponses: 2
    Dernier message: 05/01/2007, 16h37
  4. Restes (Séries)
    Par nassoufa_02 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 09/10/2006, 12h39
  5. Les condamnés à mort chinois : des réservoirs d'organes ?
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 72
    Dernier message: 28/04/2006, 14h04