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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

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

\[f(m) + f(n) - mn \mid mf(m) + nf(n). \tag{1}\]

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)

\[f(p) - p + 1 \mid pf(p) + 1 - p\big(f(p) - p + 1\big) = p^2 - p + 1.\]

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

\[f(p) \leq \frac13\left(p^2 + 2p - 2\right). \tag{2}\]

Avec \(m = n = p\) dans (1) : \(2f(p) - p^2 \mid 2pf(p)\), donc

\[2f(p) - p^2 \mid 2pf(p) - p\big(2f(p) - p^2\big) = p^3.\]

Or, d'après (2) et \(f(p) \geq 1\),

\[-p^2 < 2f(p) - p^2 \leq \frac23\left(p^2 + 2p - 2\right) - p^2 < -p,\]

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) :

\[f(p) + f(n) - pn \mid pf(p) + nf(n) - n\big(f(p) + f(n) - pn\big) = pf(p) - nf(p) + pn^2.\]

Comme \(f(p) = p^2\), ceci donne

\[p^2 - pn + f(n) \mid p\left(p^2 - pn + n^2\right).\]

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

\[p^2 - pn + f(n) \mid \left(p^2 - pn + n^2\right) - \left(p^2 - pn + f(n)\right) = n^2 - f(n).\]

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

\[mf(m) + nf(n) = m^3 + n^3 = (m + n)\left(m^2 - mn + n^2\right),\]

qui est bien divisible par \(m^2 - mn + n^2\). La seule solution est donc \(f(n) = n^2\). \(\blacksquare\)