Système de congruences

Zazoux
Zazoux
dans Arithmétique
Bonjour à tous,

mon problème est tout simple. Peut-on résoudre le système
a^x mod n = 1
b^x mod n = 1
c^x mod n = 1 ?

Je sais que seulement une des ces conditions n'est pas suffisante pour trouver facilement une solution, et que le problème avec une seule équation s'apparente au problème du logarithme discret, qui est réputé difficile à résoudre, mais d'adjonction de plusieurs équations simplifie-t-elle la situation ?
Exemple concret : 2^x mod 77 = 1, 3^x mod 77 = 1, 5^x mod 77 = 1, avec solution x = 30

Pour moi ce problème ressemble vaguement au théorème chinois des restes, mais je peux me tromper.
Merci en avance pour tout commentaire ou suggestion ou référence bibliographique.
Cordialement.

Réponses

  • nodgim
    nodgim
    Déja, il est nécessaire que a,b et c soient premiers avec n. Si l'un d'entre ne l'était pas, tu ne pourrais pas obtenir avec lui 1 modulo n, il te resterait toujours au moins le PGCD .

    Cela étant dit, connais tu le petit théorème de Fermat ?
  • Zazoux
    Zazoux
    Bonjour,
    en premier lieu je vous remercie pour votre commentaire.

    Ensuite, oui, je connais le petit théorème de Fermat, comme formulation mathématique, ça ressemble, mais je ne vois pas du tout comment cette ressemblance peut être utilisée pour avancer les choses.

    Ensuite, le petit théorème de Fermat demande que p soit prime [premier], ce qui n'est pas le cas chez moi.
    Merci encore pour toute autre détail supplémentaire ou commentaire.
    Cordialement.
  • nodgim
    nodgim
    Le petit théorème de Fermat " étendu " te dit que que si " n " et " a " sont premiers entre eux ( donc " n " pas nécessairement premier) il existe une valeur " x " pour laquelle a ^ x = 1 [n].

    Et ça, ce n'est pas bien compliqué à démontrer.

    Plus fort, on donne une indication sur x : x est un diviseur de phi(n), l'indicatrice d'Euler, qui est le nombre de nombres premiers avec n inférieurs à n.

    phi (n) se calcule facilement quand on connait les facteurs premiers de n.

    Dans ton exemple 77 = 7 *11, phi(n) = 77 * ( 6 / 7) * ( 10 * 11) = 60.
    Donc, en connaissant cette propriété, on en déduit que 60 convient sans trop se casser la tête. En revanche, c'est plus compliqué pour savoir, comme dans ton cas, si ça marche avec un diviseur de 60. Là, il faut faire le calcul.
  • Zazoux
    Zazoux
    Bonsoir,
    je vous remercie encore une fois.
    Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 21

Rescassolbiguine_equationmanuzygomathique +17 Invités