Résoudre x^n = a [m]

[invite2220c077]

Bonjour,

J'aimerais savoir comment résoudre, d'une manière générale, cette congruence avec x, a et m des entiers donnés et n l'inconnue .

Je connais une méthode mais c'est avec n, a et m connus.

Merci d'avance.
-----

[invite03f2c9c5]

Bonjour, une méthode simple consiste à tout simplement tester pour n=0, n=1, n=2, etc., en réduisant à chaque fois le résultat modulo m (c'est-à-dire qu'on regarde le reste de la division de x^n par m). Au bout d'un moment, on retombe forcément sur une valeur déjà obtenue (on peut obtenir au plus m valeurs différentes) : la suite des x^n est périodique. Aussi cette méthode rudimentaire permet-elle en théorie d'obtenir toutes les solutions à ton problème.

Maintenant, si m est grand, cela peut s'avérer compliqué en pratique… et c'est justement intéressant en cryptographie ! Le problème que tu poses est connu sous le nom de recherche du logarithme discret ; on doit trouver des références à ce sujet sur le web… Par exemple, le dernier exercice du concours général 2005 traite de ce sujet et pourrait faire ton bonheur.

[invite2220c077]

Merci bien pour votre réponse.

En fait j'aimerais montrer que la congruence 2^n = 1 [1295] n'admet aucune solution

[invite2220c077]

Ok c'est bon. En fait j'étais ammené à résoudre ça pour clore un exercice, mais je me suis rendu compte qu'il y avait une manière alternative

[A voir en vidéo sur Futura]

[invite1237a629]

Merci bien pour votre réponse.

En fait j'aimerais montrer que la congruence 2^n = 1 [1295] n'admet aucune solution

Ben je trouve que 864 marche (en utilisant la fonction d'Euler et la notion de groupe inversible)

[invite2220c077]

Oui, je m'étais gourré dans mon exercice ^ ^

[invite787dfb08]

Je suis intéressé par les détails utilisés pour arriver aux résulats Mimoimolette ? Peux tu préciser un peu...

Merci

[invite24dc6ecc]

Salut à tous. MiMoiMolette tu peu s'il te plait nous montrer comment tu as fait pour trouver ton résultat, ça a l'air intéressant.

[invite2220c077]

Il a utilisé je pense ce théorème, dit "théorème d'Euler", qui est une généralisation du petit théorème de Fermat :

Si est premier avec alors :



avec l'indicatrice d'Euler qui désigne le nombres d'entiers naturels non nuls inférieurs ou égal à et premier avec lui.

Concrètement,

avec les nombres premiers dans la décomposition en facteurs premiers de .

[invite2220c077]

Donc en fait dans mon exercice n = 1295 = 5*7*37, donc = 1295(1- 1/5)(1 - 1/7)(1 - 1/37) = 864, et donc l'équation 2^x = 1[1295] admet x = 864 comme solution. (bien vu MiMoi' )

[invite2220c077]

D'ailleurs je vais poster dans les minutes qui viennent un exercice avec cet indicateur d'Euler ici

[invite1237a629]

Voui, voilà, c'est ça

En fait, pour aller plus loin dans l'explication, 2 est premier avec 1295. Donc il appartient à son groupe inversible, c'est à dire l'ensemble des nombres premiers avec 1295. Ceux-ci auront toujours un inverse, i.e. un nombre (une classe en fait) qui, multiplié à 2, donnera 1.

Le phi(n), indicatrice d'Euler de n, correspond au nombre d'éléments contenus dans le groupe inversible. L'ordre de 2 divise le cardinal du groupe. Et un nombre élevé à la puissance égale à l'ordre = 1.

Enfin je crois, mais en gros, c'est ça

[invite787dfb08]

Hello

Ok c'est un peu plus clair...

Vous pourriez poster un résumé concerant cette résolution de congruence dans le fil de spe maths (http://forums.futura-sciences.com/thread172647-3.html), d'abord avec n petit, en cherchant une périodicité, puis ensuite avec n plus grand par le théorème d'Euler, en redonnant si besoin est cet exemple, parce que je pense que ça peut intéresser pas mal de monde...

Merci ce serait sympa

++

[invite1237a629]

Le problème, c'est que ce n'est utilisable que si ledit a est premier avec n

[invite787dfb08]

Ben ça peu quand même aider.... Cela dit si tu connais des méthodes plus générales avec n grand, n'hésite pas...

[danyvio]

Merci bien pour votre réponse.

En fait j'aimerais montrer que la congruence 2^n = 1 [1295] n'admet aucune solution

Si : n=0 et peut-être d'autres, mais celle-ci était tellement évidente...

[invite1237a629]

Hm, pour ça il faut que j'y réfléchisse.

Sinon, Zweig a posté un exercice pour le théorème d'Euler.

J'aurais juste une remarque à faire à propos du calcul de phi(n). Lorsqu'on a p^r, on ne note 1-1/p qu'une seule fois

[invite2220c077]

J'aurais juste une remarque à faire à propos du calcul de phi(n). Lorsqu'on a p^r, on ne note 1-1/p qu'une seule fois

Euh ? Non on a plutôt : . En effet, parmis {1, 2, ..., }, nombres sont des multiples de , donc non premiers avec lui. D'où le résultat.

[invite1237a629]

Ce que je voulais dire, c'est que quand on calcule phi(n) avec p^r qui divise phi(n), on ne marque pas r fois (1-1/p)

[invite2220c077]

Ah ok, au temps pour moi