Shortlist 2008, N4¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE
Solution officielle : Shortlist officielle 2008 (avec solutions), p. 47 (page 48 du PDF)
Énoncé¶
Let \(n\) be a positive integer. Show that the numbers
are congruent modulo \(2^n\) to \(1, 3, 5, \ldots, 2^n - 1\) in some order.
Indices : les idées clés
- Deux congruences : \(\binom{2^n - 1}{2k} + \binom{2^n - 1}{2k + 1} \equiv 0\) et \(\binom{2^n - 1}{2k} \equiv (-1)^k\binom{2^{n-1} - 1}{k} \pmod{2^n}\).
- Récurrence sur \(n\) : avec \(a_k = \binom{2^{n-1} - 1}{k}\) et \(b_m = \binom{2^n - 1}{m}\), on a \(b_m \equiv a_{\lfloor m/2 \rfloor}\) pour \(m \equiv 0, 3 \pmod 4\), ce qui transfère le caractère distinct.
- Valuation 2-adique : un éventuel conflit forcerait \(2^n \mid \binom{2^{n-1}}{2i + 1}\), impossible.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2008 (deux solutions et une remarque).
Solution 1¶
On sait bien que tous ces nombres sont impairs. L'affirmation que leurs restes modulo \(2^n\) forment une permutation de \(\{1, 3, \ldots, 2^n - 1\}\) revient donc simplement à dire que ces restes sont tous distincts. Montrons d'abord que
La première relation est immédiate, puisque la somme de gauche vaut \(\binom{2^n}{2k+1} = \frac{2^n}{2k+1}\binom{2^n - 1}{2k}\), qui est donc divisible par \(2^n\). Pour la seconde :
Cela prépare une preuve du résultat par récurrence sur \(n\). Le cas de base \(n = 1\) est évident. Supposons l'énoncé vrai pour \(n - 1\) et passons à \(n\), en notant \(a_k = \binom{2^{n-1} - 1}{k}\), \(b_m = \binom{2^n - 1}{m}\). L'hypothèse de récurrence dit que tous les nombres \(a_k\) (\(0 \leq k < 2^{n-2}\)) sont distincts modulo \(2^{n-1}\) ; il faut montrer que tous les nombres \(b_m\) (\(0 \leq m < 2^{n-1}\)) sont distincts modulo \(2^n\).
Les congruences (1) se réécrivent
En décalant l'exposant de la première relation de (1) de \(n\) à \(n - 1\), on a aussi la congruence \(a_{2i+1} \equiv -a_{2i} \pmod{2^{n-1}}\). On en conclut :
Si, pour certains \(j, k < 2^{n-2}\), on a \(a_k \equiv -a_j \pmod{2^{n-1}}\), alors \(\{j, k\} = \{2i, 2i + 1\}\) pour un certain \(i\). \(\quad (3)\)
C'est parce que, dans la suite \((a_k : k < 2^{n-2})\), chaque terme \(a_j\) n'est complété à \(0\) modulo \(2^{n-1}\) que par un seul autre terme \(a_k\), d'après l'hypothèse de récurrence.
D'après (2), on voit que \(b_{4i} \equiv a_{2i}\) et \(b_{4i+3} \equiv a_{2i+1} \pmod{2^n}\). Posons
Les deux dernières congruences prennent la forme unifiée
Ainsi, tous les nombres \(b_m\) pour \(m \in M\) sont distincts modulo \(2^n\), puisque les nombres \(a_k\) le sont (ils sont distincts modulo \(2^{n-1}\), donc aussi modulo \(2^n\)).
Chaque \(l \in L\) est associé à un unique \(m \in M\) en une paire de la forme \(\{2k, 2k + 1\}\). Donc (2) implique que tous les \(b_l\) pour \(l \in L\) sont aussi distincts modulo \(2^n\). Il reste à éliminer la possibilité que \(b_m \equiv b_l \pmod{2^n}\) pour certains \(m \in M\), \(l \in L\).
Supposons qu'une telle situation se produise. Soit \(m' \in M\) tel que \(\{m', l\}\) soit une paire de la forme \(\{2k, 2k + 1\}\), de sorte que (voir (2)) \(b_{m'} \equiv -b_l \pmod{2^n}\). Donc \(b_{m'} \equiv -b_m \pmod{2^n}\). Comme \(m'\) et \(m\) sont tous deux dans \(M\), on a, d'après (4), \(b_{m'} \equiv a_j\), \(b_m \equiv a_k \pmod{2^n}\) pour \(j = \lfloor m'/2 \rfloor\), \(k = \lfloor m/2 \rfloor\).
Alors \(a_j \equiv -a_k \pmod{2^n}\). Donc, d'après (3), \(j = 2i\), \(k = 2i + 1\) pour un certain \(i\) (ou l'inverse). L'égalité \(a_{2i+1} \equiv -a_{2i} \pmod{2^n}\) signifie maintenant que \(\binom{2^{n-1} - 1}{2i} + \binom{2^{n-1} - 1}{2i + 1} \equiv 0 \pmod{2^n}\). Cependant, la somme de gauche vaut \(\binom{2^{n-1}}{2i + 1}\). Un nombre de cette forme ne peut pas être divisible par \(2^n\). C'est une contradiction, qui termine l'hérédité et prouve le résultat. \(\blacksquare\)
Solution 2¶
Procédons de nouveau par récurrence, en notant pour abréger \(N = 2^{n-1}\) et en gardant les notations \(a_k = \binom{N - 1}{k}\), \(b_m = \binom{2N - 1}{m}\). Supposons le résultat vrai pour la suite \((a_0, a_1, a_2, \ldots, a_{N/2 - 1})\). Vu la symétrie \(a_{N-1-k} = a_k\), cette suite est une permutation de \((a_0, a_2, a_4, \ldots, a_{N-2})\). L'hypothèse de récurrence dit donc que cette dernière suite, prise modulo \(N\), est une permutation de \((1, 3, 5, \ldots, N - 1)\). De même, il faut montrer que \((b_0, b_2, b_4, \ldots, b_{2N-2})\), prise modulo \(2N\), est une permutation de \((1, 3, 5, \ldots, 2N - 1)\).
À la place des congruences (2), on utilise maintenant les suivantes :
Avec cela, la conclusion est immédiate : la première formule de (5), avec l'hypothèse de récurrence, montre que \((b_0, b_4, b_8, \ldots, b_{2N-4})\) modulo \(N\) est une permutation de \((1, 3, 5, \ldots, N - 1)\). La seconde formule de (5) montre alors que \((b_2, b_6, b_{10}, \ldots, b_{2N-2})\) modulo \(N\) est exactement la même permutation ; de plus, cette formule distingue modulo \(2N\) chaque \(b_{4i}\) de \(b_{4i+2}\).
Par conséquent, ces deux suites réunies représentent modulo \(2N\) une permutation de la suite \((1, 3, 5, \ldots, N - 1, N + 1, N + 3, N + 5, \ldots, N + N - 1)\), ce qui est précisément l'hérédité.
Prouvons maintenant les formules (5), en commençant par la seconde. Comme \(b_{m+1} = b_m \cdot \frac{2N - m - 1}{m + 1}\),
La congruence voulue \(b_{4i+2} \equiv b_{4i} + N\) peut être multipliée par le nombre impair \((4i + 1)(2i + 1)\), ce qui donne une chaîne de congruences successivement équivalentes :
la dernière est vérifiée, puisque \(b_{4i}\) est impair. Cela établit la seconde relation de (5).
La première se prouve par récurrence sur \(i\). Elle est vraie pour \(i = 0\). Supposons \(b_{4i} \equiv a_{2i} \pmod{2N}\) et considérons \(i + 1\) :
Les deux expressions ont la fraction \(\frac{N - 2i - 2}{2i + 2}\) comme dernier facteur. Comme \(2i + 2 < N = 2^{n-1}\), cette fraction se réduit à \(\ell/m\) avec \(\ell\) et \(m\) impairs. Pour montrer que \(b_{4i+4} \equiv a_{2i+2} \pmod{2N}\), on peut ignorer ce facteur commun \(\ell/m\). En chassant les autres dénominateurs impairs, l'affirmation se ramène à
D'après l'hypothèse de récurrence (qui dit que \(b_{4i} \equiv a_{2i} \pmod{2N}\)) et la seconde relation de (5), cela équivaut à
congruence déjà rencontrée quelques lignes plus haut. Cela termine la récurrence (sur \(i\)) et la preuve de (5), donc aussi toute la solution. \(\blacksquare\)
(La récurrence prouve en fait la première relation de (5) modulo \(2N\), ce qui est plus fort.)
Remarque¶
On peut éviter les mots « congrus modulo » dans l'énoncé en le reformulant ainsi : montrer que ces nombres ont des restes distincts dans la division par \(2^n\).