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

décompostion d'une congruence




  1. #1
    kaderben

    décompostion d'une congruence

    Bonjour

    Comment décomposer une congruence de la forme x=a[n]
    Exemple:
    x=4[15] (congruence) équivaut à x=1[3] et x=4[5]

    Je pense bien qu'il y a des conditions sur a et n.

    Je ne trouve rien sur le web !

    Merci d'avance.

    -----


  2. Publicité
  3. #2
    ansset

    Re : décompostion d'une congruence

    pour x=c[N] la décomposition peut se faire avec tous les diviseurs de N ( sauf 1 inutile )
    soit P un diviseur de N et
    x=c[N]
    c=c(P)[P] alors x=c(P)[P]
    dans ton exemple ( je prend tes chiffres, mais on pourrait l'écrire avec des variables )
    x=15k+4
    diviseurs 3 et 5
    x=4[15]
    4=1[3] d'où x=1[3]
    4=4[5] d'où x=4[5]
    Dernière modification par ansset ; 02/01/2019 à 11h40.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  4. #3
    gg0

    Re : décompostion d'une congruence

    Dans l'autre sens, voir le théorème chinois.


  5. #4
    kaderben

    Re : décompostion d'une congruence

    Bonjour

    Oui, j'ai compris !

    4=1[3] d'où x=1[3]
    4=4[5] d'où x=4[5]

    Dans l'autre sens, voir le théorème chinois.
    Comme les modulos 3 et 5 sont premiers entre eux alors on peut appliquer le théorème des restes chinois.
    C'est ce que tu voulais dire gg0 ?

  6. #5
    ansset

    Re : décompostion d'une congruence

    dans l'implication que je donnais, c'est vrai pour tous les diviseurs ( premiers entre eux ou pas )
    ex 15=3[12]
    12=2*2*3
    diviseurs : 2;3;4;6
    2 et 4 ne sont pas premiers entre eux , 3 et 6 non plus.
    pourtant
    3=1[2] et 15=3[2]
    3=0[3] et 15=0[3]
    3=3[4] et 15=3[4]
    3=3[6] et 15=3[6]

    la proposition de gg0 est la démo de l'implication inverse , en utilisant le théorème des restes chinois.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. A voir en vidéo sur Futura
  8. #6
    kaderben

    Re : décompostion d'une congruence

    OK et merci!

    Maintenant quelle est l'intérêt de casser une congruence ?
    Peut être pour, résoudre un système d'équations à une inconnue, avoir des modulos premiers entre eux et appliquer le théorème des restes chinois qui est peut être pratique pour programmer ?

  9. #7
    gg0

    Re : décompostion d'une congruence

    En général, on fait plutôt le contraire. Le théorème des restes chinois est très utilisé pour les maths discrètes (calcul formel, codage, cryptage, ...) car il permet de travailler sur des petits nombres tout en ayant des résultats sur des nombres très grands. Voir calcul formel par Davenport et al.

    Comme c'est toi qui a décidé de parler de "casser une congruence", tu as sans doute des raisons, pourquoi poser la question ?

    Cordialement.

  10. Publicité
  11. #8
    kaderben

    Re : décompostion d'une congruence

    Comme c'est toi qui a décidé de parler de "casser une congruence", tu as sans doute des raisons, pourquoi poser la question ?
    Oui, le but c'est d'écrire un programme pour résoudre des systèmes d'équations à une inconnue genre:ax=b[n] et cx=d[m] et etc...mais je n'est pas une méthode générale.
    Comme j'ai que le niveau terminale, autodidacte,curieux, je regarde sur internet, les forums etc... pour avoir des idées et des choses que je ne comprends pas!

    Toutes ses méthodes sont pour moi un peu floues et je n'arrive pas à faire un peu d'ordre dans ma tête car l'arithmétique modulaire n'est pas si simple !.

  12. #9
    gg0

    Re : décompostion d'une congruence

    Oui,

    mais tu as posé le problème à l'envers !!!
    Si tu veux vraiment traiter ça (faire le programme, car les logiciels de calcul formel le font très facilement), étudie les bases de l'arithmétique (dans un bouquin, Internet c'est pour survoler, ou pour revoir un point particulier) et vois le théorème chinois.

    NB : Ton niveau actuel n'interdit pas d'en changer. En apprenant.

  13. #10
    sylvainc2

    Re : décompostion d'une congruence

    Pour résoudre un système où les moduli sont premiers entre eux (théorème des restes chinois), par exemple:
    x = 2 (mod 3)
    x = 3 (mod 5)
    x = 2 (mod 7)

    on peut résoudre chaque congruence comme ceci séparément puis on additionne les solutions partielles:

    Première congruence:
    on cherche un multiple de 5*7=35 qui est congru à 2 mod 3 c.a.d. on cherche x1 = 35k1 tel que 35k1 = 2 mod 3
    35 et 3 sont premiers entre eux donc il y a une solution. Ce sera toujours le cas puisque les moduli sont premiers entre eux:
    --> k1 = 2* 35-1 mod 3 --> 2*2-1 = 2*2 = 1 mod 3 donc x1=35*1 = 35, et on ne réduit pas x1. Tu peux vérifier que 35 est bien multiple de 5 et 7 et congru à 2 mod 3.

    On fait la même chose pour les deux autres congruences:

    2 - On cherche un multiple de 3*7=21 qui est congru à 3 mod 5 --> x2 = 21 k2 tel que 21 k2 = 3 mod 5
    --> k2 = 3* 21-1 mod 5 --> 3*1-1 = 3 mod 5 donc x2=21*3 = 63

    3- 3*5 = 15: x3 = 15 k3 tel que 15 k3 = 2 mod 7 --> k3 = 2*15-1 = 2*1 = 2 mod 7 --> x3 = 15*2 = 30

    La solution est la somme x1+x2+x3 = 23 mod (3*5*7)

    Donc tu vois qu'il est facile d'écrire un programme qui résoud un système de ce genre, tu a besoin d'une routine qui trouve l'inverse modulaire basé sur l'algo d'Euclide étendu par exemple et puis c'est à peu près tout.

Sur le même thème :

Discussions similaires

  1. Réponses: 3
    Dernier message: 26/09/2010, 17h44
  2. Décompostion en éléments simples
    Par jules345 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 29/05/2010, 20h35
  3. [Evolution] Oeufs d'araignée & mouche morte en décompostion
    Par bordy26 dans le forum Biologie
    Réponses: 7
    Dernier message: 02/09/2009, 10h27
  4. Decompostion facteur premier Spé math S
    Par Jorqs dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 14/01/2008, 19h34
  5. tpe sur la décompostion...besoin d'aide..svp
    Par margotvd dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 18/12/2007, 19h37