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

Théorème des restes chinois



  1. #1
    loic7

    Théorème des restes chinois


    ------

    Bonjour j'ai un petit soucis sur un exercice :

    Combien l'armée de Han Xing comporte-t-elle de soldats si, rangés par 3 colonnes, il reste deux soldats, rangés par 5 colonnes, il reste trois soldats et, rangés par 7 colonnes, il reste deux soldats ?

    On a le système suivant :

    x=2[3]
    x=3[5]
    x=2[7]


    On a alors : x= u(1)*3*5*2+u(2)*3*7*3+u(3)*5*7 *2+n*3*5*7

    Le but est alors de trouver u(1),u(2) et u(3)

    On a 15=7*2+1 ==> 1=15-7*2 d'ou u(1)=1

    35=3*11+2
    11=2*5+1
    ==> 1=11-2*5=11-5*(35-3*11)=11*16-5*35 d'où u(3)=-5

    21=5*4+1
    ==>1=21-5*4 d'où u(2)=1

    on a x=3*5*2+3*7*2-5*5*7*2+n*3*5*7= GROS PROBLEME J'AI QUELQUE CHOSE DE NEGATIF

    -----

  2. Publicité
  3. #2
    Katatsumuri

    Re : Théorème reste chinois

    Bonjour,
    Trouver un résultat négatif n'est pas bien grave quand on travaille avec des modulo : tu ajoutes autant de fois 3*5*7 que nécessaire pour que ce soit positif. Ce qui compte, c'est que ton x vérifie bien ton système de départ...
    Et là par contre j'ai des doutes. Si je ne me suis pas trompé, tu trouves 37 modulo 105 alors que tu devrais trouver 23 modulo 105 (encore une fois, je peux me planter). Es-tu sûr d'avoir bien appliqué ton cours sans erreur ?

  4. #3
    loic7

    Re : Théorème des restes chinois

    on a x=3*5*2+3*7*3-5*5*7*2+n*3*5*7= -257 + 105 n

    Quelqu'un voit-il une erreur ou pas?

  5. #4
    Katatsumuri

    Re : Théorème des restes chinois

    -257+3*105=58

    Or 58= 7*8+2 = 2 modulo 7
    58= 5*11+3 = 3 modulo 5
    58= 3*19+1 = 1 modulo 3

    Donc il y a une erreur.
    Je pense que c'est la formule du x qui est fausse... (si mes souvenirs sont bons...)

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

    Re : Théorème des restes chinois

    x = 2 mod 3:

    L'idée est de chercher un multiple des 2 autres moduli , ici 5*7=35, qui en même temps est congru à 2 mod 3, ie on cherche:
    35k1 = 2 mod 3
    La raison est que ce nombre, 35k1, est un multiple de 5 et de 7 donc il n'affecte pas les 2 autres congruences, il est 'neutre": 35k1=0 mod 5 et 35k1=0 mod 7.

    Donc k1 = 35^-1 * 2 mod 3
    = 2^-1 * 2 mod 3
    = 2 *2 mod 3
    = 1 mod 3
    Donc u(1)=35*1 = 35

    On fait la même chose pour les 2 autres congruences:
    on cherche un multiple de 21 qui est congru à 3 mod 5:
    21k2 = 3 mod 5
    k2 = 21^-1 * 3 mod 5
    = 1 * 3 mod 5
    Donc u(2)=21*3 = 63

    15k3 = 2 mod 7
    k3 = 15^-1 * 2 mod 7
    k3 = 1 * 2
    donc u(3)=15*2 = 30

    Alors x = 35+63+30 = 128 = 23 mod 105

Discussions similaires

  1. théorème des restes chinois
    Par qubits dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 09/01/2010, 21h13
  2. theoreme des restes chinois
    Par visiteur33 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 09/06/2008, 18h05
  3. 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
  4. 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
  5. Théorême des restes chinois
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 26/04/2005, 01h01