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

inverse du modulo



  1. #1
    dolmen

    inverse du modulo


    ------

    Bonjour à tous,

    je voudrai savoir quelle est "la fonction inverse du modulo".

    C'est à dire que quand on a congru à c modulo m, comment peut on trouver a sans faire des "tests" mais en connaissant b et m ?

    Plus précisément (ce qui est mon problème), comment connaître x dans la formule :
    ax + b congru à c modulo m ? en connaissant a, b, c et m.

    Merci de m'éclairer !

    -----
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  2. Publicité
  3. #2
    prgasp77

    Re : inverse du modulo

    En repartant de la définition de la congruence, il trouve qu'il existe une infinité dénombrable de solution. Soit E l'ensemble de ces solutions : E = {(mn-b-c)/a, n€Z}.

    Mais il ne s'agit pas d'une fonction inverse. Le modulo inverse existe, mais n'a pas grand chose en commun.
    --Yankel Scialom

  4. #3
    invité576543
    Invité

    Re : inverse du modulo

    Avec une petite subtilité quand même, si les solutions recherchées sont des nombres entiers!

    En gros si a est premier avec m, alors il existe a' tel que aa' = 1 modulo m, et les solutions sont alors (a'(mn+c-b), n dans Z).

    Si a n'est pas premier avec m, alors il n'y a des solutions que si pgcd(a, m) divise b-c. En divisant tout par ledit pgcd on se retrouve dans le cas précédent...

    Cordialement,

  5. #4
    dolmen

    Re : inverse du modulo

    Merci pour ta réponse prgasp77 !

    Le problème avec ta formule E = {(mn-b-c)/a, n€Z}, c'est qu'il y a 2 inconues :
    -le x qu'on recherche
    -et le n.
    Alors comment faire ?

    De plus je ne trouve pas la même formule que toi,prgasp77, je trouve E = {(mn-b+c)/a, n€Z}
    car : ax + b congru à c modulo m équivaut à ax + b = nm + c
    ax + b = nm + c
    ax = nm + c - b
    x = (nm + c - b)/a

    @+
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  6. #5
    dolmen

    Re : inverse du modulo

    Merci pour ta réponse mmy !

    En effet, les solutions recherchées sont des nombres entiers.
    Je vais tenter de bien comprendre ton résonnement.

    @+
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

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

    Re : inverse du modulo

    En fait le véritable problème est qu'on a 2 inconues n et x.

    x = (nm + c - b)/a

    Je ne vois pas comment trouver x sans tester toutes les valeurs possibles de n pour que (nm + c - b)/a soit entier. C'est cela mon vrai problème.
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  9. Publicité
  10. #7
    prgasp77

    Re : inverse du modulo

    Pour le signe de c, tu as raison. Quand à n, il ne s'agit pas d'une inconnue, mais d'un paramètre. x peut prendre une infinité de valeur : une valeur possible pour chaque valeur de n possible.

    [...]
    Pour n=-2, x=(-2m + c - b)/a
    Pour n=-1, x=(-m + c - b)/a
    Pour n=0, x=(c - b)/a
    Pour n=1, x=(m + c - b)/a
    Pour n=2, x=(2m + c - b)/a
    [...]
    --Yankel Scialom

  11. #8
    dolmen

    Re : inverse du modulo

    Merci beaucoup prgasp77 pour ta réponse.

    Je comprend que x peut prendre une infinité de valeur mais existe t'il une fonction pour trouver x pour que x soir un entier.
    Dans ton exemple tu as imposer le "n" (ex : Pour n=-2, x=(-2m + c - b)/a)
    Mais si on ne connait pas n, comment fais ton pour trouver x ?

    Par exemple :

    ax + b congru à c modulo m
    a = 26
    b = 3
    c = 17
    m = 38

    Comment trouver x ? Quelle est la fonction qui permet de trouver x un entier ?

    En effet, si on utilise la formule :
    x = (nm + c - b)/a
    Cela donne :
    x = 38n + 17 - 3 / 26

    Par tests, on voit que n doit être égal à 1
    Ce qui nous donne que x = 2

    Mais sans tests, n'y a t'il pas une vrai formule ?
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  12. #9
    invité576543
    Invité

    Re : inverse du modulo

    Citation Envoyé par dolmen Voir le message
    Comment trouver x ? Quelle est la fonction qui permet de trouver x un entier ?

    En effet, si on utilise la formule :
    x = (nm + c - b)/a
    Cela donne :
    x = 38n + 17 - 3 / 26

    Par tests, on voit que n doit être égal à 1
    Tu as trouvé une des valeurs possibles de n mais ce n'est pas la seule. 14 marche aussi par exemple.

    Quand on a trouvé une solution (quelle que soit la méthode), une méthode simple pour trouver les autres est de prendre la différence comme nouvelle inconnue. Ici on écrit n = 1 + m, 1 étant la solution trouvée.

    Cela donne x = (38 + 38m +17-3)/26 = ...

    Facile de trouver les m acceptables...

    Cordialement,

  13. #10
    dolmen

    Re : inverse du modulo

    Merci Mmy pour ta réponse , maintenant je pense avoir compris, n peut prendre plusieurs valeurs donc x aussi. Il n'y a donc pas de fonction pour trouver x.

    A bientôt
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  14. #11
    prgasp77

    Re : inverse du modulo

    Citation Envoyé par dolmen Voir le message
    Comment trouver x ? Quelle est la fonction qui permet de trouver x un entier ?
    En réalité, cela est impossible : car nous n'avons pas à faire à une bijection, ie il existe une infinité de x telle que ax+b congru à c modulo m.

    Pour te donner un exemple simple, étudions la fonction entière E qui eu réel x associe le plus grand entier inérieur à x. E(3,1) = 3, E(3,9) = 3, E(1) = 1, E(-2,3) = -3, E(-pi) = -4 ... Maintenant, admétons que je te dise que E(x) = 3, peux-tu me donner LA valeur de x ? Non, c'est impossible, tout ce que tu peux me dire avec certitude c'est que 3 <= x < 4

    Mais peut être que si tu nous donnais un peu plus d'informations ...
    Allez, bonne chance dans ets traveaux
    Dernière modification par prgasp77 ; 07/01/2007 à 14h36.
    --Yankel Scialom

  15. #12
    dolmen

    Talking Re : inverse du modulo

    Merci beaucoup pour ta réponse prgasp77 !

    Je pense que toi et Mmy, vous avez répondu à mon problème : il existe une infinité de x telle que ax+b congru à c modulo m donc pas de fonction possible. La fontion que j'ai appelée "inverse du modulo" n'existe donc pas.

    Citation Envoyé par prgasp77
    Allez, bonne chance dans tes travaux
    Merci beaucoup !

    @+
    Aussi haute que soit la montagne, on y trouve toujours un sentier .

  16. Publicité

Sur le même thème :

Discussions similaires

  1. Equation, modulo 4
    Par bastien90210 dans le forum Mathématiques du collège et du lycée
    Réponses: 12
    Dernier message: 10/10/2007, 21h38
  2. modulo
    Par dim756 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 31/08/2007, 21h47
  3. Formule de modulo
    Par Hachem dans le forum Mathématiques du supérieur
    Réponses: 17
    Dernier message: 14/12/2006, 18h28
  4. modulo
    Par carl159 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 11/08/2006, 09h08
  5. fonction modulo
    Par Brumaire dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 06/11/2004, 12h06