Puissances
Observons le comportement des puissances successives de $2$ modulo différents nombres.
On a par exemple, modulo $7$ :
$$\begin{array}{c|cccccccc}
m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\[2ex]
\hline
2^m \pmod 7 & 1 & 2& 4 & 1 & 2 & 4 &1 & \ldots
\end{array}$$ Ou modulo $5$ :
$$\begin{array}{c|cccccccc}
m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\[2ex]
\hline
2^m \pmod 5 & 1 & 2& 4 & 3 & 1 & 2 & 4 &\ldots
\end{array}$$ Ou encore, modulo $6$ :
$$\begin{array}{c|cccccccc}
m & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\[2ex]
\hline
2^m \pmod 6 & 1 & 2& 4 & 2 & 4 & 2 & 4 &\ldots
\end{array}$$ Puisque pour passer d'une colonne à la suivante, on ne fait que multiplier par $2$, on peut toujours calculer une valeur à partir de la précédente. Cela signifie en particulier que les valeurs observées formeront toujours une suite périodique ! Dès que l'on retombe sur un élément que l'on a déjà rencontré, la suite devient périodique. Sur les deux premiers exemples, nous sommes retombés sur $1$ alors que sur le troisième, nous avons rencontré $2$ une seconde fois.
Nous aimerions comprendre ces suites en toute généralité, c'est-à-dire celles données par les valeurs modulo $n$ des puissances successives d'un nombre $a$. Sous quelle(s) condition(s) allons-nous retomber sur le nombre $1$ ? Et dans ce cas, après combien de temps ? Avant de pouvoir répondre à ces questions, il nous faut définir la fonction indicatrice d'Euler.