Résoudre x^n = a [m] (2024)

Affichage des résultats 1 à 20 sur 20

1. 10/11/2007,18h27 #1

   invite2220c077

   

   Résoudre x^n = a [m]

   
   

   ------

   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.

   -----

2. 10/11/2007,18h44 #2

   invite03f2c9c5

   

   Re : Résoudre x^n = a [m]

   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.

3. 10/11/2007,19h09 #3

   invite2220c077

   

   Re : Résoudre x^n = a [m]

   Merci bien pour votre réponse.

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

4. 10/11/2007,19h15 #4

   invite2220c077

   

   Re : Résoudre x^n = a [m]

   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

5. Aujourd'hui

   A voir en vidéo sur Futura

6. 10/11/2007,20h16 #5

   invite1237a629

   

   Re : Résoudre x^n = a [m]

   Envoyé par -Zweig-

   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)

   See Also

   1.5: Rules of Exponents and Scientific NotationRègles des exposants et de ses opérations - MathCracker.comExponents and Powers (Rules and Solved Examples)Exponent properties review (article) | Khan Academy

7. 10/11/2007,20h39 #6

   invite2220c077

   

   Re : Résoudre x^n = a [m]

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

8. 10/11/2007,21h23 #7

   invite787dfb08

   

   Re : Résoudre x^n = a [m]

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

   Merci

9. 10/11/2007,22h08 #8

   invite24dc6ecc

   

   Re : Résoudre x^n = a [m]

   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.

10. 10/11/2007,22h15 #9

    invite2220c077

    

    Re : Résoudre x^n = a [m]

    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 .

11. 10/11/2007,22h28 #10

    invite2220c077

    

    Re : Résoudre x^n = a [m]

    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' )

12. 10/11/2007,22h58 #11

    invite2220c077

    

    Re : Résoudre x^n = a [m]

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

    See Also

    8.1: Rules of Exponents

13. 11/11/2007,08h26 #12

    invite1237a629

    

    Re : Résoudre x^n = a [m]

    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

14. 11/11/2007,09h03 #13

    invite787dfb08

    

    Re : Résoudre x^n = a [m]

    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

    ++

15. 11/11/2007,09h08 #14

    invite1237a629

    

    Re : Résoudre x^n = a [m]

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

16. 11/11/2007,09h10 #15

    invite787dfb08

    

    Re : Résoudre x^n = a [m]

    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...

17. 11/11/2007,09h42 #16

    danyvio

    Re : Résoudre x^n = a [m]

    Envoyé par -Zweig-

    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...

    On trouve des chercheurs qui cherchent ; on cherche des chercheurs qui trouvent !

18. 11/11/2007,09h43 #17

    invite1237a629

    

    Re : Résoudre x^n = a [m]

    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

19. 11/11/2007,11h29 #18

    invite2220c077

    

    Re : Résoudre x^n = a [m]

    Envoyé par MiMoiMolette

    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.

20. 11/11/2007,11h31 #19

    invite1237a629

    

    Re : Résoudre x^n = a [m]

    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)

21. 11/11/2007,11h32 #20

    invite2220c077

    

    Re : Résoudre x^n = a [m]

    Ah ok, au temps pour moi

1. équation à résoudre

   Par invitec2877e50 dans le forum Mathématiques du collège et du lycée

   Réponses: 6

   Dernier message: 02/11/2007, 14h34

2. Résoudre A^k = B^q

   Par Anduriel dans le forum Mathématiques du collège et du lycée

   Réponses: 36

   Dernier message: 23/08/2007, 13h50

3. résoudre P(x) = 0 [n]

   Par invite4ef352d8 dans le forum Mathématiques du supérieur

   Réponses: 1

   Dernier message: 16/01/2007, 19h37

4. Résoudre x² + 1 = 0

   Par Bleyblue dans le forum Mathématiques du supérieur

   Réponses: 7

   Dernier message: 04/10/2006, 18h42

5. résoudre

   Par invite8ebda540 dans le forum Électronique

   Réponses: 20

   Dernier message: 12/04/2003, 11h56