Shortlist 2023, N3¶

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

Concepts : Valuations p-adiques et lemme LTE · Partie entière et majorations · Ordre d'un élément et racines primitives

Solution officielle : Shortlist officielle 2023 (avec solutions), p. 85 (page 87 du PDF)

Énoncé¶

For positive integers \(n\) and \(k \geq 2\) define \(E_k(n)\) as the greatest exponent \(r\) such that \(k^r\) divides \(n!\). Prove that there are infinitely many \(n\) such that \(E_{10}(n) > E_9(n)\) and infinitely many \(m\) such that \(E_{10}(m) < E_9(m)\).

Indices : les idées clés

Formule de Legendre : \(v_p(n!) = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots\), avec \(E_{10}(n) = v_5(n!)\) et \(E_9(n) = \lfloor v_3(n!)/2 \rfloor\).
Parties entières : pour \(n\) puissance de \(5\), \(v_5(n!) = \frac{n-1}{4}\) exactement, tandis que \(v_3(n!) < \frac{n}{2}\) avec une perte contrôlée par le reste de \(n\) modulo \(3\).
Choisir \(n\) avec de bons restes : \(n = 5^{2l-1} \equiv 2 \pmod 3\) et \(m = 3^{4l-2} \equiv 4 \pmod 5\) (solution 1).
Ordre et racines de l'unité (solution 2) : \(5^{3^{b-1}} \equiv -1 \pmod{3^b}\), ce qui fait perdre environ \(b\) dans la formule de Legendre.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2023 (deux solutions et une remarque).

Solution 1¶

Notons \(v_p(m)\) la valuation \(p\)-adique de \(m\). D'après la formule de Legendre, pour \(p\) premier,

\[v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots\]

On a \(E_9(n) = \left\lfloor \frac{v_3(n!)}{2} \right\rfloor\). De plus \(v_5(n!) \leq v_2(n!)\) et \(E_{10}(n) = \min\left(v_5(n!), v_2(n!)\right)\), donc \(E_{10}(n) = v_5(n!)\).

Des \(n\) avec \(E_{10}(n) > E_9(n)\). Soit \(l\) un entier positif et \(n = 5^{2l-1}\). Alors

\[E_{10}(n) = v_5(n!) = 5^{2l-2} + 5^{2l-3} + \cdots + 5 + 1 = \frac{5^{2l-1} - 1}{4} = \frac{n-1}{4}.\]

Comme \(n = 5^{2l-1} \equiv 2 \pmod 3\), on a \(\left\lfloor \frac{n}{3} \right\rfloor = \frac{n-2}{3}\), d'où, en majorant les autres parties entières par les quotients exacts,

\[v_3(n!) = \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n}{3^2} \right\rfloor + \left\lfloor \frac{n}{3^3} \right\rfloor + \cdots < \frac{n-2}{3} + \frac{n}{3^2} + \frac{n}{3^3} + \cdots = \frac{n}{2} - \frac{2}{3}.\]

On en déduit

\[E_9(n) = \left\lfloor \frac{v_3(n!)}{2} \right\rfloor \leq \frac{v_3(n!)}{2} \leq \frac{n}{4} - \frac{1}{3} < \frac{n}{4} - \frac{1}{4} = E_{10}(n).\]

Des \(m\) avec \(E_{10}(m) < E_9(m)\). Posons maintenant \(m = 3^{4l-2}\). Alors

\[v_3(m!) = 3^{4l-3} + 3^{4l-4} + \cdots + 3 + 1 = \frac{3^{4l-2} - 1}{2} = \frac{m-1}{2}.\]

Comme \(m = 9^{2l-1} \equiv 1 \pmod 4\), on a \(E_9(m) = \left\lfloor \frac{v_3(m!)}{2} \right\rfloor = \left\lfloor \frac{m-1}{4} \right\rfloor = \frac{m-1}{4}\). Par ailleurs \(m = 9^{2l-1} \equiv (-1)^{2l-1} = -1 \equiv 4 \pmod 5\), donc \(\left\lfloor \frac{m}{5} \right\rfloor = \frac{m-4}{5}\). Ainsi

\[E_{10}(m) = v_5(m!) = \left\lfloor \frac{m}{5} \right\rfloor + \left\lfloor \frac{m}{5^2} \right\rfloor + \cdots < \frac{m-4}{5} + \frac{m}{5^2} + \cdots = \frac{m}{4} - \frac{4}{5} < \frac{m}{4} - \frac{1}{4} = E_9(m).\]

Les entiers \(n = 5^{2l-1}\) et \(m = 3^{4l-2}\), pour \(l = 1, 2, 3, \ldots\), fournissent une infinité d'exemples de chaque sorte. \(\blacksquare\)

Solution 2¶

On reprend les notations de la solution 1 et l'on considère deux autres suites d'entiers.

Premier cas. Soit \(n = 5^{3^{b-1}}\) avec \(b \geq 2\). Montrons que \(n \equiv -1 \pmod{3^b}\). Comme \(\varphi(3^b) = 2 \cdot 3^{b-1}\), on a \(n^2 = 5^{\varphi(3^b)} \equiv 1 \pmod{3^b}\), donc \(n \equiv \pm 1 \pmod{3^b}\) (les seules racines carrées de \(1\) modulo \(3^b\) sont \(\pm 1\)). Et \(5\) n'est pas un carré modulo \(3\) : \(n \equiv 2^{3^{b-1}} \equiv -1 \pmod 3\). Donc \(n \equiv -1 \pmod{3^b}\), et a fortiori \(n \equiv -1 \pmod{3^i}\) pour \(i \leq b\), c'est-à-dire \(\left\lfloor \frac{n}{3^i} \right\rfloor = \frac{n - (3^i - 1)}{3^i}\). Par la formule de Legendre,

\[v_3(n!) = \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n}{3^2} \right\rfloor + \cdots < \frac{n-2}{3} + \frac{n-8}{9} + \cdots + \frac{n - (3^b - 1)}{3^b} + \frac{n}{3^{b+1}} + \cdots < \frac{n}{2} - b + \frac{1}{2},\]

car chacun des \(b\) premiers termes perd \(1 - 3^{-i}\) et \(\sum_{i \geq 1} 3^{-i} = \frac{1}{2}\). Comme \(n\) est une puissance de \(5\), \(E_{10}(n) = \frac{n-1}{4}\) (comme dans la solution 1), et, puisque \(b \geq 2\),

\[E_{10}(n) = \frac{n-1}{4} > \frac{n + 1 - 2b}{4} > \frac{v_3(n!)}{2} \geq E_9(n).\]

Second cas. De même, soit \(m = 3^{2 \cdot 5^{b-1}}\) avec \(b \geq 2\). On a \(m^2 = 3^{\varphi(5^b)} \equiv 1 \pmod{5^b}\), donc \(m \equiv \pm 1 \pmod{5^b}\), et \(m = 9^{5^{b-1}} \equiv (-1)^{5^{b-1}} = -1 \pmod 5\) ; ainsi \(m \equiv -1 \pmod{5^b}\). Alors

\[E_{10}(m) = \left\lfloor \frac{m}{5} \right\rfloor + \left\lfloor \frac{m}{5^2} \right\rfloor + \cdots < \frac{m-4}{5} + \frac{m-24}{25} + \cdots + \frac{m - (5^b - 1)}{5^b} + \frac{m}{5^{b+1}} + \cdots < \frac{m}{4} - b + \frac{1}{4},\]

et, \(m\) étant une puissance paire de \(3\), \(E_9(m) = \frac{m-1}{4} > E_{10}(m)\). \(\blacksquare\)

Remarques¶

Remarque. La solution 2 montre davantage : pour tout réel \(B > 0\), il existe une infinité d'entiers \(n\) et \(m\) tels que \(E_{10}(n) - E_9(n) > B\) et \(E_{10}(m) - E_9(m) < -B\) (prendre \(b\) grand).