Shortlist 2019, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Netherlands
Concepts : Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2019 (avec solutions), section N5 (livret PDF)
Énoncé¶
Let \(a\) be a positive integer. We say that a positive integer \(b\) is \(a\)-good if \(\binom{an}{b} - 1\) is divisible by \(an + 1\) for all positive integers \(n\) with \(an \geq b\). Suppose \(b\) is a positive integer such that \(b\) is \(a\)-good, but \(b + 2\) is not \(a\)-good. Prove that \(b + 1\) is prime.
Indices : les idées clés
- Caractériser les entiers \(a\)-bons (solution 1) : \(b\) est \(a\)-bon si et seulement si \(b\) est pair et \(p \mid a\) pour tout premier \(p \leq b\).
- Valuations \(p\)-adiques (solution 1) : si \(p \nmid a\), on choisit \(n\) pour qu'un facteur du numérateur de \(\binom{an}{b}\) soit divisible par \(p^{t+1}\), avec \(t = v_p(b!)\), et alors \(p \mid \binom{an}{b}\).
- Calcul modulo \(an + 1\) : comme \(an \equiv -1\), on a \(an(an-1)\cdots(an-b+1) \equiv (-1)^b\, b!\), et \(b!\) est inversible quand tous les premiers \(p \leq b\) divisent \(a\).
- Théorème de Lucas (solution 2) : il donne \(p \mid \binom{an}{b}\) en choisissant les chiffres de \(an\) en base \(p\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions).
Solution 1¶
Pour \(p\) premier et \(n\) entier non nul, on note \(v_p(n)\) la valuation \(p\)-adique de \(n\) : le plus grand entier \(t\) tel que \(p^t \mid n\).
Affirmation. \(b\) est \(a\)-bon si et seulement si \(b\) est pair et \(p \mid a\) pour tout nombre premier \(p \leq b\).
La condition \(an + 1 \mid \binom{an}{b} - 1\) peut s'écrire
Supposons d'abord qu'il existe un premier \(p \leq b\) avec \(p \nmid a\). Soit \(t = v_p(b!)\). Comme \(a\) est inversible modulo \(p^{t+1}\), il existe des entiers positifs \(c\) tels que \(ac \equiv 1 \pmod{p^{t+1}}\). Prenons un tel \(c\) assez grand, puis \(n = (p-1)c\) ; alors \(an = a(p-1)c \equiv p - 1 \pmod{p^{t+1}}\) et \(an \geq b\). Comme \(p \leq b\), l'un des facteurs du numérateur \(an(an-1)\cdots(an-b+1)\) est \(an - p + 1\), qui est divisible par \(p^{t+1}\). La valuation \(p\)-adique du numérateur est donc au moins \(t+1\), alors que celle du dénominateur vaut exactement \(t\). Ainsi \(p \mid \binom{an}{b}\), donc \(p \nmid \binom{an}{b} - 1\). Comme \(p \mid an + 1\), on obtient \(an + 1 \nmid \binom{an}{b} - 1\) : \(b\) n'est pas \(a\)-bon.
Supposons au contraire que \(p \mid a\) pour tout premier \(p \leq b\). Alors chaque facteur de \(b!\) est premier avec \(an + 1\), donc inversible modulo \(an + 1\) ; par suite \(b!\) est aussi inversible modulo \(an + 1\). La relation (1) se ramène alors à
Or, puisque \(an \equiv -1\), le membre de gauche vérifie
Si \(an > 1\) et \(b\) est pair, on obtient bien \((-1)^b b! \equiv b!\), comme voulu. Si au contraire \(b\) est impair et si l'on prend \(an + 1 > 2(b!)\), on n'a pas \((-1)^b b! \equiv b!\), donc \(b\) n'est pas \(a\)-bon. Cela démontre l'affirmation.
Conclusion. Supposons que \(b\) soit \(a\)-bon mais pas \(b + 2\). Alors \(b\) est pair et \(p \mid a\) pour tout premier \(p \leq b\), mais il existe un premier \(q \leq b + 2\) tel que \(q \nmid a\) : donc \(q = b + 1\) ou \(q = b + 2\). On ne peut pas avoir \(q = b + 2\), qui est pair lui aussi (et supérieur à \(2\)). Donc \(q = b + 1\) : autrement dit, \(b + 1\) est premier. \(\blacksquare\)
Solution 2¶
On ne démontre ici que la moitié de l'affirmation de la solution précédente : si \(b\) est \(a\)-bon, alors \(p \mid a\) pour tout premier \(p \leq b\). On utilise pour cela le théorème de Lucas.
Supposons qu'il existe \(p \leq b\) avec \(p \nmid a\). Écrivons \(b\) en base \(p\) ; comme \(p \leq b\), l'un des chiffres autres que le dernier est non nul, disons le chiffre de \(p^t\) avec \(t \geq 1\). Quand \(n\) parcourt les entiers, \(an + 1\) parcourt toutes les classes de résidus modulo \(p^{t+1}\) ; en particulier, on peut choisir \(n\) (avec \(an > b\)) tel que le chiffre des unités de \(an\) en base \(p\) soit \(p - 1\) (donc \(p \mid an + 1\)) et que le chiffre de \(p^t\) dans \(an\) soit \(0\). Alors \(p \mid an + 1\), mais \(p \mid \binom{an}{b}\) (par le théorème de Lucas), donc \(p \nmid \binom{an}{b} - 1\). Ainsi \(b\) n'est pas \(a\)-bon.
Montrons maintenant directement que si \(b\) est \(a\)-bon mais pas \(b + 2\), il existe un premier qui divise \(an + 1\) pour un certain \(n\) et qui divise aussi \((b+1)(b+2)\). En effet,
Il existe un choix de \(an + 1\) pour lequel \(\binom{an}{b}\) est congru à \(1\) modulo \(an + 1\) mais pas \(\binom{an}{b+2}\) ; ce rapport n'est donc pas congru à \(1\) modulo \(an + 1\). Si \(b + 1\) et \(b + 2\) étaient tous deux premiers avec \(an + 1\), ce rapport serait congru à \(1\) (car \(an - b \equiv -(b+1)\) et \(an - b - 1 \equiv -(b+2)\)). Ce n'est donc pas le cas. Comme tout premier \(p \leq b\) divise \(a\) (donc ne divise pas \(an + 1\)), on en déduit que \(b + 1\) ou \(b + 2\) est premier. (Le livret écrit « tout premier inférieur à \(b\) » ; c'est bien tout premier \(p \leq b\), comme établi ci-dessus.)
Enfin, \(b\) doit être pair : en imposant que \(an + 1\) soit premier (ce qui est possible par le théorème de Dirichlet), on a \(\binom{an}{b} \equiv (-1)^b\) modulo \(an + 1\), donc \((-1)^b = 1\). Ainsi \(b + 2\) ne peut pas être premier, et \(b + 1\) est premier. \(\blacksquare\)