Exercice 55

1. On écrit $A - B = 2E$ et $C - D = 2F$, avec $E$ et $F$ à coefficients entiers. Alors $$AC - BD = A(C - D) + (A - B)D = 2(AF + ED).$$ Les coefficients d'un produit de polynômes sont des sommes de produits de coefficients (définition du produit, section 13.1), donc $AF + ED$ est à coefficients entiers, et $AC \equiv BD \;[2]$. On remarque aussi que la relation est transitive, puisqu'une somme de polynômes à coefficients pairs est à coefficients pairs.

2. On raisonne par récurrence sur $k$, le cas $k = 0$ étant une égalité. Si $(1 + X)^{2^{k}} \equiv 1 + X^{2^{k}} \;[2]$, la question 1, appliquée avec $A = C = (1 + X)^{2^{k}}$ et $B = D = 1 + X^{2^{k}}$, donne $$(1 + X)^{2^{k + 1}} \equiv \big(1 + X^{2^{k}}\big)^{2} = 1 + 2X^{2^{k}} + X^{2^{k + 1}} \equiv 1 + X^{2^{k + 1}} \;[2].$$

3. Comme $(1 + X)^{n} = \prod_{i} (1 + X)^{2^{k_{i}}}$, la question 2 et la question 1, appliquée $s - 1$ fois, donnent la congruence annoncée. En développant le produit, on choisit dans chaque facteur le terme $1$ ou le terme $X^{2^{k_{i}}}$ : à chaque partie $I$ de $[\![1\,;s]\!]$ correspond le monôme $X^{e_{I}}$, avec $e_{I} = \sum_{i \in I} 2^{k_{i}}$, et $$\prod_{i = 1}^{s} \big(1 + X^{2^{k_{i}}}\big) = \sum_{I \subset [\![1\,;s]\!]} X^{e_{I}}.$$ Si $e_{I} = e_{J}$, les deux sommes sont deux écritures en base $2$ du même entier, donc $I = J$ par unicité de l'écriture. Les $2^{s}$ parties de $[\![1\,;s]\!]$ donnent ainsi $2^{s}$ exposants distincts, tous compris entre $0$ et $n$.

4. Notons $\mathcal{E}$ l'ensemble des exposants $e_{I}$. D'après la question 3, le coefficient de $X^{k}$ dans le produit vaut $1$ si $k \in \mathcal{E}$ et $0$ sinon. La congruence de la question 3 dit que, pour tout $k \in [\![0\,;n]\!]$, l'entier $\binom{n}{k} - \mathbf{1}_{\mathcal{E}}(k)$ est pair : $\binom{n}{k}$ est impair si et seulement si $k \in \mathcal{E}$. $$\boxed{\mathrm{card}\Big\{k \in [\![0\,;n]\!] \Bigm| \tbinom{n}{k} \text{ impair}\Big\} = 2^{s}, \quad s \text{ nombre de chiffres } 1 \text{ de } n \text{ en base } 2}$$

5. On a $2026 = 2^{10} + 2^{9} + 2^{8} + 2^{7} + 2^{6} + 2^{5} + 2^{3} + 2^{1}$, qui comporte huit chiffres $1$ en base $2$. $$\boxed{\text{la ligne } 2026 \text{ contient } 2^{8} = 256 \text{ coefficients impairs sur } 2027}$$ Les coefficients sont tous impairs si et seulement si $2^{s} = n + 1$. Or $s$ puissances de $2$ distinctes ont une somme au moins égale à $2^{0} + 2^{1} + \cdots + 2^{s - 1} = 2^{s} - 1$, avec égalité seulement si ce sont exactement ces puissances. Donc $n \geqslant 2^{s} - 1$, avec égalité si et seulement si $\{k_{1}, \dots, k_{s}\} = [\![0\,;s - 1]\!]$. $$\boxed{\text{tous les } \tbinom{n}{k} \text{ sont impairs} \iff n = 2^{s} - 1, \ s \in \mathbb{N}^{*}}$$ On le vérifie sur les lignes $1$, $3$ et $7$ du triangle de Pascal : $1, 3, 3, 1$ et $1, 7, 21, 35, 35, 21, 7, 1$. À l'opposé, pour $n = 2^{s}$, seuls les deux coefficients extrêmes sont impairs.

À retenir. La question 2 généralise la proposition 13 du chapitre 12 pour $p = 2$ : la congruence $(1 + X)^{2} \equiv 1 + X^{2}$ exprime que $2$ divise le coefficient binomial central de la ligne $2$, et l'élévation au carré répétée la propage aux puissances de $2$. Calculer « modulo $2$ » sur les coefficients d'un polynôme permet de lire d'un coup la parité de toute une ligne du triangle de Pascal.