Shortlist 2016, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 82 (page 85 du PDF)
Énoncé¶
Notons \(\mathbb{N}\) l'ensemble des entiers strictement positifs. Trouver toutes les fonctions \(f : \mathbb{N} \to \mathbb{N}\) telles que, pour tous entiers \(m\) et \(n\) strictement positifs, l'entier \(f(m) + f(n) - mn\) soit non nul et divise \(mf(m) + nf(n)\).
Énoncé original (anglais)
Denote by \(\mathbb{N}\) the set of all positive integers. Find all functions \(f : \mathbb{N} \to \mathbb{N}\) such that for all positive integers \(m\) and \(n\), the integer \(f(m) + f(n) - mn\) is nonzero and divides \(mf(m) + nf(n)\).
Indices : les idées clés
- Substitutions : on spécialise \(m = n = 1\), puis \((m, n) = (p, 1)\) et \((p, p)\) pour un nombre premier \(p\), puis \(m = p\) avec \(n\) quelconque.
- Divisibilité et PGCD : si \(d \mid A\) et \(d \mid B\), alors \(d\) divise toute combinaison \(A - \lambda B\) ; on élimine ainsi \(f(p)\) du dividende.
- Utiliser un grand nombre premier : pour \(p\) premier assez grand, \(\operatorname{pgcd}(p, p^2 - pn + f(n)) = 1\), et un diviseur arbitrairement grand d'un entier fixé force cet entier à être nul.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2016 (une solution).
Réponse. \(f(n) = n^2\) pour tout \(n \in \mathbb{N}\).
Solution¶
L'hypothèse s'écrit
Calcul de \(f(1)\). Avec \(m = n = 1\) dans (1) : \(2f(1) - 1 \mid 2f(1)\). Donc \(2f(1) - 1 \mid 2f(1) - (2f(1) - 1) = 1\), d'où \(f(1) = 1\).
Valeurs aux grands nombres premiers. Soit \(p \geq 7\) un nombre premier. Avec \(m = p\) et \(n = 1\) dans (1) : \(f(p) - p + 1 \mid pf(p) + 1\), donc (divisibilité d'une combinaison)
Si \(f(p) - p + 1 = p^2 - p + 1\), alors \(f(p) = p^2\). Sinon, comme \(p^2 - p + 1\) est un entier positif impair, son diviseur \(f(p) - p + 1\) (distinct de lui) vérifie \(p^2 - p + 1 \geq 3\big(f(p) - p + 1\big)\), c'est-à-dire
Avec \(m = n = p\) dans (1) : \(2f(p) - p^2 \mid 2pf(p)\), donc
Or, d'après (2) et \(f(p) \geq 1\),
car \(p \geq 7\). Ceci contredit le fait que \(2f(p) - p^2\) divise \(p^3\) (ses seuls diviseurs sont \(\pm 1, \pm p, \pm p^2, \pm p^3\)). On a donc montré que \(f(p) = p^2\) pour tout nombre premier \(p \geq 7\).
Cas général. Fixons \(n \in \mathbb{N}\) et choisissons un nombre premier \(p\) assez grand. Avec \(m = p\) dans (1) :
Comme \(f(p) = p^2\), ceci donne
Puisque \(p\) est assez grand et \(n\) fixé, \(p\) ne divise pas \(f(n)\), donc \(\operatorname{pgcd}\big(p,\ p^2 - pn + f(n)\big) = 1\). Il s'ensuit que \(p^2 - pn + f(n) \mid p^2 - pn + n^2\), puis
L'entier \(n^2 - f(n)\) est fixé, tandis que \(p^2 - pn + f(n)\) peut être rendu arbitrairement grand. On a donc nécessairement \(n^2 - f(n) = 0\), soit \(f(n) = n^2\) pour tout \(n\).
Vérification. Si \(f(n) = n^2\) pour tout \(n\), alors \(f(m) + f(n) - mn = m^2 - mn + n^2 > 0\) et
qui est bien divisible par \(m^2 - mn + n^2\). La seule solution est donc \(f(n) = n^2\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2020 A6 ★★★★☆ : Trouver les fonctions de \(\mathbb{Z}\) telles que \(f^{a^2 + b^2}(a + b) = a f(a) + b f(b)\).
- 2008 A6 ★★★★☆ : Une fonction à valeurs entières vérifiant \(f(x + 1/f(y)) = f(y + 1/f(x))\) ne prend pas toutes les valeurs.
- 2024 N7 ★★★★★ : Une équation fonctionnelle vraie exactement pour les couples premiers entre eux : quelles valeurs peut prendre \(f(n)\) ?
- 2023 N8 ★★★★★ : Trouver les fonctions des entiers positifs telles que \(f^{b f(a)}(a + 1) = (a + 1) f(b)\).