L'indicatrice d'Euler et les nombres premiers de Fermat

(i) Dans le groupe cyclique ${\mathbb Z/n\mathbb Z}$, les générateurs sont au nombre de $\varphi(n)$, et ce sont les éléments d'ordre $n$ (Groupes cycliques, (iii)). Si $m \wedge n = 1$, le groupe $\mathbb Z/mn\mathbb Z$ est isomorphe à $\mathbb Z/m\mathbb Z \times \mathbb Z/n\mathbb Z$ (même nœud, (iv)), et un isomorphisme conserve l'ordre des éléments.

Dans le produit, soit $(x, y)$ avec $x$ d'ordre $d \mid m$ et $y$ d'ordre $d' \mid n$ ; un diviseur commun à $d$ et $d'$ divise $m$ et $n$, donc $d \wedge d' = 1$. On a $k(x, y) = 0$ si et seulement si $d \mid k$ et $d' \mid k$, c'est-à-dire $dd' \mid k$, par le lemme de Gauss (PGCD, Bézout, (iii)). L'ordre de $(x, y)$ est donc $dd'$, et il vaut $mn$ si et seulement si $d = m$ et $d' = n$ : il y a $\varphi(m)\varphi(n)$ éléments d'ordre $mn$.

Pour $p$ premier, un entier $k$ est premier à $p^a$ si et seulement si $p \nmid k$. En effet, un diviseur premier commun à $k$ et à $p^a$ divise $p$ par le lemme d'Euclide (Nombres premiers, (i)), donc vaut $p$. Les multiples de $p$ dans $\{1, \dots, p^a\}$ sont les $p^{a-1}$ entiers $p, 2p, \dots, p^{a-1}p$, d'où $\varphi(p^a) = p^a - p^{a-1}$.

(ii) Si $m$ avait un diviseur impair $q > 1$, avec $m = qr$, l'identité $$x^q + 1 = (x + 1)\sum_{k=0}^{q-1}(-x)^k,$$ valable pour $q$ impair, appliquée à $x = 2^r$, montrerait que $2^r + 1$ divise $2^m + 1$, avec $1 < 2^r + 1 < 2^m + 1$. Donc $m$ n'a pas de facteur premier impair, et c'est une puissance de $2$ (Nombres premiers, (ii)).

(iii) Écrivons $n = 2^k p_1^{a_1} \cdots p_r^{a_r}$, avec des nombres premiers impairs $p_i$ distincts et $a_i \geqslant 1$. Par (i), appliqué de proche en proche aux facteurs, deux à deux premiers entre eux, $$\varphi(n) = \varphi(2^k) \prod_{i=1}^r p_i^{a_i - 1}(p_i - 1),$$ avec $\varphi(2^k) = 2^{k-1}$ si $k \geqslant 1$ et $\varphi(1) = 1$.

Par unicité de la décomposition en facteurs premiers, ce produit est une puissance de $2$ si et seulement si chaque facteur en est une, c'est-à-dire si chaque $a_i$ vaut $1$ et si chaque $p_i - 1$ est une puissance $2^{m_i}$, avec $m_i \geqslant 1$. Par (ii), $p_i = 2^{m_i} + 1$ est alors un nombre premier de Fermat. Réciproquement, pour un nombre premier de Fermat $p$, $p - 1 = 2^{2^j}$.