Shortlist 2021, N8¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : non indiqué
Concepts : Théorème des restes chinois · Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 80 (page 80 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For a polynomial \(P(x)\) with integer coefficients let \(P^1(x) = P(x)\) and \(P^{k+1}(x) = P(P^k(x))\) for \(k \geq 1\). Find all positive integers \(n\) for which there exists a polynomial \(P(x)\) with integer coefficients such that for every integer \(m \geq 1\), the numbers \(P^m(1), \ldots, P^m(n)\) leave exactly \(\lceil n/2^m \rceil\) distinct remainders when divided by \(n\).
Indices : les idées clés
- Reformuler avec les images : en notant \(f_{m,\ell} = |P^m(\mathbb{Z}_\ell)|\), la condition équivaut à \(f_{m+1,n} = \lceil f_{m,n}/2 \rceil\) pour tout \(m \geq 0\) ; une fois que \(f_{m,\ell}\) stagne, elle reste constante.
- Restes chinois : pour \(n = ab\) avec \(\gcd(a, b) = 1\), \(f_{m,ab} = f_{m,a} f_{m,b}\), ce qui empêche la division par \(2\) à chaque étape.
- Polynômes à coefficients entiers : tout \(f : \mathbb{Z}_p \to \mathbb{Z}_p\) est polynomial ; la formule \(P(r + h) = P(r) + hP'(r) + h^2 Q(r, h)\) contrôle la taille de \(P(S_r)\) pour \(n = p^k\).
- Congruences : étude modulo \(p\) (point fixe unique \(t\) de \(P\) modulo \(p\)) et modulo les puissances de \(p\) ; argument de comptage qui exclut \(p \geq 5\), puis \(p = 3\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et une remarque).
Réponse : toutes les puissances de \(2\) et tous les nombres premiers.
Solution¶
Notons \(\mathbb{Z}_\ell\) l'ensemble des résidus modulo \(\ell\). Le polynôme \(P\) peut être vu comme une fonction \(\mathbb{Z}_\ell \to \mathbb{Z}_\ell\) pour tout entier \(\ell > 0\). Notons \(f_{m,\ell}\) le cardinal de l'ensemble \(P^m(\mathbb{Z}_\ell)\) (avec \(P^0 = \mathrm{id}\)). On remarque que \(f_{m,n} = \lceil n/2^m \rceil\) pour tout \(m \geq 1\) si et seulement si \(f_{m+1,n} = \lceil f_{m,n}/2 \rceil\) pour tout \(m \geq 0\).
Partie 1. Le polynôme existe lorsque \(n\) est une puissance de \(2\) ou un nombre premier.
Si \(n\) est une puissance de \(2\), on prend \(P(x) = 2x\).
Si \(n = p\) est un nombre premier impair, toute fonction \(f : \mathbb{Z}_p \to \mathbb{Z}_p\) coïncide avec un polynôme à coefficients entiers (interpolation modulo \(p\)). On peut donc choisir la fonction qui envoie \(x \in \{0, 1, \ldots, p-1\}\) sur \(\lfloor x/2 \rfloor\).
Partie 2. Le polynôme n'existe pas lorsque \(n\) n'est pas une puissance d'un nombre premier.
Soit \(n = ab\) avec \(a, b > 1\) et \(\gcd(a, b) = 1\). Par le théorème des restes chinois,
Remarquons aussi que si \(f_{m,\ell} = f_{m+1,\ell}\), alors \(P\) permute l'image de \(P^m\) dans \(\mathbb{Z}_\ell\), donc \(f_{s,\ell} = f_{m,\ell}\) pour tout \(s > m\). Comme \(f_{m,ab} = 1\) pour \(m\) assez grand, on a pour tout \(m\)
Choisissons le plus petit \(m\) tel que \(f_{m+1,a} = 1\) ou \(f_{m+1,b} = 1\), disons (sans perte de généralité) \(f_{m+1,a} = 1\). Alors
contradiction (on a utilisé \(f_{m,a} \geq 2\) et \(f_{m,b} \geq 2\) par minimalité de \(m\)).
Partie 3. Le polynôme n'existe pas lorsque \(n\) est une puissance d'un premier impair, sans être premier.
Soit \(n = p^k\), avec \(p \geq 3\) premier et \(k \geq 2\). Pour \(r \in \mathbb{Z}_p\), notons \(S_r\) le sous-ensemble de \(\mathbb{Z}_{p^k}\) formé des nombres congrus à \(r\) modulo \(p\), et \(|S|\) le cardinal d'un ensemble \(S\).
Affirmation. Pour tout résidu \(r\) modulo \(p\), on a soit \(|P(S_r)| = p^{k-1}\), soit \(|P(S_r)| \leq p^{k-2}\).
Preuve. Rappelons que \(P(r + h) = P(r) + hP'(r) + h^2 Q(r, h)\), où \(Q\) est un polynôme à coefficients entiers.
Si \(p \mid P'(r)\), alors \(P(r + ps) \equiv P(r) \pmod{p^2}\), donc tous les éléments de \(P(S_r)\) sont congrus modulo \(p^2\), et \(|P(S_r)| \leq p^{k-2}\).
Montrons maintenant que \(p \nmid P'(r)\) implique \(|P(S_r)| = p^{k-1}\) pour tout exposant \(k\). Supposons le contraire, \(|P(S_r)| < p^{k-1}\) pour un certain \(k > 1\), et choisissons le plus petit tel \(k\). À chaque résidu de \(P(S_r)\) associons son résidu modulo \(p^{k-1}\), et notons \(\overline{P}(S, r)\) l'ensemble obtenu. Par minimalité de \(k\), \(|\overline{P}(S, r)| = p^{k-2}\). Alors \(|P(S_r)| < p^{k-1} = p \cdot |\overline{P}(S, r)|\) : il existe \(u = P(x) \in P(S_r)\) (avec \(x \equiv r \pmod p\)) et \(t \not\equiv 0 \pmod p\) tels que \(u + p^{k-1}t \notin P(S_r)\). Or \(P(x + p^{k-1}s) \equiv u + p^{k-1} s P'(x) \pmod{p^k}\). Comme \(P(x + p^{k-1}s) \not\equiv u + p^{k-1}t \pmod{p^k}\) pour tout \(s\), la congruence \(p^{k-1} s P'(x) \equiv p^{k-1} t \pmod{p^k}\) n'a pas de solution ; donc \(sP'(x) \equiv t \pmod p\) n'a pas de solution, ce qui contredit \(p \nmid P'(r)\) (car \(P'(x) \equiv P'(r) \pmod p\)). \(\square\)
Comme l'image de \(P^m\) est réduite à un élément pour \(m\) assez grand, on peut prendre le plus petit \(m\) tel que \(|P^m(S_q)| \leq p^{k-2}\) pour tout \(q \in \mathbb{Z}_p\) ; d'après l'affirmation (appliquée à \(P^{m-1}\)), il existe alors \(r \in \mathbb{Z}_p\) avec \(|P^{m-1}(S_r)| = p^{k-1}\). On fixe désormais \(m\) et \(r\).
Comme l'image de \(P^{m-1}(\mathbb{Z}_{p^k}) \setminus P^{m-1}(S_r)\) par \(P\) contient \(P^m(\mathbb{Z}_{p^k}) \setminus P^m(S_r)\), on a
donc
d'où
Comme \(f_{i,p} = 1\) pour \(i\) assez grand, il existe exactement un \(t \in \mathbb{Z}_p\) tel que \(P(t) \equiv t \pmod p\). De plus, quand \(i\) augmente, le cardinal de l'ensemble \(\{s \in \mathbb{Z}_p \mid P^i(s) \equiv t \pmod p\}\) augmente strictement jusqu'à atteindre la valeur \(p\). Donc
Par conséquent, ou bien \(f_{m-1,p} = 1\), ou bien il existe un sous-ensemble \(X \subset \mathbb{Z}_p\) de cardinal au moins \(m\) tel que \(P^{m-1}(x) \equiv t \pmod p\) pour tout \(x \in X\).
Premier cas. \(|P^{m-1}(\mathbb{Z}_{p^k})| \leq p^{k-1} = |P^{m-1}(S_r)|\), donc \(a = 0\), contradiction.
Second cas. Soit \(Y\) l'ensemble des éléments de \(\mathbb{Z}_{p^k}\) congrus modulo \(p\) à un élément de \(X\), et \(Z = \mathbb{Z}_{p^k} \setminus Y\). Alors \(P^{m-1}(Y) \subset S_t\), \(P(S_t) \subsetneq S_t\) (sinon \(P\) permuterait \(S_t\)), donc \(|P(S_t)| \leq p^{k-2}\) par l'affirmation, et \(Z = \bigcup_{i \in \mathbb{Z}_p \setminus X} S_i\). Ainsi
Donc
et \(m < 3\). Alors \(|P^2(S_q)| \leq p^{k-2}\) pour tout \(q \in \mathbb{Z}_p\), donc
ce qui est impossible pour \(p \geq 5\). Il reste le cas \(p = 3\).
Comme précédemment, soit \(t\) l'unique résidu modulo \(3\) tel que \(P(t) \equiv t \pmod 3\). Si \(3 \nmid P'(t)\), alors \(P(S_t) = S_t\) d'après la preuve de l'affirmation, ce qui est impossible. Donc \(3 \mid P'(t)\). En substituant \(h = 3^i s\) dans la formule \(P(t + h) = P(t) + hP'(t) + h^2 Q(t, h)\), on obtient \(P(t + 3^i s) \equiv P(t) \pmod{3^{i+1}}\). Par récurrence sur \(i\), tous les éléments de \(P^i(S_t)\) sont congrus modulo \(3^{i+1}\). Ainsi \(|P^{k-1}(S_t)| = 1\).
Notons que \(f_{1,3} \leq 2\) et \(f_{2,3} \leq 1\), donc \(P^2(\mathbb{Z}_{3^k}) \subset S_t\). Par conséquent \(|P^{k+1}(\mathbb{Z}_{3^k})| \leq |P^{k-1}(S_t)| = 1\), ce qui donne \(\lceil 3^k / 2^{k+1} \rceil \leq 1\), c'est-à-dire \(3^k \leq 2^{k+1}\), impossible pour \(k \geq 2\). \(\blacksquare\)
Remarques¶
Remarque (variante du problème). Une fonction \(f : \mathbb{Z} \to \mathbb{Z}\) vérifie \(a - b \mid f(a) - f(b)\) pour tous entiers \(a \neq b\). On pose \(S_0 = \mathbb{Z}\) et, pour \(m \geq 1\), \(S_m = f(S_{m-1})\). On suppose que, pour tout \(m \geq 0\), l'ensemble \(S_m\) contient exactement \(\lceil n/2^m \rceil\) résidus distincts modulo \(n\). Trouver tous les \(n\) possibles. Réponse : toutes les puissances de nombres premiers.
Esquisse de la solution officielle. On voit encore \(f\) comme une fonction \(\mathbb{Z}_\ell \to \mathbb{Z}_\ell\), avec les mêmes notations.
- Existence pour \(n = p^k\). Pour \(x \in \mathbb{Z}_{p^k}\), écrit avec exactement \(k\) chiffres en base \(p\), soit \(\mathrm{rev}(x)\) le nombre obtenu en renversant l'ordre des chiffres, et \(f(x) = \mathrm{rev}\left(\left\lfloor \frac{\mathrm{rev}(x)}{2} \right\rfloor\right)\) (où \(\mathrm{rev}(x)\) est vu comme un entier de \([0, p^k)\)). On a \(f_{m+1,k} = \lceil f_{m,k}/2 \rceil\). Si \(p^m \mid a - b\), alors, avec \(x = \mathrm{rev}(a)\) et \(y = \mathrm{rev}(b)\), les \(m\) premiers chiffres de \(x\) et \(y\) coïncident : \(\lfloor x/p^{k-m} \rfloor = \lfloor y/p^{k-m} \rfloor\). Comme \(\lfloor \lfloor z/c \rfloor / d \rfloor = \lfloor z/(cd) \rfloor\), on obtient \(\lfloor \lfloor x/2 \rfloor / p^{k-m} \rfloor = \lfloor \lfloor y/2 \rfloor / p^{k-m} \rfloor\), donc les \(m\) derniers chiffres de \(f(a)\) et \(f(b)\) coïncident : \(p^m \mid f(a) - f(b)\).
- Relèvement à \(\mathbb{Z}\). Toute fonction \(f : \mathbb{Z}_{p^k} \to \mathbb{Z}_{p^k}\) avec \(\gcd(p^k, a - b) \mid f(a) - f(b)\) se relève en \(g : \mathbb{Z} \to \mathbb{Z}\) avec \(a - b \mid g(a) - g(b)\) et \(g \equiv f \pmod{p^k}\) : on construit \(g\) de proche en proche sur un intervalle \([a, b)\) ; pour définir \(g(b)\), on choisit pour chaque premier \(q \leq |a - b|\) l'exposant maximal \(\alpha_q\) tel qu'il existe \(c_q \in [a, b)\) avec \(q^{\alpha_q} \mid b - c_q\), puis, par le théorème des restes chinois, \(g(b) \equiv g(c_q) \pmod{q^{\alpha_q}}\) pour \(q \neq p\), et \(g(b) \equiv g(c_p) \pmod{p^{\alpha_p}}\) si \(\alpha_p \geq k\), \(g(b) \equiv f(b) \pmod{p^k}\) si \(\alpha_p < k\).
- Non-existence si \(n\) a deux facteurs premiers distincts : la preuve est identique à celle de la partie 2.