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é¶

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.