Shortlist 2011, N8¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : non indiqué
Concepts : Ordre d'un élément et racines primitives · Résidus quadratiques · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 74 (page 75 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(k\) be a positive integer and set \(n = 2^k + 1\). Prove that \(n\) is a prime number if and only if the following holds: there is a permutation \(a_1, \ldots, a_{n-1}\) of the numbers \(1, 2, \ldots, n - 1\) and a sequence of integers \(g_1, g_2, \ldots, g_{n-1}\) such that \(n\) divides \(g_i^{a_i} - a_{i+1}\) for every \(i \in \{1, 2, \ldots, n - 1\}\), where we set \(a_n = a_1\).
Indices : les idées clés
- Graphe orienté : \(a \to b\) si \(b \equiv g^a \pmod n\) pour un certain \(g\) ; on cherche un cycle hamiltonien.
- \(n\) composé : un facteur carré \(p_i^2\) force \(p_i\) et \(2p_i\) à suivre \(1\) ; si \(n\) est sans facteur carré, les \(\frac{n-1}{2}\) successeurs des nombres pairs sont des résidus quadratiques, qui sont trop peu nombreux.
- \(n\) premier (ordres) : \(a \to b\) si et seulement si \(\nu_2(a) \leq \mu(b)\) ; les ensembles \(A_i\) et \(B_i\) ont même cardinal, et l'on fusionne les cycles d'une bijection \(A_i \to B_i\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et deux remarques).
Solution¶
Posons \(N = \{1, 2, \ldots, n - 1\}\). Pour \(a, b \in N\), on dit que \(b\) suit \(a\) s'il existe un entier \(g\) tel que \(b \equiv g^a \pmod n\), et l'on note cette propriété \(a \to b\). On obtient ainsi un graphe orienté d'ensemble de sommets \(N\). Si \(a_1, \ldots, a_{n-1}\) est une permutation de \(1, 2, \ldots, n - 1\) telle que \(a_1 \to a_2 \to \cdots \to a_{n-1} \to a_1\), c'est un cycle hamiltonien du graphe.
Étape I. Considérons d'abord le cas où \(n\) est composé. Soit \(n = p_1^{\alpha_1} \cdots p_s^{\alpha_s}\) sa décomposition en facteurs premiers. Tous les \(p_i\) sont impairs.
Supposons \(\alpha_i > 1\) pour un certain \(i\). Pour tous entiers \(a\), \(g\) avec \(a \geq 2\), on a \(g^a \not\equiv p_i \pmod{p_i^2}\), car \(g^a\) est soit divisible par \(p_i^2\), soit non divisible par \(p_i\). Il s'ensuit que, dans tout cycle hamiltonien, \(p_i\) vient immédiatement après \(1\). Le même argument montre que \(2p_i\) doit aussi venir immédiatement après \(1\), ce qui est impossible. Il n'y a donc pas de cycle hamiltonien dans le graphe.
Supposons maintenant \(n\) sans facteur carré. On a \(n = p_1p_2 \cdots p_s > 9\) et \(s \geq 2\). Supposons qu'il existe un cycle hamiltonien. Ce cycle contient \(\frac{n-1}{2}\) nombres pairs, et chaque nombre qui suit l'un d'eux doit être un résidu quadratique modulo \(n\). Il doit donc y avoir au moins \(\frac{n-1}{2}\) résidus quadratiques non nuls modulo \(n\). D'autre part, pour chaque \(p_i\), il y a exactement \(\frac{p_i + 1}{2}\) résidus quadratiques modulo \(p_i\) ; par le théorème chinois, le nombre de résidus quadratiques modulo \(n\) est exactement \(\frac{p_1 + 1}{2} \cdot \frac{p_2 + 1}{2} \cdots \frac{p_s + 1}{2}\), en comptant \(0\). On obtient alors une contradiction :
Cela prouve la partie « si » du problème.
Étape II. Supposons maintenant \(n\) premier. Pour tout \(a \in N\), notons \(\nu_2(a)\) l'exposant de \(2\) dans la décomposition en facteurs premiers de \(a\), et posons \(\mu(a) = \max\{t \in [0, k] \mid 2^t \to a\}\).
Lemme. Pour tous \(a, b \in N\), on a \(a \to b\) si et seulement si \(\nu_2(a) \leq \mu(b)\).
Preuve. Posons \(\ell = \nu_2(a)\) et \(m = \mu(b)\).
Supposons \(\ell \leq m\). Comme \(b\) suit \(2^m\), il existe un \(g_0\) tel que \(b \equiv g_0^{2^m} \pmod n\). Comme \(\gcd(a, n - 1) = 2^\ell\), il existe des entiers \(p\) et \(q\) tels que \(pa - q(n - 1) = 2^\ell\). En choisissant \(g = g_0^{2^{m-\ell}p}\), on a
par le petit théorème de Fermat. Donc \(a \to b\).
Pour la réciproque, supposons \(a \to b\), de sorte que \(b \equiv g^a \pmod n\) pour un certain \(g\). Alors \(b \equiv \big(g^{a/2^\ell}\big)^{2^\ell}\), et donc \(2^\ell \to b\). Par définition de \(\mu(b)\), on a \(\mu(b) \geq \ell\). Le lemme est démontré. \(\square\)
Pour tout \(i\) avec \(0 \leq i \leq k\), posons
Montrons que \(\lvert A_i \rvert = \lvert B_i \rvert\) pour tout \(0 \leq i \leq k\). Évidemment, \(\lvert A_i \rvert = 2^{k-i-1}\) pour tout \(i = 0, \ldots, k - 1\), et \(\lvert A_k \rvert = 1\). Déterminons maintenant \(\lvert C_i \rvert\). On a \(\lvert C_0 \rvert = n - 1\) et, par le petit théorème de Fermat, \(C_k = \{1\}\), donc \(\lvert C_k \rvert = 1\). Ensuite, remarquons que \(C_{i+1} = \{x^2 \bmod n \mid x \in C_i\}\). Pour tout \(a \in N\), la relation \(x^2 \equiv a \pmod n\) a au plus deux solutions dans \(N\). On a donc \(2\lvert C_{i+1} \rvert \leq \lvert C_i \rvert\), avec égalité seulement si, pour tout \(y \in C_{i+1}\), il existe deux éléments distincts \(x, x' \in C_i\) tels que \(x^2 \equiv x'^2 \equiv y \pmod n\) (ce qui implique \(x + x' = n\)). Comme \(2^k \lvert C_k \rvert = \lvert C_0 \rvert\), l'égalité doit avoir lieu à chaque étape. Donc \(\lvert C_i \rvert = 2^{k-i}\) pour \(0 \leq i \leq k\), et par conséquent \(\lvert B_i \rvert = 2^{k-i-1}\) pour \(0 \leq i \leq k - 1\) et \(\lvert B_k \rvert = 1\).
Les arguments précédents montrent aussi que, pour tout \(z \in C_i\) (\(0 \leq i < k\)), l'équation \(x^2 \equiv z^2 \pmod n\) a deux solutions dans \(C_i\), donc \(n - z \in C_i\). Ainsi, pour chaque \(i = 0, 1, \ldots, k - 1\), exactement la moitié des éléments de \(C_i\) sont impairs. La même affirmation vaut pour \(B_i = C_i \setminus C_{i+1}\) pour \(0 \leq i \leq k - 2\). En particulier, chacun de ces \(B_i\) contient un nombre impair. Remarquons que \(B_k = \{1\}\) contient aussi un nombre impair, et que \(B_{k-1} = \{2^k\}\) puisque \(C_{k-1}\) est formé des deux racines carrées de \(1\) modulo \(n\).
Étape III. Construisons maintenant un cycle hamiltonien dans le graphe. D'abord, pour chaque \(i\) avec \(0 \leq i \leq k\), relions les éléments de \(A_i\) à ceux de \(B_i\) par une bijection arbitraire. Après avoir fait cela pour chaque \(i\), on obtient un sous-graphe dont tous les sommets ont un degré entrant \(1\) et un degré sortant \(1\) ; ce sous-graphe est donc une union disjointe de cycles. S'il n'y a qu'un cycle, c'est fini. Sinon, on modifie le sous-graphe de façon à conserver cette propriété tout en diminuant le nombre de cycles ; après un nombre fini d'étapes, on arrive à un cycle unique.
Pour tout cycle \(C\), posons \(\lambda(C) = \min_{c \in C} \nu_2(c)\). Considérons un cycle \(C\) pour lequel \(\lambda(C)\) est maximal. Si \(\lambda(C) = 0\), alors \(\lambda(C') = 0\) pour tout autre cycle \(C'\). Prenons deux sommets quelconques \(a \in C\) et \(a' \in C'\) tels que \(\nu_2(a) = \nu_2(a') = 0\) ; soient \(b\) et \(b'\) leurs successeurs directs respectifs. On peut alors réunir \(C\) et \(C'\) en un seul cycle en remplaçant les arêtes \(a \to b\) et \(a' \to b'\) par \(a \to b'\) et \(a' \to b\).
Supposons maintenant \(\lambda = \lambda(C) \geq 1\) ; soit \(a \in C \cap A_\lambda\). S'il existe un \(a' \in A_\lambda \setminus C\), alors \(a'\) est dans un autre cycle \(C'\), et l'on peut fusionner les deux cycles exactement comme ci-dessus. Le seul cas restant est donc \(A_\lambda \subset C\). Comme les arêtes issues de \(A_\lambda\) mènent à \(B_\lambda\), on a aussi \(B_\lambda \subset C\). Si \(\lambda \neq k - 1\), alors \(B_\lambda\) contient un nombre impair, ce qui contredit l'hypothèse \(\lambda(C) > 0\). Enfin, si \(\lambda = k - 1\), alors \(C\) contient \(2^{k-1}\), qui est l'unique élément de \(A_{k-1}\). Comme \(B_{k-1} = \{2^k\} = A_k\) et \(B_k = \{1\}\), le cycle \(C\) contient le chemin \(2^{k-1} \to 2^k \to 1\), et il contient de nouveau un nombre impair. Cela achève la preuve de la partie « seulement si » du problème. \(\blacksquare\)
Remarques¶
Remarque 1. Le lemme et le fait que \(\lvert A_i \rvert = \lvert B_i \rvert\) montrent ensemble que, pour toute arête \(a \to b\) du cycle hamiltonien, on doit avoir \(\nu_2(a) = \mu(b)\). Une fois cette observation faite, on peut construire le cycle hamiltonien de nombreuses façons. Par exemple, on peut choisir des arêtes de \(A_i\) vers \(B_i\) pour \(i = k, k - 1, \ldots, 1\) de façon qu'elles forment des chemins disjoints ; à la fin, tous ces chemins ont des extrémités impaires. À la dernière étape, on peut refermer les chemins en un cycle unique.
Remarque 2. L'étape II est une conséquence facile de quelques propriétés de base du groupe multiplicatif modulo le nombre premier \(n = 2^k + 1\). Le lemme découle du fait que ce groupe est d'ordre \(2^k\), donc les puissances \(a\)-ièmes sont exactement les puissances \(2^{\nu_2(a)}\)-ièmes. En utilisant l'existence d'une racine primitive \(g\) modulo \(n\), on voit que l'application de \(\{1, 2, \ldots, n - 1\}\) dans lui-même qui envoie \(a\) sur \(g^a \bmod n\) est une bijection qui envoie \(A_i\) sur \(B_i\) pour tout \(i \in \{0, \ldots, k\}\).