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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

É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\)