trouver un nombre en fonction de son modulo

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

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

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.

La méthode pour trouver une des valeurs de x ? D'accord, mais je suis pas censé avoir 401 au début non ?

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

Ok, donc la seule solution est d'essayer des valeurs de x jusqu'à tomber sur un résultat égal à 1 ? Mon but n'est pas de trouver toutes les valeurs, mais une seule

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.

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

Ça peut marcher ? Intéressant, j'avais jamais vu. On m'a toujours appris ça au « démerde-toi ». Bon ben c'est noté. Et désolé.