Comparaisons et restes chinois

Bonjour à tous, je suis à la recherche d'articles ou de résultats intéressants concernant le problème suivant.

Étant donnés deux nombres $x$ et $y$, et un ensemble de nombres premiers impairs $m_1,\dots, m_n$, comment puis-je savoir "efficacement" si $x<y$ à partir de leurs restes modulo les $m_i$, sans recomposer les nombres entiers $x$ et $y$ sous-jacents ?

Exemple au hasard.
J'ai $x<37\times 41$ tel que $x\mod 37 = 14$ et $x\mod 41 = 9$,
$\hspace{2.35cm}y$ tel que $y\mod 37 = 11$ et $y\mod 41 = 33$.
Quel est le meilleur moyen de déterminer si $x<y$ ?

Résultat déjà connu : c'est équivalent à déterminer si un nombre est pair à partir de ses résidus (laissé en exercice au lecteur :D )

Réponses

  • salut
    Si tu as x=ri modulo mi et y=r'i modulo mi alors x-y= (ri-r'i) modulo mi et le tthoreme des restes chinois te dit que le problème admet une solution unique modulo le produit des mi si tu trouve x-y tu saura si x-y est positif ou negatif
    Si je me trompe donne un exemple précis de ce que tu cherches
Connectez-vous ou Inscrivez-vous pour répondre.