Shortlist 2019, N1¶

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

Concepts : Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2019 (avec solutions), section N1 (livret PDF)

Problème 4 de l'OIM 2019

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2019, où il était le problème 4 (jour 2).

Énoncé¶

Find all pairs \((m, n)\) of positive integers satisfying the equation

\[(2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1}) = m!\]

Indices : les idées clés

Valuations p-adiques : \(v_2(L_n) = \frac{n(n-1)}{2}\) et la formule de Legendre \(v_2(m!) < m\) forcent \(m\) à être grand (solution 1).
Encadrement par la taille (solution 1) : \(L_n < 2^{n^2}\), tandis que \(m!\) est beaucoup plus grand dès que \(n \geq 6\).
Lemme LTE (solution 2) : \(v_3(4^k - 1) = v_3(3k)\), d'où \(m \approx 3\lfloor n/2 \rfloor\) ; le premier \(31 = 2^5 - 1\) donne au contraire \(m > 3n\).
Vérifier les petits cas : pour \(n \leq 5\), un calcul direct suffit.

Solutions

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

Réponse : les seuls couples sont \((m, n) = (1, 1)\) et \((m, n) = (3, 2)\).

Notations communes. Pour un nombre premier \(p\) et un entier \(N \geq 1\), on note \(v_p(N)\) l'exposant de la plus grande puissance de \(p\) qui divise \(N\). On note \(L_n\) le membre de gauche :

\[L_n = (2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1}),\]

et l'équation s'écrit \(L_n = m!\).

Solution 1¶

On majore \(n\) en étudiant la croissance de \(v_2(L_n)\). En factorisant les puissances de \(2\),

\[L_n = 2^{1 + 2 + \cdots + (n-1)} (2^n - 1)(2^{n-1} - 1) \cdots (2^1 - 1),\]

donc, par les valuations \(2\)-adiques,

\[v_2(L_n) = 1 + 2 + \cdots + (n - 1) = \frac{n(n-1)}{2}.\]

D'autre part, la formule de Legendre donne \(v_2(m!) = \sum_{i \geq 1} \left\lfloor \frac{m}{2^i} \right\rfloor\), et en enlevant les parties entières,

\[v_2(m!) < \sum_{i=1}^{\infty} \frac{m}{2^i} = m.\]

Donc \(L_n = m!\) implique

\[\frac{n(n-1)}{2} < m. \tag{2}\]

Pour l'estimation inverse, on observe que

\[L_n = (2^n - 1)(2^n - 2) \cdots (2^n - 2^{n-1}) < (2^n)^n = 2^{n^2}.\]

Montrons que

\[2^{n^2} < \left(\frac{n(n-1)}{2}\right)! \quad \text{pour } n \geq 6. \tag{3}\]

Pour \(n = 6\) : \(2^{36} < 6{,}9 \cdot 10^{10}\) et \(\left(\frac{n(n-1)}{2}\right)! = 15! > 1{,}3 \cdot 10^{12}\). Pour \(n \geq 7\) :

\[\left(\frac{n(n-1)}{2}\right)! = 15! \cdot 16 \cdot 17 \cdots \frac{n(n-1)}{2} > 2^{36} \cdot 16^{\frac{n(n-1)}{2} - 15} = 2^{2n(n-1) - 24} = 2^{n^2} \cdot 2^{n(n-2) - 24} > 2^{n^2}.\]

En combinant (2) et (3), pour \(n \geq 6\) on obtient la contradiction

\[L_n < 2^{n^2} < \left(\frac{n(n-1)}{2}\right)! < m! = L_n.\]

Donc \(n \leq 5\). On vérifie à la main :

\[L_1 = 1 = 1!, \quad L_2 = 6 = 3!, \quad 5! < L_3 = 168 < 6!, \quad 7! < L_4 = 20\,160 < 8!, \quad 10! < L_5 = 9\,999\,360 < 11!.\]

Il y a donc exactement deux solutions : \((m, n) \in \{(1, 1), (3, 2)\}\). \(\blacksquare\)

Solution 2¶

Comme dans la solution précédente, on traite à la main les cas \(n = 1, 2, 3, 4\). On exclut \(n \geq 5\) en comparant les exposants de \(3\) et de \(31\) dans l'équation.

Rappelons le lemme LTE : pour un premier impair \(p\) et des entiers distincts \(a, b\) premiers avec \(p\) tels que \(p \mid a - b\),

\[v_p(a^k - b^k) = v_p(a - b) + v_p(k).\]

Or \(3\) divise \(2^k - 1\) si et seulement si \(k\) est pair ; de plus, par LTE,

\[v_3(2^{2k} - 1) = v_3(4^k - 1) = 1 + v_3(k) = v_3(3k).\]

D'où

\[v_3(L_n) = \sum_{2k \leq n} v_3(4^k - 1) = \sum_{k \leq \lfloor n/2 \rfloor} v_3(3k).\]

Cette dernière somme est exactement l'exposant de \(3\) dans \(\left(3\lfloor n/2 \rfloor\right)!\) (les multiples de \(3\) jusqu'à \(3\lfloor n/2 \rfloor\) sont les \(3k\)). Donc

\[v_3(m!) = v_3(L_n) = v_3\left(\left(3\left\lfloor \tfrac{n}{2} \right\rfloor\right)!\right), \quad \text{d'où} \quad 3\left\lfloor \tfrac{n}{2} \right\rfloor \leq m \leq 3\left\lfloor \tfrac{n}{2} \right\rfloor + 2. \tag{4}\]

Supposons \(n \geq 5\). Un facteur sur cinq de \(L_n\) est divisible par \(31 = 2^5 - 1\) (car \(2^5 - 1 \mid 2^{5j} - 1\)), donc \(v_{31}(L_n) \geq \lfloor n/5 \rfloor\). Alors

\[\frac{n}{10} \leq \left\lfloor \frac{n}{5} \right\rfloor \leq v_{31}(L_n) = v_{31}(m!) = \sum_{k=1}^{\infty} \left\lfloor \frac{m}{31^k} \right\rfloor < \sum_{k=1}^{\infty} \frac{m}{31^k} = \frac{m}{30}. \tag{5}\]

En combinant (4) et (5),

\[3n < m \leq \frac{3n}{2} + 2,\]

donc \(n < \frac{4}{3}\), ce qui contredit \(n \geq 5\). Les solutions sont donc \((1, 1)\) et \((3, 2)\). \(\blacksquare\)

Remarques¶

Remarque 1. On peut combiner les idées ci-dessus de bien des façons ; par exemple, (2) et (4) ensemble donnent aussi \(n < 5\). De manière générale, comparer les exposants de deux nombres premiers quelconques, ou d'un premier et l'ordre de grandeur, fournit une borne sur \(n\) et \(m\).

Remarque 2 (lien avec la théorie des groupes). Le membre de gauche est l'ordre du groupe \(GL_n(\mathbb{F}_2)\) des matrices \(n \times n\) inversibles à coefficients modulo \(2\), et le membre de droite est l'ordre du groupe symétrique \(S_m\). Le résultat montre que les seuls isomorphismes possibles entre ces groupes sont \(GL_1(\mathbb{F}_2) \cong S_1\) et \(GL_2(\mathbb{F}_2) \cong S_3\), qui existent effectivement. En général, \(GL_n(\mathbb{F}_2)\) est un groupe simple pour \(n \geq 3\), car il est isomorphe à \(PSL_n(\mathbb{F}_2)\). Une « presque-solution » intéressante : pour \(n = 4\), le membre de gauche vaut la moitié de \(8!\), ce qui correspond à un isomorphisme \(GL_4(\mathbb{F}_2) \cong A_8\) avec le groupe alterné. Mais la théorie des groupes n'est d'aucune aide pour résoudre le problème !