Aller au contenu

Shortlist 2009, N3

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

Concepts : Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide

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

Énoncé

Soit \(f\) une fonction non constante de l'ensemble des entiers strictement positifs dans lui-même, telle que \(a - b\) divise \(f(a) - f(b)\) pour tous entiers \(a, b\) strictement positifs distincts. Montrer qu'il existe une infinité de nombres premiers \(p\) tels que \(p\) divise \(f(c)\) pour un certain entier \(c\) strictement positif.

Énoncé original (anglais)

Let \(f\) be a non-constant function from the set of positive integers into the set of positive integers, such that \(a - b\) divides \(f(a) - f(b)\) for all distinct positive integers \(a, b\). Prove that there exist infinitely many primes \(p\) such that \(p\) divides \(f(c)\) for some positive integer \(c\).

Indices : les idées clés
  • Par l'absurde : seuls les premiers \(p_1, \ldots, p_m\) divisent les valeurs de \(f\) ; on prend \(a = (p_1 \cdots p_m)^\alpha\) avec \(\alpha\) grand.
  • Valuations : si \(f(a + 1) \neq f(1)\), une valuation \(v_{p_i}\) diffère, et \(v_{p_i}(f(a + 1) - f(1)) \leq v_{p_i}(f(1)) < v_{p_i}(a)\), contredisant \(a \mid f(a + 1) - f(1)\).
  • Divisibilité par de grands nombres : \(f(a + 1) = f(1)\) pour une infinité de \(a\), et \((a + 1 - b) \mid f(1) - f(b)\) force \(f(b) = f(1)\).
Solutions

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

Solution 1

Notons \(v_p(a)\) l'exposant du nombre premier \(p\) dans la décomposition en facteurs premiers de \(a\). Supposons qu'il n'y ait qu'un nombre fini de nombres premiers \(p_1, p_2, \ldots, p_m\) divisant une valeur de \(f\).

Il existe une infinité d'entiers \(a > 0\) tels que \(v_{p_i}(a) > v_{p_i}(f(1))\) pour tout \(i = 1, 2, \ldots, m\), par exemple \(a = (p_1p_2 \cdots p_m)^\alpha\) avec \(\alpha\) assez grand. Prenons un tel \(a\). La condition du problème donne alors \(a \mid (f(a + 1) - f(1))\). Supposons \(f(a + 1) \neq f(1)\). On doit alors avoir \(v_{p_i}(f(a + 1)) \neq v_{p_i}(f(1))\) pour au moins un \(i\). Cela donne \(v_{p_i}(f(a + 1) - f(1)) = \min\{v_{p_i}(f(a + 1)), v_{p_i}(f(1))\} \leq v_{p_i}(f(1)) < v_{p_i}(a)\) (le livret écrit \(v_{p_1}(f(1))\) ; il s'agit de \(v_{p_i}\)). Mais cela contredit le fait que \(a \mid (f(a + 1) - f(1))\).

On doit donc avoir \(f(a + 1) = f(1)\) pour tous ces \(a\).

Maintenant, pour tout entier \(b > 0\) et tous ces \(a\), on a \((a + 1 - b) \mid (f(a + 1) - f(b))\), c'est-à-dire \((a + 1 - b) \mid (f(1) - f(b))\). Comme c'est vrai pour une infinité d'entiers \(a > 0\), on doit avoir \(f(b) = f(1)\). Donc \(f\) est constante, ce qui est une contradiction. Notre hypothèse initiale était donc fausse, et il existe bien une infinité de nombres premiers \(p\) divisant \(f(c)\) pour un certain entier \(c > 0\). \(\blacksquare\)

Solution 2

Supposons qu'il n'y ait qu'un nombre fini de nombres premiers \(p_1, p_2, \ldots, p_m\) divisant une valeur de \(f\). Comme \(f\) n'est pas identiquement égale à \(1\), on a \(m \geq 1\). Il existe alors des entiers positifs ou nuls \(\alpha_1, \ldots, \alpha_m\) tels que

\[f(1) = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_m^{\alpha_m}.\]

On peut choisir un entier \(r > 0\) tel que \(f(r) \neq f(1)\). Posons

\[M = 1 + p_1^{\alpha_1+1}p_2^{\alpha_2+1} \cdots p_m^{\alpha_m+1} \cdot (f(r) + r).\]

Alors, pour tout \(i \in \{1, \ldots, m\}\), \(p_i^{\alpha_i+1}\) divise \(M - 1\), donc, d'après la condition du problème, aussi \(f(M) - f(1)\). Cela implique que \(f(M)\) est divisible par \(p_i^{\alpha_i}\) mais pas par \(p_i^{\alpha_i+1}\) pour tout \(i\), et donc \(f(M) = f(1)\). Ainsi

\[\begin{aligned} M - r &> p_1^{\alpha_1+1}p_2^{\alpha_2+1} \cdots p_m^{\alpha_m+1} \cdot (f(r) + r) - r \\ &\geq p_1^{\alpha_1+1}p_2^{\alpha_2+1} \cdots p_m^{\alpha_m+1} + (f(r) + r) - r \\ &> p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_m^{\alpha_m} + f(r) \geq \lvert f(M) - f(r) \rvert. \end{aligned}\]

Mais comme \(M - r\) divise \(f(M) - f(r)\), cela n'est possible que si \(f(r) = f(M) = f(1)\), ce qui contredit le choix de \(r\). \(\blacksquare\)

Remarque

Dans le cas où \(f\) est un polynôme à coefficients entiers, le résultat est bien connu ; voir par exemple W. Schwarz, Einführung in die Methoden der Primzahltheorie, 1969.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2015 N3 ★★☆☆☆ : Si tous les \((m + k)/(n + k)\) sont entiers, leur produit moins \(1\) a un facteur premier impair.
  • 2025 N5 ★★★☆☆ : Chaque terme d'un triplet augmente du PGCD des deux autres, \(2025\) fois de suite : quelle valeur minimale pour \(a_{2025}\) ?
  • 2024 N4 ★★★☆☆ · OIM P2 : Pour quels \(a, b\) le PGCD de \(a^n + b\) et \(b^n + a\) finit-il par être constant ?
  • 2018 N7 ★★★★★ : Des fractions à numérateurs et dénominateurs distincts au plus \(5n\) en progression arithmétique sont toutes égales.