Calcul de grandes puissances

[invitecaeaab4f]

Bonsoir,

Y'a t-il un moyen de vérifier que est congru à 1 modulo 7879 ? car ma calculatrice n'est pas assez puissante pour le calculer donc je voudrai connaitre une méthode qui puisse le faire, sans ordinateur.

Merci d'avance.
-----

[sylvainc2]

64+32+4+1=101
Donc tu peux calculer 170^64 en faisant 6 élévations au carré et réduisant mod 7879 à chaque fois.
Puis 170^101 = 170^64 * 170^32 * 170^4 * 170 mod 7879
en ayant conservé les résultats intermédiaires 170^32 et 170^4.

[invitecaeaab4f]

D'accord.

On se retrouve donc avec :
170^101 = 5263^6 * 170^32 * 170^4 * 170 (mod 7879)

Mais je ne vois toujours pas comment montrer que c'est congru à 1 modulo 7879.

[invitecaeaab4f]

Enfin, j'ai fais comme ceci :

170^2 = 5263 [7879]
5263 * 170^2 = 4484 [7879]
4484 * 170^2 = 1687 [7879]
.
.
.
et je me retrouve avec 170^64 = 1650 [7879]

[A voir en vidéo sur Futura]

[sylvainc2]

Il faut faire ceci:
170^2=5263
5263^2=4484 = 170^4
4484^2=6927=170^8
6927^2=219=170^16
219^2=687=170^32
687^2=7108=170^64

Donc on fait 7108*687=6095
6095*4484=5608
5608*170=1
tout ca modulo 7879 bien sur.