Congruences

[HC53]

bonjour,
je dois montrer que 4^20 est congru à 1 modulo 41.

je sais par le petit théorème de fermat que 4^40 est congru à 1 modulo 41
or dans les règles de congruences, on ne peut pas passer à la racine carrée, pouvez vous m'aider pour poursuivre

merci

[Doraki]

et que peux-tu dire de 2^40 ?

[bend]

remarque que 41 est un nombre premier , puis qu'est ce que on peut dire de 2^41 ?? (pense à Feramt) , apres c'est facile il suffit juste de voir que (2^40) = 4^20!!!

[Ben314]

Je rajouterais qu'il peut aussi être interessant de savoir faire le calcul "a la main", c'est à dire sans Fermat (c'est utile par exemple dans les méthodes de cryptage R.S.A.)
La décomposition de 20 en base 2 est 20=4+16 et on a :
4^2 = 16
4^4 = 16^2 = 256 = 10 [mod 41]
4^8 = 10^2 = 100 = 18 [mod 41]
4^16 = 18^2 = 324 = 37 [mod 41]
Donc 4^20 = 4^(4+16) = 4^4 x 4^16 = 10 x 37 = 370 = 1 [mod 41]

Bon, d'accord, dans le cas présent, c'est trés crétin, mais ça donne une idée de comment font les ordi. pour calculer des trés trés grandes puissances.