trouver un nombre en fonction de son modulo

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Je cherche à trouver x dans cette équation simple :
(53 * x) mod 1932 = 1
Je sais que la réponse est x = 401, mais je n'arrive pas à résoudre moi-même …

Pouvez-vous m'aider, me proposer des pistes pour résoudre ceci ? merci d'avance

Édité par Paul64

+0 -0

Cette réponse a aidé l'auteur du sujet

Coucou,

as-tu vu les équations diophantiennes ?A vue de nez, il n'y a pas que 401 d'ailleurs comme solution. Et à défaut de connaître, le théorème de Gauss c'est quelque chose que tu maîtrises ou pas du tout ?

Ich bin très occupé cette année. Ne vous étonnez pas si je réponds par intermittence.

+0 -0
Auteur du sujet

Oui, effectivement, il y a plusieurs solutions car il n'y a pas qu'un seul multiple de 53 qui donne comme reste 1 lorsque qu'on fait une division (euclidienne) par 1932 … Les équations diophantiennes sont des équations dont les solutions sont cherchées parmi les nombres entiers, non ? J'ai pas vu le le théorème de Gauss

Édité par Paul64

+0 -0

Si tu ne l'as pas vu, il te manque des ressources théoriques pour pouvoir résoudre l'équation proprement. Je donne juste la méthode :

  • trouver une solution particulière (ici 401 fer l'affaire)
  • soustraire pour retomber sur $53×(x - 401) [1932] \equiv 0$
  • traduire la congruence en $\exists k \in N$, … EDIT : d'ailleurs c'est plutôt $\exists k \in Z$.
  • trouver des conditions nécessaires sur le k puis sur le $x - 401$. C'est ce point-là qui va te manquer car tu ne pourras pas dire grand chose.

Édité par Goeland-croquant

Ich bin très occupé cette année. Ne vous étonnez pas si je réponds par intermittence.

+0 -0

Bah il faut tester un peu, soit par essais de 1 à n, soit un peu au pif et en ajustant. Tu es obligé de trouver une solution particulière pour commencer (son existence est assurée, sous certains critères qui sont respectés ici, par le théorème de Bezout).

Ich bin très occupé cette année. Ne vous étonnez pas si je réponds par intermittence.

+0 -0

Ok, donc si tu veux une seule solution, pas d'autres solutions que le pifomètre pour trouver la première. Sous réserve du théorème de Bezout, que tu peux regarder sur Wiki si besoin.

Ich bin très occupé cette année. Ne vous étonnez pas si je réponds par intermittence.

+0 -0

Je ne crois pas l'avoir vu cité plus haut dans le thread, mais on peut quand même utiliser l'algo d'Euclide. En effet, si on trouve un couple $(x, y)$ tel que $53x+1932y=1$, c'est gagné (question : pourquoi ?). Or, un tel couple existe, puisque, si on regarde bien : $\text{pgcd}(53,1932)=1$ (c'est d'ailleurs la condition d'existence de $x$ évoquée plus haut). Il ne reste plus qu'à « renverser » les étapes de l'algo d'Euclide pour trouver $x$ et $y$ (ça doit se trouver un peu partout sur le Web). Ça s'appelle « l'algorithme d'Euclide étendu ».

Édité par Lucas-84

Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte