Congruences avec les puissances

Dans cet exercice, l'objectif est de trouver le reste de la division par 13 du nombre 100 puissance 1000. Pour cela, il est recommandé d'utiliser les congruences plutôt qu'une calculatrice en raison de la taille du nombre. Tout d'abord, on détermine le reste de la division de 100 par 13, qui est 9. Ensuite, au lieu de travailler avec 100, on travaillera avec 9 car ils sont congruents modulo 13. Par exemple, si 100 puissance 4 est congru à 1 modulo 13, alors 9 puissance 4 sera aussi congru à 1 modulo 13. On calcule donc les puissances de 9. On constate que 9 puissance 2 est congru à 3 modulo 13, mais ce n'est pas ce que l'on souhaite. On cherche à trouver une puissance de 9 qui est congru à 1 modulo 13, et on trouve que 9 puissance 3 est congru à 1 modulo 13. Donc la puissance recherchée est 3. On réécrit alors 100 puissance 3 comme congru à 9 puissance 3, qui est congru à 1 modulo 13. Etant donné que 100 puissance 3 est congru à 1 modulo 13, le nouveau diviseur sera 3 cette fois-ci. On effectue donc une division euclidienne de 1000 par 3, ce qui donne 333 avec un reste de 1. On réécrit alors 100 puissance 1000 comme 100 puissance 3 fois 333 plus 1, en utilisant les règles de calcul sur les puissances. Cela devient donc (100 puissance 3) puissance 333 multiplié par 100. Il est important de ne pas se tromper en interprétant cela comme (100 puissance 333) puissance 3, car cela engendrerait une interprétation différente. Ici, on écrit cette expression de cette façon spécifique car on sait que 100 puissance 3 est congru à 1 modulo 13, et que 100 est congru à 9. Ainsi, on peut remplacer 100 par 9 dans l'expression. En considérant que 1 puissance 333 est égal à 1 modulo 13, le calcul final donne que 1 puissance 333 fois 9 est congru à 9 modulo 13. Par conséquent, selon la définition des congruences, le reste de la division euclidienne de 100 puissance 1000 par 13 est égal à 9.