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.
--Yankel Scialom
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
[...]
--Yankel Scialom
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
Dernière modification par prgasp77 ; 07/01/2007 à 13h36.
--Yankel Scialom
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 !
@+
