Aller au contenu

Shortlist 2022, N4

Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Belgium

Concepts : Équations diophantiennes : factorisation et encadrement · Valuations p-adiques et lemme LTE · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 64 (page 66 du PDF)

Problème 5 de l'OIM 2022

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2022, où il était le problème 5 (jour 2).

Énoncé

Find all triples of positive integers \((a, b, p)\) with \(p\) prime and

\[a^p = b! + p.\]
Indices : les idées clés
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (quatre solutions et une remarque).

Réponse : \((a, b, p) = (2, 2, 2)\) et \((3, 4, 3)\).

Solution 1

Clairement \(a > 1\). On distingue trois cas.

Cas 1 : \(a < p\). Si \(a \leq b\), alors \(a \mid a^p - b! = p\), ce qui est impossible (\(1 < a < p\)). Si \(a > b\), c'est aussi impossible, car alors \(b! \leq a! < a^p - p\), la dernière inégalité étant vraie pour tout \(p > a > 1\).

Cas 2 : \(a > p\). Alors \(b! = a^p - p > p^p - p \geq p!\), donc \(b > p\), et \(a^p = b! + p\) est divisible par \(p\). Ainsi \(p \mid a\), et \(b! = a^p - p\) n'est pas divisible par \(p^2\) (car \(p^2 \mid a^p\) et \(p^2 \nmid p\)). Cela impose \(b < 2p\). Si \(a < p^2\), alors \(a/p < p \leq b\) divise à la fois \(a^p\) et \(b!\), donc aussi \(p = a^p - b!\) : impossible puisque \(1 < a/p < p\). Enfin, le cas \(a \geq p^2\) est impossible lui aussi, car alors

\[a^p \geq (p^2)^p > (2p-1)! + p \geq b! + p\]

(voir la remarque pour l'inégalité du milieu).

Cas 3 : \(a = p\). Alors \(b! = p^p - p\). On vérifie que \(p = 2\) et \(p = 3\) donnent les solutions annoncées (\(2! = 2^2 - 2\) et \(4! = 24 = 3^3 - 3\)), et que \(p = 5\) n'en donne pas (\(5^5 - 5 = 3120\) n'est pas une factorielle). Supposons désormais \(p \geq 7\). On a \(b! = p^p - p > p!\), donc \(b \geq p + 1\), ce qui implique, avec le lemme LTE au milieu,

\[v_2\big((p+1)!\big) \leq v_2(b!) = v_2(p^{p-1} - 1) \overset{\text{LTE}}{=} 2v_2(p-1) + v_2(p+1) - 1 = v_2\left(\frac{p-1}{2} \cdot (p-1) \cdot (p+1)\right).\]

Dans le membre de droite, \(\frac{p-1}{2}\), \(p - 1\) et \(p + 1\) sont trois facteurs distincts de \((p+1)!\). Or, comme \(p + 1 \geq 8\), il y a au moins \(4\) nombres pairs parmi \(1, 2, \ldots, p+1\) : l'un d'eux n'est pas parmi ces trois facteurs, donc \(v_2\big((p+1)!\big)\) est strictement plus grand que le membre de droite. Ce cas est impossible. \(\blacksquare\)

Solution 2

Les cas \(a \neq p\) se traitent comme dans la solution 1, ainsi que \(p = 2, 3\). Pour \(p \geq 5\), on a \(b! = p(p^{p-1} - 1)\). D'après le théorème de Zsigmondy, il existe un nombre premier \(q\) qui divise \(p^{p-1} - 1\) mais ne divise \(p^k - 1\) pour aucun \(k < p - 1\). Il s'ensuit que l'ordre de \(p\) modulo \(q\) vaut \(\mathrm{ord}_q(p) = p - 1\), et donc (petit théorème de Fermat) \(p - 1 \mid q - 1\), c'est-à-dire \(q \equiv 1 \pmod{p-1}\). Notons que \(q \neq p\). On a donc \(q \geq 2p - 1\), et comme \(q \mid b!\), \(b \geq 2p - 1\), d'où

\[b! \geq (2p-1)! = [1 \cdot (2p-1)] \cdot [2 \cdot (2p-2)] \cdots [(p-1)(p+1)] \cdot p > (2p-1)^{p-1} p > p^p > p^p - p,\]

une contradiction. \(\blacksquare\)

Solution 3

Les cas \(a \neq p\) se traitent comme dans la solution 1, ainsi que \(p = 2, 3\). On a aussi \(b > p\), car \(p^p > p! + p\) pour \(p > 2\). Les cas \(p = 5, 7, 11\) se vérifient à la main ; supposons donc \(p \geq 13\).

\(p + 1\) est une puissance de \(2\). Soit \(q\) un premier impair divisant \(p + 1\). Par le lemme LTE,

\[v_q(p^p - p) = v_q\left((p^2)^{\frac{p-1}{2}} - 1\right) = v_q(p^2 - 1) + v_q\left(\frac{p-1}{2}\right) = v_q(p+1).\]

Mais \(b \geq p + 1\), donc \(v_q(b!) > v_q(p+1)\) (car \(q < p + 1\), donc \(q\) et \(p + 1\) sont deux facteurs distincts de \(b!\)) : contradiction. Ainsi \(p + 1\) n'a pas de diviseur premier impair, c'est-à-dire \(p + 1 = 2^k\) pour un certain \(k\).

\(p - 1\) est le double d'un premier. Soit maintenant \(q\) un premier impair divisant \(p - 1\). Par LTE,

\[v_q(p^p - p) = 2v_q(p-1).\]

Posons \(d = v_q(p - 1)\). Alors \(p \geq 1 + q^d\), donc

\[v_q(b!) \geq v_q(p!) \geq v_q(q^d!) > q^{d-1} \geq 2d\]

dès que \(d \geq 2\) et \(q > 3\), ou \(d \geq 3\). Si \(q = 3\), \(d = 2\) et \(p \geq 13\), alors \(v_q(b!) \geq v_q(p!) \geq v_3(13!) = 5 > 2d\). Dans tous les cas, \(d \leq 1\).

Si \(p > 2q + 1\) (donc \(p > 3q\), puisque \(q \mid p - 1\) et \(p - 1\) est pair), alors

\[v_q(b!) \geq v_q\big((3q)!\big) \geq 3 > 2 \geq 2d,\]

ce qui est impossible ; on doit donc avoir \(q \geq \frac{p}{2}\), autrement dit \(p - 1 = 2q\). Cela implique que \(p = 2^k - 1\) et \(q = 2^{k-1} - 1\) sont tous deux premiers ; mais deux nombres de Mersenne consécutifs ne peuvent pas être tous deux premiers (pour que \(2^m - 1\) soit premier, il faut que \(m\) soit premier, et \(k - 1\), \(k\) ne sont tous deux premiers que pour \(k = 3\), soit \(p = 7 < 13\)). Contradiction. \(\blacksquare\)

Solution 4

Soit \(a = p\), \(b > p\) et \(p \geq 5\) (les autres cas se traitent comme dans la solution 3). Modulo \((p+1)^2\), par la formule du binôme :

\[p^p - p = (p + 1 - 1)^p - p \equiv \binom{p}{1}(p+1)(-1)^{p-1} + (-1)^p - p = p(p+1) - 1 - p = p^2 - 1 \not\equiv 0 \pmod{(p+1)^2}.\]

Comme \(p \geq 5\), les nombres \(2\) et \(\frac{p+1}{2}\) sont distincts et inférieurs ou égaux à \(p\) ; donc \(p + 1 \mid p!\), et ainsi \((p+1)^2 \mid (p+1)!\).

Mais \(b \geq p + 1\), donc \(b! \equiv 0 \not\equiv p^p - p \pmod{(p+1)^2}\) : contradiction. \(\blacksquare\)

Remarques

Remarque 1 (l'inégalité \(p^{2p} > (2p-1)! + p\) du cas 2). On peut l'obtenir en écrivant

\[(2p-1)! = [1 \cdot (2p-1)] \cdot [2 \cdot (2p-2)] \cdots [(p-1)(p+1)] \cdot p < \left(\left(\frac{2p}{2}\right)^2\right)^{p-1} \cdot p = p^{2p-1},\]

où l'inégalité vient de AM-GM appliquée à chaque crochet : \(k(2p - k) \leq p^2\).