Aller au contenu

Shortlist 2007, N4

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

Concepts : Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 58 (page 59 du PDF)

Énoncé

For every integer \(k \geq 2\), prove that \(2^{3k}\) divides the number

\[\binom{2^{k+1}}{2^k} - \binom{2^k}{2^{k-1}} \tag{1}\]

but \(2^{3k+1}\) does not.

Indices : les idées clés
  • Doubles factorielles : avec \((2n)! = 2^nn!(2n - 1)!!\), l'expression (1) s'écrit \(\frac{2^{2^k}(2^k - 1)!!}{(2^k)!}\) fois la différence de deux produits d'impairs.
  • Valuation 2-adique : \(v_2((2^n)!) = 2^n - 1\), donc le premier facteur a valuation \(1\).
  • Polynôme impair : la différence vaut \(P(2^k)\) avec \(P(x) = x^3Q(x) + cx\) ; le coefficient \(c = 2^kS\) vérifie \(S \equiv -(2^k - 1)!!\frac{2^{k-1}(2^{2k} - 1)}{3}\) modulo \(2^k\), donc \(v_2(c) = 2k - 1\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque).

Solution

On utilise les notations \((2n - 1)!! = 1 \cdot 3 \cdots (2n - 1)\) et \((2n)!! = 2 \cdot 4 \cdots (2n) = 2^nn!\) pour tout entier \(n > 0\). Remarquons que \((2n)! = (2n)!!\,(2n - 1)!! = 2^nn!\,(2n - 1)!!\).

Pour tout entier \(n > 0\), on a

\[\binom{4n}{2n} = \frac{(4n)!}{(2n)!^2} = \frac{2^{2n}(2n)!\,(4n - 1)!!}{(2n)!^2} = \frac{2^{2n}}{(2n)!}(4n - 1)!!,\]
\[\binom{2n}{n} = \frac{1}{(2n)!}\left(\frac{(2n)!}{n!}\right)^2 = \frac{1}{(2n)!}\big(2^n(2n - 1)!!\big)^2 = \frac{2^{2n}}{(2n)!}(2n - 1)!!^2.\]

L'expression (1) se réécrit donc

\[\begin{aligned} \binom{2^{k+1}}{2^k} - \binom{2^k}{2^{k-1}} &= \frac{2^{2^k}}{(2^k)!}(2^{k+1} - 1)!! - \frac{2^{2^k}}{(2^k)!}(2^k - 1)!!^2 \\ &= \frac{2^{2^k}(2^k - 1)!!}{(2^k)!} \cdot \Big((2^k + 1)(2^k + 3) \cdots (2^k + 2^k - 1) - (2^k - 1)(2^k - 3) \cdots (2^k - 2^k + 1)\Big). \end{aligned} \tag{2}\]

Calculons l'exposant de \(2\) dans la décomposition en facteurs premiers de chaque facteur (le premier est un rationnel, pas forcément entier ; ce n'est pas important).

Montrons d'abord par récurrence sur \(n\) que l'exposant de \(2\) dans \((2^n)!\) vaut \(2^n - 1\). Le cas de base \(n = 1\) est trivial. Supposons \((2^n)! = 2^{2^n - 1}(2d + 1)\) pour un entier \(d\). On a alors

\[(2^{n+1})! = 2^{2^n}(2^n)!\,(2^{n+1} - 1)!! = 2^{2^n}2^{2^n - 1} \cdot (2d + 1)(2^{n+1} - 1)!! = 2^{2^{n+1} - 1} \cdot (2q + 1)\]

pour un entier \(q\). Cela termine l'hérédité.

L'exposant de \(2\) dans le premier facteur de (2) est donc \(2^k - (2^k - 1) = 1\).

Le second facteur de (2) peut être vu comme la valeur en \(x = 2^k\) du polynôme

\[P(x) = (x + 1)(x + 3) \cdots (x + 2^k - 1) - (x - 1)(x - 3) \cdots (x - 2^k + 1). \tag{3}\]

Rassemblons quelques informations sur \(P(x)\).

Remarquons que \(P(-x) = -P(x)\), puisque \(k \geq 2\). Donc \(P(x)\) est une fonction impaire, et ses coefficients non nuls ne portent que sur les puissances impaires de \(x\). Donc \(P(x) = x^3Q(x) + cx\), où \(Q(x)\) est un polynôme à coefficients entiers.

Calculons l'exposant de \(2\) dans \(c\). On a

\[c = 2(2^k - 1)!!\sum_{i=1}^{2^{k-1}}\frac{1}{2i - 1} = (2^k - 1)!!\sum_{i=1}^{2^{k-1}}\left(\frac{1}{2i - 1} + \frac{1}{2^k - 2i + 1}\right) = (2^k - 1)!!\sum_{i=1}^{2^{k-1}}\frac{2^k}{(2i - 1)(2^k - 2i + 1)} = 2^k\sum_{i=1}^{2^{k-1}}\frac{(2^k - 1)!!}{(2i - 1)(2^k - 2i + 1)} = 2^kS.\]

Pour tout entier \(i = 1, \ldots, 2^{k-1}\), notons \(a_{2i-1}\) l'inverse de \(2i - 1\) modulo \(2^k\). Évidemment, quand \(2i - 1\) parcourt tous les résidus impairs, \(a_{2i-1}\) aussi ; donc

\[S = \sum_{i=1}^{2^{k-1}}\frac{(2^k - 1)!!}{(2i - 1)(2^k - 2i + 1)} \equiv -\sum_{i=1}^{2^{k-1}}\frac{(2^k - 1)!!}{(2i - 1)^2} \equiv -\sum_{i=1}^{2^{k-1}}(2^k - 1)!!\,a_{2i-1}^2 = -(2^k - 1)!!\sum_{i=1}^{2^{k-1}}(2i - 1)^2 = -(2^k - 1)!!\frac{2^{k-1}(2^{2k} - 1)}{3} \pmod{2^k}.\]

L'exposant de \(2\) dans \(S\) est donc \(k - 1\), de sorte que \(c = 2^kS = 2^{2k-1}(2t + 1)\) pour un certain entier \(t\).

Finalement, on obtient

\[P(2^k) = 2^{3k}Q(2^k) + 2^kc = 2^{3k}Q(2^k) + 2^{3k-1}(2t + 1),\]

qui est divisible exactement par \(2^{3k-1}\). L'exposant de \(2\) dans (2) est donc \(1 + (3k - 1) = 3k\). \(\blacksquare\)

Remarque

On sait que (1) est divisible par \(2^{2k}\) ; mais cela n'aide pas à résoudre le problème.