Aller au contenu

Shortlist 2011, N7

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 2011 (avec solutions), p. 72 (page 73 du PDF)

Énoncé

Let \(p\) be an odd prime number. For every integer \(a\), define the number

\[S_a = \frac{a}{1} + \frac{a^2}{2} + \cdots + \frac{a^{p-1}}{p-1}.\]

Let \(m\) and \(n\) be integers such that

\[S_3 + S_4 - 3S_2 = \frac{m}{n}.\]

Prove that \(p\) divides \(m\).

Indices : les idées clés
  • Congruences de fractions : \(\frac{1}{p}\binom{p}{k} \equiv \frac{(-1)^{k-1}}{k} \pmod p\), ce qui donne la formule \(S_a \equiv \frac{(a - 1)^p - a^p + 1}{p} \pmod p\).
  • Carré parfait : la combinaison demandée vaut \(-\frac{(2^p - 2)^2}{p}\) modulo \(p\), et \(p^2 \mid (2^p - 2)^2\) par Fermat (une valuation de plus que nécessaire).
  • Solution 2 : le lemme \(S_{a+1} \equiv S_{-a}\), puis un découpage selon la parité de \(k\) et la réindexation \(m = \ell + \frac{p-1}{2}\) donnent \(S_3 - 3S_2 \equiv -S_4\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions).

Solution 1

Pour des nombres rationnels \(p_1/q_1\) et \(p_2/q_2\) dont les dénominateurs \(q_1\), \(q_2\) ne sont pas divisibles par \(p\), on écrit \(p_1/q_1 \equiv p_2/q_2 \pmod p\) si le numérateur \(p_1q_2 - p_2q_1\) de leur différence est divisible par \(p\).

Commençons par trouver une formule explicite pour le résidu de \(S_a\) modulo \(p\). Remarquons d'abord que, pour tout \(k = 1, \ldots, p - 1\), le nombre \(\binom{p}{k}\) est divisible par \(p\), et que

\[\frac{1}{p}\binom{p}{k} = \frac{(p - 1)(p - 2) \cdots (p - k + 1)}{k!} \equiv \frac{(-1) \cdot (-2) \cdots (-k + 1)}{k!} = \frac{(-1)^{k-1}}{k} \pmod p.\]

On a donc

\[S_a = -\sum_{k=1}^{p-1} \frac{(-a)^k (-1)^{k-1}}{k} \equiv -\sum_{k=1}^{p-1} (-a)^k \cdot \frac{1}{p}\binom{p}{k} \pmod p.\]

Le nombre du membre de droite est entier. Par la formule du binôme, on l'exprime ainsi :

\[-\sum_{k=1}^{p-1} (-a)^k \cdot \frac{1}{p}\binom{p}{k} = -\frac{1}{p}\left(-1 - (-a)^p + \sum_{k=0}^{p} (-a)^k \binom{p}{k}\right) = \frac{(a - 1)^p - a^p + 1}{p},\]

puisque \(p\) est impair. On a donc

\[S_a \equiv \frac{(a - 1)^p - a^p + 1}{p} \pmod p.\]

Enfin, avec cette formule, on obtient

\[S_3 + S_4 - 3S_2 \equiv \frac{(2^p - 3^p + 1) + (3^p - 4^p + 1) - 3(1^p - 2^p + 1)}{p} = \frac{4 \cdot 2^p - 4^p - 4}{p} = -\frac{(2^p - 2)^2}{p} \pmod p.\]

D'après le petit théorème de Fermat, \(p \mid 2^p - 2\), donc \(p^2 \mid (2^p - 2)^2\), et par conséquent \(S_3 + S_4 - 3S_2 \equiv 0 \pmod p\). \(\blacksquare\)

Solution 2

On peut résoudre le problème sans trouver de formule explicite pour \(S_a\). Il suffit d'établir la propriété suivante.

Lemme. Pour tout entier \(a\), on a \(S_{a+1} \equiv S_{-a} \pmod p\).

Preuve. Développons \(S_{a+1}\) par la formule du binôme :

\[S_{a+1} = \sum_{k=1}^{p-1} \frac{1}{k}\sum_{j=0}^{k}\binom{k}{j}a^j = \sum_{k=1}^{p-1}\left(\frac{1}{k} + \sum_{j=1}^{k} a^j \cdot \frac{1}{k}\binom{k}{j}\right) = \sum_{k=1}^{p-1}\frac{1}{k} + \sum_{j=1}^{p-1} a^j \sum_{k=j}^{p-1}\frac{1}{k}\binom{k}{j}.\]

Remarquons que \(\frac{1}{k} + \frac{1}{p - k} = \frac{p}{k(p - k)} \equiv 0 \pmod p\) pour tout \(1 \leq k \leq p - 1\) ; la première somme est donc nulle modulo \(p\). Pour la seconde somme, on utilise la relation \(\frac{1}{k}\binom{k}{j} = \frac{1}{j}\binom{k-1}{j-1}\) pour obtenir

\[S_{a+1} \equiv \sum_{j=1}^{p-1}\frac{a^j}{j}\sum_{k=1}^{p-1}\binom{k-1}{j-1} \pmod p.\]

Enfin, de la relation

\[\sum_{k=1}^{p-1}\binom{k-1}{j-1} = \binom{p-1}{j} = \frac{(p - 1)(p - 2) \cdots (p - j)}{j!} \equiv (-1)^j \pmod p,\]

on obtient

\[S_{a+1} \equiv \sum_{j=1}^{p-1}\frac{a^j(-1)^j}{j} = S_{-a}. \qquad \square\]

(Le livret laisse un facteur \(a^k\) en trop à la fin du premier développement et écrit \(j!\) au lieu de \(j\) dans la dernière somme.)

Revenons au problème. D'après le lemme,

\[S_3 - 3S_2 \equiv S_{-2} - 3S_2 = \sum_{\substack{1 \leq k \leq p-1 \\ k \text{ pair}}} \frac{-2 \cdot 2^k}{k} + \sum_{\substack{1 \leq k \leq p-1 \\ k \text{ impair}}} \frac{-4 \cdot 2^k}{k} \pmod p. \tag{1}\]

La première somme de (1) s'écrit

\[\sum_{\ell=1}^{(p-1)/2} \frac{-2 \cdot 2^{2\ell}}{2\ell} = -\sum_{\ell=1}^{(p-1)/2} \frac{4^\ell}{\ell}.\]

Ensuite, en utilisant le petit théorème de Fermat, on développe la seconde somme de (1) :

\[-\sum_{\ell=1}^{(p-1)/2} \frac{2^{2\ell+1}}{2\ell - 1} \equiv -\sum_{\ell=1}^{(p-1)/2} \frac{2^{p+2\ell}}{p + 2\ell - 1} = -\sum_{m=(p+1)/2}^{p-1} \frac{2 \cdot 4^m}{2m} = -\sum_{m=(p+1)/2}^{p-1} \frac{4^m}{m} \pmod p\]

(on a posé ici \(m = \ell + \frac{p-1}{2}\)). Donc

\[S_3 - 3S_2 \equiv -\sum_{\ell=1}^{(p-1)/2} \frac{4^\ell}{\ell} - \sum_{m=(p+1)/2}^{p-1} \frac{4^m}{m} = -S_4 \pmod p,\]

ce qu'il fallait démontrer. \(\blacksquare\)