Calculs de puissances modulo n et cycles périodiques des restes

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Si a et n sont premiers entre eux, la suite des restes de a^k modulo n est périodique dès k = 0. • Si a^T 1 n, alors pour tout p = Tq + r : a^p a^r n • Si l'on obtient a^m -1 n, alors a^2m 1 n : les restes se répètent tous les 2m rangs.

Le cours

1. Pourquoi les restes des puissances se répètent Modulo n, il n'y a que n restes possibles. Comme a^k+1 a a^k n, chaque reste détermine le suivant : dès qu'un reste réapparaît, toute la suite se répète. Si a et n sont premiers entre eux, la suite des restes de a^k est périodique dès k = 0 et l'on finit par trouver a^T 1 n. Sinon, elle n'est périodique qu'à partir d'un certain rang et ne repasse jamais par 1 : les restes de 2^k modulo 12 sont 1, 2, 4, 8, 4, 8, 4, 2. Méthode 1. Calculer a^1, a^2, a^3, modulo n jusqu'à obtenir 1 (ou -1, qui donne 1 en élevant au carré). 2. Noter le plus petit T 1 tel que a^T 1 n. 3. Diviser l'exposant : p = Tq + r avec 0 r 4. Conclure : a^p = (a^T)^q a^r a^r n. Mini-exemple : 4^1 4, 4^2 7, 4^3 1 9 ; 100 = 3 33 + 1, donc 4^100 4 9. 3. Attention Si le reste r de l'exposant est nul, alors a^p a^0 = 1, et non a^T écrit à part. Et la période dépend de a : modulo 7, elle vaut 3 pour 2 mais 6 pour 3.

Dans ce chapitre