Système de congruences

[Zazoux]

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 sait que seulement une des ces conditions n'est pas suffisante pour trouver facilement une solution, et que le problème avec une seule equation s'apparente au problème du logarithme discret, qui est reputé difficile a resoudre, mais d'adjonction de plusieurs equations simplifie 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 resemble vaguement au théorème chinois des restes, mais je peut me tromper.
merci en avance pour tout commentaire ou suggestion ou réference bibliographique

cordialement

[Ben314]

Salut,
Vu de façon théorique, c'est complètement "culcul" comme système :
Pour a et n fixés premiers entre eux, l'équation a^x=1 [n] elle dit (exactement) que n est un multiple de l'ordre de a dans le groupe multiplicatif (Z/nZ)* donc elle équivaut à une équation de la forme x = 0 [A] pour un certain entier A.
Donc tes 3 équations équivalent à :
x = 0 [A]
x = 0 [B]
x = 0 [C]
Et les solutions, c'est les multiples du ppcm(A,B,C).

Et concernant le "problème du logarithme discret", c'est pas du tout un problème en math. mais uniquement en informatique c'est à dire uniquement si tu cherche un algorithme pour déterminer les solutions d'un tel système, c'est à dire en fait une méthode calculatoire rapide pour déterminer le A connaissant a et n.

[Zazoux]

Bonjour,
en premièr lieu, je vous remercie pour votre réponse.
Ensuite, même si votre formulation est claire, moi je ne suis pas sûr de comprendre correctement. Dans le cas du petit exemple, avez vous l'amabilité de détailler d'une manière pedagogique vos propos ?
A = ?, B = ?, C = ?
En vous remeciant en avance
cordialement

[Ben314]

Dans ton exemple, tu as :



Donc en fait, dans ce cas là, il n'y a rien à "résoudre" comme système.
Mais par contre



Donc le système formé par ces 3 congruence a pour solution tout les multiples du ppcm(10,6,5)=30

[Lostounet]

Dans ton exemple, tu as :



Donc en fait, dans ce cas là, il n'y a rien à "résoudre" comme système.
Mais par contre



Donc le système formé par ces 3 congruence a pour solution tout les multiples du ppcm(10,6,5)=30

Salut,
Pour redire un peu la même chose que Ben mais peut-être plus 'lentement':

Considérons par exemple
6^x=1 [77]
10^x=1 [77]
15^x=1 [77]

Considérons 6^x=1 [77]
Nous devons rechercher le plus petit entier naturel n tel que
6^n = 1 [77]
Une fois cet entier n trouvé, nous saurons à coup sûr que x est un multiple de n (car n est le plus petit possible et x est forcément plus grand que lui et son multiple).

Maintenant pour trouver ce n, on peut par exemple calculer toutes les puissances de 6 une à une modulo 77 ce qui n'est pas difficile. Voici une autre méthode:

6^n = 1 [77]
Est équivalente à:
6^n = 1 + 77k (k un entier)
Alors 6^n = 1 + 7*(11k)
Et bien sûr: 6^n = 1 + 11*(7k)

Ce qui signifie que ( 6^n = 1 [7] et 6^n = 1 [11] ) sont équivalentes à 6^n = 1 [77]
(Cela est une application du Lemme chinois/le théorème d'isomorphisme chinois si ça te dit quelque chose)

Donc on cherche n tel que 6^n = 1 [7]
Et 6^n = 1 [11]

Un autre résultat d'algèbre (le théorème de Lagrange appliqué aux ss-groupes engendrés par <6> dans les groupes Z/pZ* qui sont maintenant cycliques car p est premier) dit:
On calcule 7-1=6
Et 11-1=10
On liste leurs diviseurs: {2;3,1,6}
{1;2;5;10}
Il suffit donc de chercher k dans {2;3;6;1}
Tel que 6^k = 1 [7]
On trouve k=2

Puis on cherche k dans {1;2;5;10} tel que 6^k=1 [11]
On trouve k=10

Donc 6^2=1[7]
Et 6^10=1 [11]

Donc si on prend n=10 (le ppcm de 2 et 10) on voit bien que
6^10=1 [7]
Et 6^10=1 [11]

Ce qui équivaut à 6^10=1 [77]

Donc n=10


Donc 10 divise x

On refait de même pour les 2 autres équations !

[Zazoux]

Merci beaucoup a tous les deux pour ces détails

cordialement