Congruences et grands nombres

[roro1664]

Salut tout le monde !

Mon problème est de trouver le reste de par 187 dans la division euclidienne. Inutile de chercher avec la calculatrice c'est un nombre à 26 chiffres !
Alors mon prof m'a donné une astuce utilisant les congruences :

( est manipulable)
Puis
et

Donc

Je ne comprends pas bien son raisonnement et j'aimerais pouvoir l'appliquer à d'autres puissances, par exemple pour montrer que

En fait c'est un exemple du cryptage RSA avec pour clé publique (187;13) et pour clé privée (187;37). On a : et

Merci d'avance pour votre aide

[maturin]

ben le but c'est de dire que
si a=a'[n]
et b=b'[n]
alors ab=a'b'[n]

ce que tu retrouves facilement en disant a=a'+kn
donc là ton but c'est de décomposer ton très grand nombre ne produit de plus petit nombre dont tu pourras calculer la congruance.
ici 100^13=100^4*100^4*100^4*100^4*100

et tu as 155^37=((155^4)^2)^4*155^4*155 par exemple

[fahr451]

en fait 187 est un peu lourd à manipuler mais

187 = 11.17 donc on peut regarder modulo 11 et 17 qui sont premiers entre eux

si a et b sont congrus modulo 11 et 17 ils le sont aussi modulo 187

or 155 congru à 1 modulo 11 donc 155^37 aussi et 100 aussi

pour 17 : 155 congru à 2, 2^16 congru à 1 ( car 17 premier (petit théorème de fermat)) puis 2^32 congru à 1 et 2^37 congru à 2^5 = 32 congru à 15 et 100 aussi.

[roro1664]

Ah d'accord !!!!!!!!!!!!!
J'avais pas vu !!! honte à moi :briques:

merci beacoup