Shortlist 2025, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : U.S.A.
Concepts : Récurrence et constructions récursives · Divisibilité, PGCD et algorithme d'Euclide · Théorème des restes chinois
Solution officielle : Shortlist officielle 2025 (avec solutions), section N6 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For positive integers \(n\) and \(k\), let \(f_k(n)\) denote the remainder when \(n\) is divided by \(2^k - 1\). A positive integer \(n\) is grouse if
(a) Prove that there are infinitely many grouse numbers.
(b) Prove that there exists a positive integer \(M\) such that there are at most \(M/2025^{2025}\) grouse numbers less than \(M\).
Indices : les idées clés
- Construction récursive (partie (a)) : on construit \(x_k, x_{k-1}, \ldots, x_1\) en prenant à chaque étape le plus petit multiple de \(2^i - 1\) supérieur ou égal au précédent ; \(x_1\) est grouse.
- Comparer avec cette construction (partie (b), solution 1) : un nombre grouse de \([2^k, 2^{k+1})\) est au moins \(x_{\lceil k/2 \rceil}\), donc très proche de \(2^{k+1}\) ; il y en a au plus \(3 \cdot 2^{k/2}\).
- Divisibilité et PGCD (partie (b), solution 2) : \(\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a, b)} - 1\).
- Théorème des restes chinois (partie (b), solution 2) : des classes résiduelles « interdites » modulo des entiers premiers entre eux se combinent, et la proportion de classes permises devient aussi petite qu'on veut.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (une solution pour la partie (a), deux solutions pour la partie (b)).
Solution de la partie (a)¶
Il suffit de montrer que, pour tout entier \(k \geq 1\), il existe un nombre grouse supérieur ou égal à \(2^k - 1\).
Étant donnés des entiers strictement positifs \(k\) et \(m\), on construit par récurrence descendante une suite \(x_k, x_{k-1}, \ldots, x_1\) : on pose \(x_k = (2^k - 1)m\) et, pour \(i < k\), on note \(x_i\) le plus petit multiple de \(2^i - 1\) tel que \(x_i \geq x_{i+1}\).
Lemme. Pour tous entiers strictement positifs \(k\) et \(m\), le nombre \(x_1\) obtenu vérifie
Preuve. La minoration découle de \(x_1 \geq x_2 \geq \cdots \geq x_k = (2^k - 1)m\). Pour la majoration, \(x_i \leq x_{i+1} + (2^i - 2)\) pour tout \(1 \leq i \leq k - 1\), donc
Le lemme s'applique aussi en partant de n'importe quel \(x_i\) (\(1 \leq i \leq k\)), c'est-à-dire en remplaçant \(k\) par \(i\) et \(m\) par \(m'\) tel que \(x_i = (2^i - 1)m'\) : on obtient les mêmes \(x_i, x_{i-1}, \ldots, x_1\), et donc \((2^i - 1)m' \leq x_1 < (2^i - 1)(m' + 1)\).
Montrons qu'en partant d'un entier \(k \geq 1\) quelconque avec \(m = 1\) (c'est-à-dire \(x_k = 2^k - 1\)), le nombre \(x_1\) obtenu est grouse. D'après le lemme, \(f_k(x_1) = x_1 - (2^k - 1) = x_1 - x_k\). En appliquant le lemme à partir de \(x_i\), on a \(f_i(x_1) = x_1 - (2^i - 1)m' = x_1 - x_i\). Comme \(x_1 \geq x_2 \geq \cdots \geq x_k\), il vient
Pour tout \(\ell > k\), montrons que \(f_\ell(x_1) = x_1\), ce qui prouvera que \(x_1\) est grouse. Comme \(m = 1\), le lemme donne \(x_1 < (2^k - 1)(m + 1) = 2(2^k - 1)\), et \(2(2^k - 1) < 2^{k+1} - 1 \leq 2^\ell - 1\). Comme \(x_1 < 2^\ell - 1\), on a \(f_\ell(x_1) = x_1\). Donc \(x_1\) est grouse.
Ce nombre grouse vérifie \(x_1 \geq x_k = 2^k - 1\). On a donc trouvé, pour tout \(k \geq 1\), un nombre grouse au moins égal à \(2^k - 1\) : il y en a une infinité. \(\blacksquare\)
Solution 1 de la partie (b)¶
Affirmation. Soit \(k \geq 1\) un entier, et soit \(n \in [2^k, 2^{k+1})\) un nombre grouse. Alors \(n \geq 2^{k+1} - 3 \cdot 2^{k/2}\).
Preuve. Posons \(x_k = 2^k - 1\) et considérons la suite \(x_k, x_{k-1}, \ldots, x_1\) construite dans la partie (a). Comme \(2^k - 1 < n < 2^{k+1}\), on a \(f_k(n) \leq n - (2^k - 1) = n - x_k\), c'est-à-dire \(x_k \leq n - f_k(n)\). Montrons par récurrence descendante sur \(i\) que, pour tout \(1 \leq i \leq k\),
Le cas \(i = k\) est établi. Soit \(i < k\), et supposons \(x_{i+1} \leq n - f_{i+1}(n)\). Le nombre \(n - f_i(n)\) est un multiple de \(2^i - 1\) et, comme \(n\) est grouse, \(n - f_i(n) \geq n - f_{i+1}(n) \geq x_{i+1}\). Par définition de \(x_i\), on a donc \(n - f_i(n) \geq x_i\), ce qui achève la récurrence.
D'autre part, montrons que
pour tout entier \(i\) tel que \(k/2 \leq i \leq k\). C'est clair pour \(i = k\) ; procédons encore par récurrence descendante, en supposant \(i < k\) et \(x_{i+1} = (2^{i+1} - 1)(2^{k-i} - 1)\). Alors
Comme \(k/2 \leq i < k\), on a \(0 \leq 2^i - 2^{k-i} < 2^i - 1\). Donc \((2^i - 1)(2^{k+1-i} - 1)\) est le plus petit multiple de \(2^i - 1\) supérieur ou égal à \(x_{i+1}\), ce qui prouve (2).
En combinant (1) et (2) avec \(i = \lceil k/2 \rceil\), on obtient
et il reste à montrer que cette dernière quantité est au moins \(2^{k+1} - 3 \cdot 2^{k/2}\), c'est-à-dire
Si \(k = 2\ell\) est pair, \(2^{\lceil k/2 \rceil} + 2^{k+1-\lceil k/2 \rceil} = 2^\ell + 2^{\ell+1} = 3 \cdot 2^{k/2}\). Si \(k = 2\ell - 1\) est impair, \(2^{\lceil k/2 \rceil} + 2^{k+1-\lceil k/2 \rceil} = 2^{\ell+1} = 2\sqrt{2} \cdot 2^{k/2}\). L'affirmation en découle. \(\square\)
L'affirmation montre que le nombre de nombres grouse dans \([2^k, 2^{k+1})\) est au plus \(3 \cdot 2^{k/2}\). Soit \(M = 2^{b+1}\), où l'entier \(b\) sera choisi plus tard. Le nombre de nombres grouse inférieurs à \(M\) est alors au plus
Cette dernière expression est inférieure à \(M / 2025^{2025} = 2^{b+1}/2025^{2025}\) si et seulement si
La base de l'exponentielle du membre de droite est strictement supérieure à \(1\), donc c'est vrai pour \(b\) assez grand, ce qui prouve (b). \(\blacksquare\)
Solution 2 de la partie (b)¶
Disons qu'une classe résiduelle \(r\) modulo \(d\) est cuite si \(n \equiv r \pmod d\) entraîne que \(n\) n'est pas grouse. Il suffit de trouver un \(M\) tel qu'au plus \(2025^{-2025} M\) classes résiduelles modulo \(M\) ne soient pas cuites.
Lemme. Pour tout entier \(k \geq 1\), il y a au moins \(\binom{2^{2k-1} - 1}{2}\) classes résiduelles modulo \((2^{2k-1} - 1)(2^{2k+1} - 1)\) qui sont cuites.
Preuve. Soient \(i\), \(j\) des entiers tels que \(0 \leq j < i \leq 2^{2k-1} - 2\). Par définition, si \(n\) vérifie \(f_{2k-1}(n) = i\) et \(f_{2k+1}(n) = j\), alors \(n\) n'est pas grouse. D'après le résultat classique \(\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a, b)} - 1\), on a
Comme \(2^{2k-1} - 1\) et \(2^{2k+1} - 1\) sont premiers entre eux, le théorème des restes chinois montre que, pour tout couple \((i, j)\), il existe une unique classe \(r\) modulo \((2^{2k-1} - 1)(2^{2k+1} - 1)\) telle que \(r \equiv i \pmod{2^{2k-1} - 1}\) et \(r \equiv j \pmod{2^{2k+1} - 1}\). Ainsi, à chaque couple \((i, j)\) avec \(0 \leq j < i \leq 2^{2k-1} - 2\) correspond une classe cuite. (Le livret écrit ici \(1 \leq j\) ; il faut lire \(0 \leq j\), comme au début de la preuve, pour obtenir le décompte annoncé.) Il y a \(\binom{2^{2k-1} - 1}{2}\) tels couples, et les classes correspondantes modulo \((2^{2k-1} - 1)(2^{2k+1} - 1)\) sont distinctes et cuites. \(\square\)
Un nombre grouse n'appartient à aucune classe cuite, quel que soit le module. Par le théorème des restes chinois, si pour \(1 \leq i \leq \ell\) il y a \(a_i\) classes non cuites modulo \(d_i\), et si les \(d_i\) sont deux à deux premiers entre eux, alors il y a au plus \(\prod_{i=1}^{\ell} a_i\) classes non cuites modulo \(M = \prod_{i=1}^{\ell} d_i\). Autrement dit, si la proportion de classes non cuites modulo \(d_i\) est \(a_i / d_i\), la proportion de classes non cuites modulo \(M\) est au plus \(\prod_{i=1}^{\ell} a_i / d_i\).
Choisissons des \(d_i\) convenables. Définissons par récurrence \(k_1 = 2\) et
et posons
Nous allons voir que \(M = M_\ell\) convient dès que \(\ell\) est assez grand pour que \(\left(\frac{10}{11}\right)^\ell < 2025^{-2025}\).
On voit facilement que \(2k_1 - 1, 2k_1 + 1, 2k_2 - 1, 2k_2 + 1, \ldots, 2k_\ell - 1, 2k_\ell + 1\) sont deux à deux premiers entre eux. En utilisant de nouveau \(\gcd(2^a - 1, 2^b - 1) = 2^{\gcd(a, b)} - 1\), les nombres \((2^{2k_i - 1} - 1)(2^{2k_i + 1} - 1)\), \(1 \leq i \leq \ell\), sont deux à deux premiers entre eux. De plus, pour \(k \geq 2\),
Par conséquent, la proportion de classes non cuites modulo \(M\) est au plus
et l'on obtient la majoration voulue. \(\blacksquare\)