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 ?

Petit goéland très cordial

+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

Petit goéland très cordial

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

Petit goéland très cordial

+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