Aller au contenu

Shortlist 2013, N1

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

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

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 52 (page 52 du PDF)

Énoncé

Let \(\mathbb{Z}_{>0}\) be the set of positive integers. Find all functions \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) such that

\[m^2 + f(n) \mid m f(m) + n\]

for all positive integers \(m\) and \(n\).

Indices : les idées clés
  • Substitutions : \(m = n = 2\) donne \(f(2) = 2\), puis \(m = 2\) donne \(4 + f(n) \mid 4 + n\), donc \(f(n) \leq n\).
  • Divisibilité et taille : \(m = n\) donne \(n^2 + f(n) \leq n f(n) + n\), soit \((n - 1)(f(n) - n) \geq 0\), donc \(f(n) \geq n\).
  • Variante (solution 2) : avec un grand nombre premier \(p\) et \(n = p - m f(m)\), le diviseur \(m^2 + f(n)\) de \(p\) vaut \(p\).
Solutions

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

Réponse : \(f(n) = n\).

Solution 1

Avec \(m = n = 2\), on obtient \(4 + f(2) \mid 2f(2) + 2\). Comme \(2f(2) + 2 < 2(4 + f(2))\), on doit avoir \(2f(2) + 2 = 4 + f(2)\), donc \(f(2) = 2\). Avec \(m = 2\), on obtient alors \(4 + f(n) \mid 4 + n\), ce qui implique \(f(n) \leq n\) pour tout \(n\).

Avec \(m = n\), on obtient \(n^2 + f(n) \mid n f(n) + n\), donc \(n f(n) + n \geq n^2 + f(n)\), ce qui s'écrit \((n - 1)(f(n) - n) \geq 0\). Donc \(f(n) \geq n\) pour tout \(n \geq 2\). C'est aussi trivialement vrai pour \(n = 1\).

Il s'ensuit que \(f(n) = n\) pour tout \(n\). Cette fonction vérifie évidemment la propriété voulue. \(\blacksquare\)

Solution 2

Avec \(m = f(n)\), on obtient \(f(n)\big(f(n) + 1\big) \mid f(n) f(f(n)) + n\). Cela implique \(f(n) \mid n\) pour tout \(n\).

Soit maintenant \(m\) un entier strictement positif quelconque, et \(p > 2m^2\) un nombre premier. On a aussi \(p > m f(m)\). Avec \(n = p - m f(m)\), on obtient que \(m^2 + f(n)\) divise \(p\). Comme \(m^2 + f(n)\) ne peut pas valoir \(1\), il vaut \(p\). Donc \(p - m^2 = f(n) \mid n = p - m f(m)\). Mais \(p - m f(m) < p < 2(p - m^2)\), donc on doit avoir \(p - m f(m) = p - m^2\), c'est-à-dire \(f(m) = m\). \(\blacksquare\)

Solution 3

Avec \(m = 1\), on obtient \(1 + f(n) \leq f(1) + n\), donc \(f(n) \leq n + c\) pour la constante \(c = f(1) - 1\). Supposons \(f(n) \neq n\) pour un \(n\) fixé. Pour \(m\) assez grand (par exemple \(m \geq \max(n, c + 1)\)), on a

\[m f(m) + n \leq m(m + c) + n \leq 2m^2 < 2\big(m^2 + f(n)\big),\]

donc on doit avoir \(m f(m) + n = m^2 + f(n)\). Cela implique

\[0 \neq f(n) - n = m\big(f(m) - m\big),\]

ce qui est impossible pour \(m > \lvert f(n) - n \rvert\). Donc \(f\) est l'identité. \(\blacksquare\)