Aller au contenu

Shortlist 2025, N4

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

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2025 (avec solutions), section N4 (livret PDF)

Énoncé

Let \(\mathbb{Z}_{>0}\) be the set of positive integers. Determine all functions \(f : \mathbb{Z}_{>0} \to \mathbb{Z}\) such that for every \(n \in \mathbb{Z}_{>0}\), and every positive divisor \(d\) of \(n\), there exists a positive divisor \(e\) of \(n\) such that \(n\) divides \(d + f(e)\).

Indices : les idées clés
  • Une bijection sur les diviseurs : pour chaque \(n\), la relation « \(n \mid d + f(e)\) » définit une bijection \(X_n\) de l'ensemble des diviseurs de \(n\) dans lui-même.
  • Équations fonctionnelles : injectivité : \(f\) est injective, ce qui exclut que deux entiers aient la même image.
  • Divisibilité : un entier divisible par une infinité de nombres premiers (ou par \(mp^k\) pour tout \(k\)) est nul.
  • Récurrence forte sur le nombre de facteurs premiers de \(n\) (solutions 1 et 2), ou sur \(n\) minimal (solution 3).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (trois solutions).

Réponse : la seule fonction est \(f(n) = -n\).

Solution 1

Vérification. Si \(f(n) = -n\), pour \(n\) et un diviseur \(d\) de \(n\), on prend \(e = d\) : alors \(d + f(e) = 0\) est divisible par \(n\).

Dans la suite, « diviseur » signifie diviseur positif. Pour \(f\) solution, notons \(S_n\) l'ensemble des couples \((d, e)\) de diviseurs de \(n\) tels que \(n \mid d + f(e)\).

Affirmation 1. Pour tout diviseur \(e\) de \(n\), il existe au plus un diviseur \(d\) de \(n\) tel que \((d, e) \in S_n\).

Preuve. Si \((d_1, e)\) et \((d_2, e)\) sont dans \(S_n\), alors \(n \mid d_1 + f(e)\) et \(n \mid d_2 + f(e)\) ; en soustrayant, \(n \mid d_1 - d_2\). Comme \(1 \leq d_1, d_2 \leq n\), on obtient \(d_1 = d_2\). \(\square\)

La condition de l'énoncé dit que pour tout diviseur \(d\) de \(n\), il existe un diviseur \(e\) de \(n\) avec \((d, e) \in S_n\). L'ensemble des diviseurs de \(n\) étant fini, ce fait et l'affirmation 1 montrent que \(S_n\) est le graphe d'une bijection de l'ensemble des diviseurs de \(n\) dans lui-même. Pour un diviseur \(e\) de \(n\), on note \(X_n(e)\) l'unique \(d\) tel que \((d, e) \in S_n\).

Affirmation 2. La fonction \(f\) est injective.

Preuve. Si \(f(a) = f(b)\), alors \(X_{ab}(a) = X_{ab}(b)\), ce qui contredit l'injectivité de \(X_{ab}\) si \(a \neq b\). \(\square\)

Nous montrons par récurrence forte sur le nombre de facteurs premiers de \(n\) (comptés avec multiplicité) que \(f(n) = -n\). Supposons le résultat établi pour tous les entiers ayant moins de \(k\) facteurs premiers, et soit \(m\) un entier qui en a \(k\) ; montrons que \(f(m) = -m\).

Prenons \(n = m\) dans la condition. L'hypothèse de récurrence donne \(f(e) + e = 0\) pour tout diviseur strict \(e\) de \(m\), donc \(X_m(e) = e\). Comme \(X_m\) est une bijection, \(X_m(m) = m\). Donc \(m \mid f(m)\).

Lemme. Si \(m\) a \(k\) facteurs premiers et \(f(m) \neq 0\), alors \(f(m) = -m\).

Preuve. Soit \(p\) un nombre premier premier avec \(f(m)\), et soit \(d = X_{mp}(m)\). Si \(p \mid d\), alors \(p \mid f(m)\) (car \(mp \mid d + f(m)\)), contradiction. Donc \(d\) est un diviseur de \(m\). Par l'hypothèse de récurrence, \(X_{mp}(e) = e\) pour tout diviseur strict \(e\) de \(m\). Comme \(X_{mp}\) est une bijection, cela impose \(X_{mp}(m) = m\). Donc \(p \mid mp \mid f(m) + m\). Ceci vaut pour une infinité de nombres premiers \(p\), donc \(f(m) = -m\). \(\square\)

Il reste à traiter le cas \(f(m) = 0\). Soit \(p\) un nombre premier ne divisant pas \(m\). Si \(d\) est un diviseur strict de \(mp\) différent de \(m\), alors d'après le lemme (ou l'hypothèse de récurrence), \(f(d) = -d\) ou \(f(d) = 0\) ; comme \(f\) est injective et \(f(m) = 0\), on a \(f(d) = -d\) pour tous ces diviseurs de \(mp\). Cela détermine complètement \(X_{mp}\) ; en particulier \(X_{mp}(mp) = m\). Donc \(mp \mid f(mp) + m\).

Comme \(f(mp) \neq 0\), on peut choisir un nombre premier \(q\) premier avec \(f(mp)\). Considérons \(X_{mpq}(mp)\). Comme \(q \nmid f(mp)\), \(X_{mpq}(mp)\) n'est pas divisible par \(q\) : c'est un diviseur de \(mp\). Le lemme s'applique à tous les diviseurs \(d \neq mp\) de \(mp\) : \(f(d) = -d\) ou \(f(d) = 0\). Comme \(f(m) = 0\) et \(f\) est injective, pour tout diviseur \(d \neq m, mp\) de \(mp\), on a \(f(d) = -d\) et \(X_{mpq}(d) = d\). Donc \(X_{mpq}(mp)\) vaut \(m\) ou \(mp\).

Comme \(mp \mid f(mp) + m\), on a \(mp \nmid f(mp) + mp\) ; a fortiori \(mpq \nmid f(mp) + mp\). Donc \(X_{mpq}(mp) = m\), et \(q \mid f(mp) + m\). Ceci vaut pour une infinité de nombres premiers \(q\), donc \(f(mp) = -m\). Mais cela est vrai pour une infinité de nombres premiers \(p\), ce qui contredit l'injectivité de \(f\).

Ceci achève l'hérédité : \(f(m) = -m\). Par récurrence, \(f(n) = -n\) pour tout \(n\). \(\blacksquare\)

Solution 2

On procède comme dans la solution 1 jusqu'au troisième paragraphe avant la fin (le traitement du cas \(f(m) = 0\)). On suppose donc, par l'absurde, que \(f(m) = 0\) et que \(f(d) = -d\) pour tout entier \(d\) ayant moins de facteurs premiers que \(m\). On a déjà établi que, si \(p\) est un nombre premier ne divisant pas \(m\), alors \(mp \mid f(mp) + m\).

Soit \(k\) un entier strictement positif ; on a \(mp^k \mid f(mp) + X_{mp^k}(mp)\). Comme \(p \mid f(mp) + m\), on a \(X_{mp^k}(mp) \equiv m \not\equiv 0 \pmod p\) : \(X_{mp^k}(mp)\) est un diviseur de \(mp^k\) non divisible par \(p\), donc un diviseur de \(m\). Mais \(X_{mp^k}(d) = d\) pour tout diviseur strict \(d\) de \(m\). Donc \(X_{mp^k}(mp) = m\) et \(mp^k \mid f(mp) + m\).

Ceci vaut pour tout \(k\), donc \(f(mp) = -m\). Et cela vaut pour une infinité de nombres premiers \(p\), ce qui contredit l'injectivité.

Ceci achève l'hérédité, et donc \(f(n) = -n\) pour tout \(n\). \(\blacksquare\)

Solution 3

On procède comme dans la solution 1 jusqu'à la fin de l'affirmation 2.

Lemme. Pour tout \(m\), on a soit \(f(m) = 0\), soit \(f(m) = -d\) pour un certain diviseur \(d\) de \(m\).

Preuve. Supposons par l'absurde que \(f(m)\) n'est d'aucune de ces formes. Soit \(p > m + |f(m)|\) un nombre premier, et soit \(d \mid pm\) tel que \(mp \mid d + f(m)\).

  • Si \(p \nmid d\), alors \(d \mid m\). Donc \(|d + f(m)| \leq m + |f(m)| < p\), et \(d + f(m) \neq 0\) par hypothèse. Donc \(d + f(m)\) ne peut pas être divisible par \(p\).
  • Si \(p \mid d\), alors \(p \mid f(m)\), ce qui est absurde (car \(0 < |f(m)| < p\), puisque \(f(m) \neq 0\)).

Dans les deux cas, on obtient une contradiction. \(\square\)

Montrons que \(f(n) = -n\) pour tout \(n\). Supposons par l'absurde que \(n\) est le plus petit entier tel que \(f(n) \neq -n\). Alors \(f(d) = -d\) pour tout diviseur strict \(d\) de \(n\). D'après le lemme et l'injectivité de \(f\), il vient \(f(n) = 0\).

Soit \(p\) un nombre premier tel que \(p \nmid n\). Comme \(f(n) = 0\), on a \(pn \mid f(n) + pn\). Soit \(m \mid pn\) tel que \(pn \mid n + f(m)\). Remarquons que \(n \neq m\) et que \(n \mid f(m)\). Si \(d\) est un diviseur strict de \(n\), alors \(n \nmid f(d) = -d\). Donc \(m \nmid n\), ce qui, avec \(m \mid pn\), donne \(p \mid m\).

D'après le lemme, \(n - pn \leq n + f(m) \leq n\). Le nombre \(n + f(m)\), multiple de \(pn\) dans cet intervalle, ne peut être que \(0\) : \(f(m) = -n\). Par injectivité, \(m\) ne dépend pas du nombre premier \(p\). Mais alors \(m\) est divisible par une infinité de nombres premiers, ce qui est absurde.

Donc \(f(n) = -n\) pour tout \(n\). \(\blacksquare\)