Home

MPSI/PCSI

Maths

Algèbre

Congruences

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.

Salut ! Alors dans cet exercice, le but est de trouver le reste de la division par 13 du nombre 100 puissance 1000. Je vous déconseille de le faire à la calculatrice, de toute façon la calculatrice fait une erreur, c'est un nombre qui est tellement grand. Là, il faut absolument passer par les congruences. Donc le premier truc à faire, c'est de voir juste 100, ça vaut combien de modules aux 13 ? Donc là, on le fait, la division euclidienne classique, 100 c'est 13 fois 7 plus 9, et donc ça nous fait que 100 est congru à 9 modules aux 13. Ensuite, ce qu'on veut trouver, c'est une puissance de 100 qui va nous donner un module aux 13. C'est ça la méthode, c'est on regarde ce nombre-là, on cherche à quelle puissance on peut le mettre pour trouver un module au, le nombre par lequel on fait la division, donc là, module aux 13. Sauf qu'au lieu de travailler avec 100, on va travailler avec 9, parce que 100 est congru à 9, donc si 100 puissance par exemple 4 est congru à 1 module aux 13, c'est 9 puissance 4 aussi qui sera congru à 1 module aux 13, et dans les deux sens ça marche. Donc on va faire les puissances de 9, donc 9 puissance 2 ça fait 81, c'est congru à 3 modules aux 13, ça ne nous arrange pas, nous ce qu'on veut c'est 1, 9 puissance 3 c'est 9 puissance 2 fois 9, donc ça c'est congru à 27, mais 27 c'est congru à 1 module aux 13, parce qu'il y a 26 justement, donc 27 c'est congru à 1 module aux 13, ça ça nous arrange bien, c'est ce qu'on voulait, donc finalement la puissance qu'on cherchait c'est 3. Donc on réécrit 100 puissance 3 c'est congru à 9 puissance 3, c'est congru à 1 puissance 3, c'est congru à 1 module aux 13. Et étant donné que le 100 puissance 3 est congru à 1 module aux 13, le 3 qui est là, ça ça va être notre nouveau diviseur, cette fois-ci de la puissance qui est là. Donc ça veut dire qu'on va faire une division euclidienne de 1000 par 3. Donc c'est parti, donc le 3 comme je disais voilà, on fait 1000 c'est 3 fois 333, plus 1. Bon, maintenant qu'on a cette division euclidienne, on va le réécrire comme la puissance de 100, et il y a beaucoup de choses qui vont se simplifier du fait de cette division euclidienne justement. Donc 100 puissance 1000, c'est 100 puissance 3 fois 333 plus 1, et donc on utilise les règles de calcul qu'on connaît sur les puissances, ça fait 100 puissance 3, le tout à la puissance 333 d'accord, parce qu'on a un produit ici, c'est qu'on a une puissance et encore une puissance, et le plus 1 qui est là, c'est le x100 qu'on a rajouté ici sur le côté. Alors maintenant qu'on a ça, donc il ne faut pas se planter, il ne faut pas dire que c'est 100 puissance 333, le tout à la puissance 3, on verrait beaucoup moins ce qui se passe. Le fait de l'écrire comme ça, c'est parce qu'en fait 100 puissance 3, comme on l'a dit, ça c'est exactement congru à 1, et 100 est congru à 9. Donc on remplace 100 par 9, parce qu'ici on n'a pas mis une égalité, on a mis une congruence, et un petit modulo 13 ici, et donc 1 puissance 333, c'est quand même 1 modulo 13, donc finalement 1 puissance 333 fois 9 est congru juste à 9 modulo 13. Donc étant donné que 100 puissance 1000 est congru à 9 modulo 13, par définition des congruences, le reste de la division euclidienne de 100 puissance 1000 par 13, et bien c'est 9.

Congruences avec les puissances

RELATED

Recommended videos

Cubes consécutifs

Division de puissances