arithmétique

[xintia]

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

[SoS-Math(9)]

Bonjour Xintia,

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

SoSMath.

[Xintia]

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

[Xintia]

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

[sos-math(21)]

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

[Xintia]

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

[sos-math(21)]

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

[Xintia]

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é ?

[sos-math(21)]

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

[xintia]

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

[sos-math(21)]

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