Aller au contenu

Shortlist 2021, N5

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

Concepts : AM-GM et moyennes · Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 74 (page 74 du PDF)

Énoncé

Prove that there are only finitely many quadruples \((a, b, c, n)\) of positive integers such that

\[n! = a^{n-1} + b^{n-1} + c^{n-1}.\]
Indices : les idées clés
  • AM-GM : \(n! < \left(\frac{n-1}{2}\right)^{n-1}\) pour \(n > 100\), d'où \(a, b, c < \frac{n-1}{2}\).
  • Valuations et LTE : la formule de Legendre donne \(\nu_p(n!) < \frac{n}{p-1}\), et le lemme LTE calcule \(\nu_p(a^{n-1} + b^{n-1}) = \nu_p(a+b) + \nu_p(n-1)\).
  • Congruences : carrés modulo \(4\) pour \(n\) impair, parité et argument modulo \(5\) quand \(a+b\), \(b+c\), \(c+a\) sont des puissances de \(2\).
  • Compter les multiples de \(p\) : l'égalité des valuations ne laisse que deux multiples de \(p\) dans \(\{1, \ldots, n\}\), ce qui force \(n - 1 = 2p\), absurde.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (une solution et trois remarques).

Solution

Pour \(n\) fixé, il y a clairement un nombre fini de solutions ; nous allons montrer qu'il n'y a aucune solution avec \(n > 100\). Supposons donc \(n > 100\). Par l'inégalité AM-GM,

\[\begin{aligned} n! &= 2n(n-1)(n-2)(n-3) \cdot \big(3 \cdot 4 \cdots (n-4)\big) \\ &\leq 2(n-1)^4 \left(\frac{3 + \cdots + (n-4)}{n-6}\right)^{n-6} = 2(n-1)^4 \left(\frac{n-1}{2}\right)^{n-6} < \left(\frac{n-1}{2}\right)^{n-1}, \end{aligned}\]

donc \(a, b, c < \frac{n-1}{2}\).

Pour tout nombre premier \(p\) et tout entier \(m \neq 0\), notons \(\nu_p(m)\) la valuation \(p\)-adique de \(m\), c'est-à-dire le plus grand entier \(k \geq 0\) tel que \(p^k\) divise \(m\). La formule de Legendre affirme

\[\nu_p(n!) = \sum_{s=1}^{\infty} \left\lfloor \frac{n}{p^s} \right\rfloor,\]

et un corollaire bien connu est

\[\nu_p(n!) < \sum_{s=1}^{\infty} \frac{n}{p^s} = \frac{n}{p-1}. \qquad (\heartsuit)\]

Cas \(n\) impair. Alors \(a^{n-1}\), \(b^{n-1}\), \(c^{n-1}\) sont des carrés, et leur somme \(n!\) est divisible par \(4\) ; en considérant les carrés modulo \(4\), on obtient que \(a\), \(b\) et \(c\) sont pairs. Donc \(2^{n-1} \mid n!\), ce qui est impossible pour \(n\) impair puisque \(\nu_2(n!) = \nu_2((n-1)!) < n - 1\) par \((\heartsuit)\).

Cas \(n\) pair. Si les trois nombres \(a+b\), \(b+c\), \(c+a\) sont des puissances de \(2\), alors \(a, b, c\) ont la même parité. S'ils sont tous impairs, \(n! = a^{n-1} + b^{n-1} + c^{n-1}\) est impair, absurde. S'ils sont tous divisibles par \(4\), cela contredit \(\nu_2(n!) \leq n - 1\). Si, par exemple, \(a\) n'est pas divisible par \(4\), alors \(2a = (a+b) + (a+c) - (b+c)\) n'est pas divisible par \(8\), et comme \(a+b\), \(b+c\), \(c+a\) sont des puissances de \(2\), l'une de ces sommes vaut \(4\) : deux des nombres \(a, b, c\) valent \(2\). Disons \(a = b = 2\) ; alors \(c = 2^r - 2\) et, comme \(c \mid n!\), on a \(c \mid a^{n-1} + b^{n-1} = 2^n\), ce qui impose \(r = 2\), donc \(c = 2\) ; c'est impossible car \(n! \equiv 0 \not\equiv 3 \cdot 2^{n-1} \pmod 5\).

On suppose donc que la somme de deux des nombres \(a, b, c\), disons \(a + b\), n'est pas une puissance de \(2\) ; elle est donc divisible par un nombre premier impair \(p\). Alors \(p \leq a + b < n\), et donc \(c^{n-1} = n! - (a^{n-1} + b^{n-1})\) est divisible par \(p\) (car \(n - 1\) est impair, donc \(a + b \mid a^{n-1} + b^{n-1}\)). Si \(p\) divisait \(a\) et \(b\), on aurait \(p^{n-1} \mid n!\), ce qui contredit \((\heartsuit)\). Ensuite, comme \(\nu_p(c^{n-1}) \geq n - 1 > \nu_p(n!)\) par \((\heartsuit)\), et par le lemme LTE (« Lifting The Exponent ») :

\[\nu_p(1) + \nu_p(2) + \cdots + \nu_p(n) = \nu_p(n!) = \nu_p\big(n! - c^{n-1}\big) = \nu_p\big(a^{n-1} + b^{n-1}\big) = \nu_p(a+b) + \nu_p(n-1). \qquad (\diamondsuit)\]

Au vu de \((\diamondsuit)\), aucun des nombres \(1, 2, \ldots, n\) n'est divisible par \(p\), sauf \(a + b\) et \(n - 1\) (et \(n - 1 > a + b\)). D'autre part, \(p \mid c\) implique \(p \leq c < n/2\), donc il y a au moins deux multiples de \(p\) parmi \(1, \ldots, n\), à savoir \(p\) et \(2p\). Ainsi les multiples de \(p\) dans \(\{1, \ldots, n\}\) sont exactement \(a + b = p\) et \(n - 1 = 2p\). C'est encore une contradiction, car \(n - 1\) est impair. Cette dernière contradiction montre que l'équation n'a pas de solution pour \(n > 100\), d'où la finitude. \(\blacksquare\)

Remarques

Remarque 1. La version originale du problème demandait de trouver toutes les solutions de l'équation. La solution de cette version n'est pas très différente, mais plus technique.

Remarque 2 (toutes les solutions). Pour trouver toutes les solutions, on peut remplacer la borne \(a, b, c < (n-1)/2\) (pour tout \(n\)) par la borne plus faible \(a, b, c \leq n/2\), seulement pour \(n\) pair, qui découle de AM-GM appliquée à \((2, 3, \ldots, n)\). On peut alors utiliser le même argument pour \(n\) impair (il marche pour \(n \geq 5\) et ne demande aucune borne sur \(a, b, c\)), et pour \(n\) pair la même solution marche pour \(n \geq 6\), sauf si \(a + b = n - 1\) et \(2\nu_p(n-1) = \nu_p(n!)\). Ce n'est possible que pour \(p = 3\) et \(n = 10\) ; dans ce cas, on considère l'équation modulo \(7\) pour obtenir \(7 \mid abc\), ce qui contredit \(7^9 > 10!\). En examinant \(n \leq 4\), on trouve quatre solutions :

\[(a, b, c, n) = (1, 1, 2, 3),\ (1, 2, 1, 3),\ (2, 1, 1, 3),\ (2, 2, 2, 4).\]

Remarque 3. Pour \(n\) assez grand, l'inégalité \(a, b, c < (n-1)/2\) découle aussi de la formule de Stirling.