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é¶
Soit \(p\) un nombre premier impair. Pour tout entier \(a\), on pose
Soient \(m\) et \(n\) des entiers tels que
Montrer que \(p\) divise \(m\).
Énoncé original (anglais)
Let \(p\) be an odd prime number. For every integer \(a\), define the number
Let \(m\) and \(n\) be integers such that
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
On a donc
Le nombre du membre de droite est entier. Par la formule du binôme, on l'exprime ainsi :
puisque \(p\) est impair. On a donc
Enfin, avec cette formule, on obtient
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 :
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
Enfin, de la relation
on obtient
(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,
La première somme de (1) s'écrit
Ensuite, en utilisant le petit théorème de Fermat, on développe la seconde somme de (1) :
(on a posé ici \(m = \ell + \frac{p-1}{2}\)). Donc
ce qu'il fallait démontrer. \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2014 N4 ★★★☆☆ : Une infinité de termes \(\lfloor n^k / k \rfloor\) sont impairs.
- 2011 N4 ★★★☆☆ : Pour quels \(a\) existe-t-il \(a\) différences consécutives \(t(n + a + i) - t(n + i)\) de plus grands diviseurs impairs toutes divisibles par \(4\) ?
- 2008 N4 ★★★☆☆ : Les coefficients \(\binom{2^n - 1}{k}\) pour \(k < 2^{n-1}\) sont, modulo \(2^n\), les impairs dans un certain ordre.
- 2025 N7 ★★★★☆ · OIM P3 : Les fonctions telles que \(f(a)\) divise \(b^a - f(b)^{f(a)}\) : quelle est la meilleure constante \(c\) avec \(f(n) \leq cn\) ?