SOS-MATH

Bonjour j'ai quelque soucie en arithmétique pour un exercice

il faut touver x
dans
204^235 congru à x modulo (391)
la réponse est 34 mais je sais pas comment on y arrive

j'ai essayé de me rapporter à des congruences modulo 1 pour après pouvoir multiplier par 34 mais ça ne donner rien de concluant :
204^352 est congru à 1 modulo (391)
204^(352-117)=204^352 * 204^(-117) congru à 1 * 204^(-117) modulo (391)
mais après ......il reste toujours de grosses puissances et en plus négatives !
normalement 204^(-117) devrait être égal à 34 sauf que le problème c'est que ça n'est pas supérieur à 1 puisque c'est de la forme 1/a avec a plus grand que 1 .

Donc je ne vois pas comment faire, pouvez vous m'aider SVP

Bonjour Xintia,

Tu peux commencer par chercher un diviseur commun à 204 et 391 ...

SoSMath.

391 = 17 *23
204= 2²*3*17
235= 5*47

le diviseur commun de 391 et 204 est 17
donc on a au départ 17 congru à 0 modulo 17 et 23 congru à 0 modulo 23
ce qui donne 17^235 congru à 0 modulo 17
je multiplie les 2 congruences çà donne : 17^235 * 23 congru à 0*23 congru à 0 modulo (17*23) donc modulo 391
ce qui équivaut à 6^235 * 34^235 * 23 congru à modulo 391

mais après ......
je ne vois pas ....

391 = 17 *23
204= 2²*3*17
235= 5*47

le diviseur commun de 391 et 204 est 17
donc on a au départ 17 congru à 0 modulo 17 et 23 congru à 0 modulo 23
ce qui donne 17^235 congru à 0 modulo 17
je multiplie les 2 congruences çà donne : 17^235 * 23 congru à 0*23 congru à 0 modulo (17*23) donc modulo 391
ce qui équivaut à 6^235 * 34^235 * 23 congru à modulo 391

mais après ......
je ne vois pas ....

J'ai une solution un peu artisanale, faute de mieux :
Décompose ton exposant en somme de puissances de 2 puis calcule les congruences successives de \(204^{2^n}\).
Multiplie ensuite les réponses et calcule encore modulo 391.
A la fin, après quelques calculs, on arrive bien à une congruence de 34 modulo 391.
Bons calculs

Bon alors voilà ce que j'ai fait

204^235 = 204^2^7 * 204^2^6 * 204^2^5 * 204^2^3 * 204^3
204^2 congru à 106 modulo 391
donc 204^2^7 congru à 106^7 congru à 387 modulo 391
et on fait comme çà pour chaque congruence ensuite, on multiplie le tout
et ça donne
204^235 congru à 187 modulo 391
et là après ... ??
187= 34+9*17
....
je ne vois pas vraiment

Tu as :
\(235=1+2+2^3+2^5+2^6+2^7=1+2+8+32+64+128\)
\(204\eq 204 [391]\)
\(204^2\eq 170 [391]\)
\(204^8\eq170^4\eq 374 [391]\)
\(204^{16}\eq 374^2\eq 289[391]\)
\(204^{32}\eq 289^2\eq 238 [391]\)
\(204^{64}\eq 238^2\eq 340 [391]\)
\(204^{128}\eq 340^2\eq 255 [391]\)
Maintenant, tu sais donc que \(204^{235}\eq 204^{1+2+8+32+64+128}\eq 204\times 204^2\times 204^8\times 204^{32}\times 204^{64}\times 204^{128}\eq 204\times 170\times 374\times 238\times 340\times 255\eq .... [391]\)
Il te reste ensuite à calculer ces congruences 2 à 2, puis de continuer....

ah oui, j'ai recopié le quotient à la place du reste dans ma division euclidienne de 204^2 par 391, suis-je bête,

oui donc après ça donne 204^235 congru à 34 modulo 391
et c'est terminé merci beaucoup
mais une question comment avez vous su que cette méthode marcherait, vous le saviez d'avance ou vous avez testé ?

Non, c'est une méthode qu'on peut appliquer notamment lorsque l'on fait du chiffrage RSA :
391 est le produit de deux nombres premiers 17 et 23, ce qui est le point de départ du chiffrement.
Donc cette méthode, classique, est toujours valable.
Bon courage

ah oui, merci
et est ce que ça se démontre que cette méthode marche tout le temps ?

Oui, je pense qu'on peut le démontrer car tout entier peut s'écrire comme une somme de puissance de 2 : c'est l'écriture en base 2.
Ensuite le protocole de calcul est de type algorithmique.
En un nombre fini d'opérations, on peut avoir la congruence cherchée.
Bonne continuation