Modulo et retournement

[Elnorth]

Bonjour,

J'ai une expression du modulo :

xv + w = y modulo n

Dans l'exercice, on nous demande d'inverser la formule, seulement avec les exemples donnés (pour vérifier si elle est valide, les résultats sont toujours faux).

En d'autres termes, je cherche à retrouver x connaissant y, v, w et n.

Merci d'avance !

[Clembou]

Bonjour,

J'ai une expression du modulo :

xv + w = y modulo n

Dans l'exercice, on nous demande d'inverser la formule, seulement avec les exemples donnés (pour vérifier si elle est valide, les résultats sont toujours faux).

En d'autres termes, je cherche à retrouver x connaissant y, v, w et n.

Merci d'avance !

Si j'ai bien compris ton équation est ça :


Tu passe le w de l'autre côté, cela donne :


Et ça revient à résoudre une équation diophantienne simple :

[Elnorth]

J'avais remarqué cette solution, mais elle ne donne pas directement la valeur de x :/

J'ai aussi oublié de préciser qu'il existait une fonction C qui est définie par le reste de la division euclidienne de (xv + w) par n. Et que l'on cherche au finale une fonction D qui se charge de trouver y. En gros : D(C(x)) = x.

De plus, 0 <= x <= n et 0 <= y <= n :/ Je me suis cassé la tête plus de 2 jours sur le problème, ça commence à être limite loufoque :s

[maturin]

et

est-ce que tu travailles avec des nombres entiers ?
as tu des relations entre v,w,n ?

[yos]

de vx=a (n), on multiplie les deux membres par un inverse de v modulo n, c'est-à-dire un entier k tel que kv=1 (n) . L'existence d'un tel entier est la condition d'existence d'une solution.
Par exemple pour 14x=30 (5), on multiplie par 4 qui est un inverse de 14 modulo 5.

[Elnorth]

Je n'ai pas compris la seconde solution ... :s

D'après ce que tu dis : a = y - w. Donc, j'ai essayé en multipliant les deux nombres par l'inverse (noté également k) :

xv = a [n]
kv = 1 [n]

On se retrouve avec un système :

kv = 1 [n] <> kv = 1 + nb <> v(k-x) = 1 + a + n(b-b')
xv = a [n] <> xv = a + nb' <> v(k-x) - n(b-b') = 1 + a

On se retrouve donc dans la même situation qu'au départ, c'est à dire que nous avons une équation à résoudre. La solution n'est donc pas immédiate comme souhaitée dans le sujet :s

----
de vx=a (n), on multiplie les deux membres par un inverse de v modulo n, c'est-à-dire un entier k tel que kv=1 (n) . L'existence d'un tel entier est la condition d'existence d'une solution.
----
Je ne cherche pas non plus à prouver une solution mais plutôt à trouver une formule permettant de calculer la solution connaissant y :/

[yos]

Qu'est-ce que tu me fais? C'est comme pour les équations en classe de cinquième :
xv=a (n) donc xvk=ak (n) donc x=ak (n) (car vk=1 mod (n)).