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 !
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.
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,
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
@+
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.
@+
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.
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
[...]
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 ?
Tu as trouvé une des valeurs possibles de n mais ce n'est pas la seule. 14 marche aussi par exemple.Envoyé par dolmen
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,
Merci Mmy pour ta réponse
A bientôt
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
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.
Merci beaucoup !
@+
