Aller au contenu

Shortlist 2020, N6

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Cyprus

Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · AM-GM et moyennes

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 81 (page 83 du PDF)

Énoncé

Pour un entier \(n\) strictement positif, notons \(d(n)\) le nombre de diviseurs positifs de \(n\), et \(\varphi(n)\) le nombre d'entiers strictement positifs inférieurs ou égaux à \(n\) et premiers avec \(n\). Existe-t-il une constante \(C\) telle que

\[\frac{\varphi(d(n))}{d(\varphi(n))} \leq C\]

pour tout \(n \geq 1\) ?

Énoncé original (anglais)

For a positive integer \(n\), let \(d(n)\) be the number of positive divisors of \(n\), and let \(\varphi(n)\) be the number of positive integers not exceeding \(n\) which are coprime to \(n\). Does there exist a constant \(C\) such that

\[\frac{\varphi(d(n))}{d(\varphi(n))} \leq C\]

for all \(n \geq 1\)?

Indices : les idées clés
  • Fonctions arithmétiques : formules multiplicatives de \(d\) et \(\varphi\) ; on choisit \(n\) pour que \(d(n)\) soit une puissance de \(2\) (fois une puissance d'un grand premier) et que \(\varphi(n)\) n'ait que de petits facteurs premiers.
  • Exposant énorme (solution 1) : avec \(n = (p_1 \cdots p_k)^{q-1} p_{k+1} \cdots p_{k+s}\), le rapport tend vers \(2^{s-1}\) quand le premier \(q\) tend vers l'infini.
  • Beaucoup de premiers entre \(N\) et \(2N\) (solution 1) : conséquence de la divergence de \(\sum 1/p\).
  • AM-GM (solution 2) : majore \(d(\varphi(n))\), combinée au théorème des nombres premiers.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).

Réponse. Non, une telle constante n'existe pas.

Solution 1

Fixons \(N > 1\) ; soient \(p_1, \ldots, p_k\) tous les nombres premiers entre \(1\) et \(N\), et \(p_{k+1}, \ldots, p_{k+s}\) tous les premiers entre \(N + 1\) et \(2N\). Pour \(j \leq k + s\), tous les diviseurs premiers de \(p_j - 1\) sont au plus \(N\), donc

\[\prod_{j=1}^{k+s} (p_j - 1) = \prod_{i=1}^{k} p_i^{c_i}\]

pour certains exposants fixés \(c_1, \ldots, c_k\). Choisissons un nombre premier \(q\) très grand et considérons

\[n = (p_1 \cdots p_k)^{q-1} \cdot (p_{k+1} \cdots p_{k+s}).\]

Par les formules des fonctions arithmétiques \(d\) et \(\varphi\) :

\[\varphi(d(n)) = \varphi(q^k \cdot 2^s) = q^{k-1}(q - 1) 2^{s-1}\]

et

\[d(\varphi(n)) = d\left((p_1 \cdots p_k)^{q-2} \prod_{i=1}^{k+s} (p_i - 1)\right) = d\left(\prod_{i=1}^{k} p_i^{q-2+c_i}\right) = \prod_{i=1}^{k} (q - 1 + c_i),\]

donc

\[\frac{\varphi(d(n))}{d(\varphi(n))} = \frac{q^{k-1}(q - 1) 2^{s-1}}{\prod_{i=1}^{k} (q - 1 + c_i)} = 2^{s-1} \cdot \frac{q - 1}{q} \cdot \prod_{i=1}^{k} \frac{q}{q - 1 + c_i},\]

quantité aussi proche que l'on veut de \(2^{s-1}\) quand \(q\) est assez grand. Il reste à montrer que \(s\) peut être arbitrairement grand, c'est-à-dire qu'il peut y avoir arbitrairement beaucoup de nombres premiers entre \(N\) et \(2N\).

Cela découle par exemple du fait bien connu que \(\sum_{p \in \mathbb{P}} \frac{1}{p} = \infty\), la somme portant sur l'ensemble \(\mathbb{P}\) des nombres premiers. En effet, si pour une constante \(C\) il y avait toujours au plus \(C\) premiers entre \(2^\ell\) et \(2^{\ell+1}\), on aurait

\[\sum_{p \in \mathbb{P}} \frac{1}{p} = \sum_{\ell=0}^{\infty} \sum_{\substack{p \in \mathbb{P} \\ p \in [2^\ell, 2^{\ell+1})}} \frac{1}{p} \leq \sum_{\ell=0}^{\infty} \frac{C}{2^\ell} < \infty,\]

ce qui est une contradiction. \(\blacksquare\)

Solution 2

On utilise le théorème des nombres premiers : \(\pi(m) = \frac{m}{\log m}(1 + o(1))\) quand \(m \to \infty\), où \(\pi(m)\) est le nombre de premiers au plus égaux à \(m\) et \(\log\) le logarithme népérien.

Soit \(m > 5\) un grand entier et \(n := p_1 p_2 \cdots p_{\pi(m)}\) le produit de tous les premiers au plus égaux à \(m\). Alors \(\varphi(d(n)) = \varphi\left(2^{\pi(m)}\right) = 2^{\pi(m) - 1}\). Considérons

\[\varphi(n) = \prod_{k=1}^{\pi(m)} (p_k - 1) = \prod_{s=1}^{\pi(m/2)} q_s^{\alpha_s},\]

où \(q_1, \ldots, q_{\pi(m/2)}\) sont les premiers au plus égaux à \(m/2\). Chaque facteur \(p_k - 1\) apporte au plus un premier \(q_s > \sqrt{m}\) au produit \(\prod_s q_s^{\alpha_s}\) (car \(p_k - 1 < m\)), donc

\[\sum_{s :\, q_s > \sqrt{m}} \alpha_s \leq \pi(m) \quad \Longrightarrow \quad \sum_{s :\, q_s > \sqrt{m}} (1 + \alpha_s) \leq \pi(m) + \pi(m/2).\]

Par AM-GM puis l'inégalité \((A/x)^x \leq e^{A/e}\), on obtient

\[\prod_{s :\, q_s > \sqrt{m}} (\alpha_s + 1) \leq \left(\frac{\pi(m) + \pi(m/2)}{\ell}\right)^\ell \leq \exp\left(\frac{\pi(m) + \pi(m/2)}{e}\right),\]

où \(\ell\) est le nombre de facteurs du produit.

Précision ajoutée : le livret dit « \(\ell\) est le nombre de premiers de l'intervalle \((\sqrt{m}, m]\) » ; c'est le nombre de premiers \(q_s\) de \((\sqrt{m}, m/2]\) qui intervient, et la majoration finale vaut quel que soit \(\ell\).

Pour les \(i\) tels que \(q_i < \sqrt{m}\), on utilise la majoration triviale \(\alpha_i \leq \log_2(\varphi(n)) \leq \log_2 n < \log_2(m^m) < m^2\), d'où

\[\prod_{s=1}^{\pi(\sqrt{m})} (\alpha_s + 1) \leq \left(m^2\right)^{\sqrt{m}} = m^{2\sqrt{m}}.\]

En rassemblant,

\[d(\varphi(n)) = \prod_{s=1}^{\pi(m/2)} (\alpha_s + 1) \leq \exp\left(2\sqrt{m} \cdot \log m + \frac{\pi(m) + \pi(m/2)}{e}\right).\]

Le théorème des nombres premiers donne alors

\[\limsup_{m \to \infty} \frac{\log(d(\varphi(n)))}{m / \log m} \leq \limsup_{m \to \infty} \frac{2\sqrt{m} \cdot \log m}{m / \log m} + \limsup_{m \to \infty} \frac{\pi(m) + \pi(m/2)}{e \cdot m / \log m} = \frac{3}{2e},\]

tandis que, toujours par ce théorème,

\[\liminf_{m \to \infty} \frac{\log(\varphi(d(n)))}{m / \log m} = \liminf_{m \to \infty} \frac{\log\left(2^{\pi(m) - 1}\right)}{m / \log m} = \log 2.\]

Comme \(\frac{3}{2e} < \frac{3}{5} < \log 2\), le rapport \(\varphi(d(n)) / d(\varphi(n))\) peut être rendu arbitrairement grand. \(\blacksquare\)

Remarques

Remarque 1 (preuves élémentaires de la dernière étape de la solution 1). On peut éviter la divergence de \(\sum 1/p\). Supposons que pour une constante \(C\) et tout \(k \geq 1\), il y ait au plus \(C\) premiers entre \(2^k\) et \(2^{k+1}\). Écrivons \((2^n)! = \prod p^{\alpha_p}\), avec \(\alpha_p = \lfloor 2^n/p \rfloor + \lfloor 2^n/p^2 \rfloor + \cdots\) (formule de Legendre). Pour \(p \in [2^k, 2^{k+1})\), on a \(\alpha_p \leq 2^n/2^k + 2^n/2^{k+1} + \cdots = 2^{n-k+1}\), donc \(p^{\alpha_p} \leq 2^{(k+1) 2^{n-k+1}}\). Avec la minoration \((2m)! \geq m(m+1) \cdots (2m-1) \geq m^m\) pour \(m = 2^{n-1}\), on obtient

\[2^{(n-1) \cdot 2^{n-1}} \leq (2^n)! \leq \prod_{k=1}^{n-1} 2^{C(k+1) 2^{n-k+1}}, \quad \text{soit} \quad \sum_{k=1}^{n-1} C(k+1) 2^{1-k} \geq \frac{n-1}{2},\]

ce qui est faux pour \(n\) grand, puisque \(C(k+1)2^{1-k} < 1/3\) sauf pour un nombre fini de \(k\).

On obtient même élémentairement bien plus : la formule de \(\nu_p(n!)\) montre que si \(p^\alpha\) est la plus grande puissance de \(p\) divisant \(\binom{n}{n/2}\), alors \(p^\alpha \leq n\). En regardant la décomposition de \(\binom{n}{n/2}\) en facteurs premiers,

\[\pi(n) \geq \log_n \binom{n}{n/2} \geq \frac{\log(2^n / n)}{\log n} \geq \frac{n}{2 \log n}.\]

En particulier, pour une infinité de \(n\), il y a au moins \(\frac{n}{3 \log n}\) premiers entre \(n\) et \(2n\).

Remarque 2. La formulation originale demandait si \(d(\varphi(n)) \geq \varphi(d(n))\) pour tous les \(n\) sauf un nombre fini. Le comité de sélection a jugé la version présentée mieux adaptée à la Shortlist.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2011 N1 ★★☆☆☆ : Le plus petit entier à \(2^k\) diviseurs divise le plus petit entier à \(2^{k+1}\) diviseurs.
  • 2006 N3 ★★☆☆☆ : La moyenne \(\frac{1}{n}\sum \lfloor n/k \rfloor\) augmente une infinité de fois et diminue une infinité de fois.
  • 2008 N5 ★★★★☆ : Trouver les fonctions telles que \(f(x)\) ait exactement \(x\) diviseurs, avec une condition de divisibilité sur \(f(xy)\).
  • 2013 N7 ★★★★★ : Le nombre de couples excellents pour une équation avec parties entières de \(a\nu\) et \(b\nu\) est la somme des diviseurs de \(m\).