Aller au contenu

Shortlist 2010, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : U.S.A.

Concepts : Valuations p-adiques et lemme LTE · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Équations fonctionnelles : substitutions, injectivité, surjectivité

Solution officielle : Shortlist officielle 2010 (avec solutions), p. 71 (page 72 du PDF)

Problème 3 de l'OIM 2010

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2010, où il était le problème 3 (jour 1).

Énoncé

Let \(\mathbb{N}\) be the set of all positive integers. Find all functions \(f : \mathbb{N} \to \mathbb{N}\) such that the number \(\big(f(m) + n\big)\big(m + f(n)\big)\) is a square for all \(m, n \in \mathbb{N}\).

Indices : les idées clés
  • Lemme : si un premier \(p\) divise \(f(k) - f(\ell)\), alors \(p \mid k - \ell\).
  • Valuations : on choisit \(n\) pour que \(n + f(k)\) et \(n + f(\ell)\) soient divisibles par \(p\) (ou \(p^3\)) mais pas par \(p^2\) (ou \(p^4\)) ; comme les produits sont des carrés, \(p\) divise \(f(n) + k\) et \(f(n) + \ell\).
  • Conséquences : \(f\) est injective et \(\lvert f(k + 1) - f(k) \rvert = 1\), d'où \(f(n) = n + c\) (substitutions successives).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2010 (une solution).

Réponse : toutes les fonctions de la forme \(f(n) = n + c\), où \(c \in \mathbb{N} \cup \{0\}\).

Solution

D'abord, toutes les fonctions de la forme \(f(n) = n + c\), avec \(c\) entier positif ou nul constant, vérifient évidemment les conditions du problème, puisque \(\big(f(m) + n\big)\big(f(n) + m\big) = (n + m + c)^2\) est un carré.

Il reste à prouver qu'il n'y a pas d'autres fonctions. Commençons par le résultat suivant.

Lemme. Supposons que \(p \mid f(k) - f(\ell)\) pour un nombre premier \(p\) et des entiers \(k, \ell > 0\). Alors \(p \mid k - \ell\).

Preuve. Supposons d'abord que \(p^2 \mid f(k) - f(\ell)\), de sorte que \(f(\ell) = f(k) + p^2a\) pour un certain entier \(a\). Prenons un entier \(D > \max\{f(k), f(\ell)\}\) non divisible par \(p\), et posons \(n = pD - f(k)\). Alors les entiers strictement positifs \(n + f(k) = pD\) et \(n + f(\ell) = pD + \big(f(\ell) - f(k)\big) = p(D + pa)\) sont tous deux divisibles par \(p\) mais pas par \(p^2\). D'après les conditions du problème, les nombres \(\big(f(k) + n\big)\big(f(n) + k\big)\) et \(\big(f(\ell) + n\big)\big(f(n) + \ell\big)\) sont des carrés divisibles par \(p\) (donc par \(p^2\)) ; cela signifie que les facteurs \(f(n) + k\) et \(f(n) + \ell\) sont aussi divisibles par \(p\), donc \(p \mid \big(f(n) + k\big) - \big(f(n) + \ell\big) = k - \ell\) également.

D'autre part, si \(f(k) - f(\ell)\) est divisible par \(p\) mais pas par \(p^2\), choisissons le même nombre \(D\) et posons \(n = p^3D - f(k)\). Alors les entiers strictement positifs \(f(k) + n = p^3D\) et \(f(\ell) + n = p^3D + \big(f(\ell) - f(k)\big)\) sont respectivement divisibles par \(p^3\) (mais pas par \(p^4\)) et par \(p\) (mais pas par \(p^2\)). Par un raisonnement analogue, les nombres \(f(n) + k\) et \(f(n) + \ell\) sont divisibles par \(p\), donc \(p \mid \big(f(n) + k\big) - \big(f(n) + \ell\big) = k - \ell\). \(\square\)

Revenons au problème. Supposons d'abord que \(f(k) = f(\ell)\) pour certains \(k, \ell \in \mathbb{N}\). D'après le lemme, \(k - \ell\) est divisible par tout nombre premier, donc \(k - \ell = 0\), soit \(k = \ell\). La fonction \(f\) est donc injective.

Considérons ensuite les nombres \(f(k)\) et \(f(k + 1)\). Comme le nombre \((k + 1) - k = 1\) n'a aucun diviseur premier, il en est de même de \(f(k + 1) - f(k)\) d'après le lemme ; donc \(\lvert f(k + 1) - f(k) \rvert = 1\).

Posons maintenant \(f(2) - f(1) = q\), avec \(\lvert q \rvert = 1\). Montrons par récurrence que \(f(n) = f(1) + q(n - 1)\). L'initialisation pour \(n = 1, 2\) vient de la définition de \(q\). Pour l'hérédité, si \(n > 1\), on a \(f(n + 1) = f(n) \pm q = f(1) + q(n - 1) \pm q\). Comme \(f(n + 1) \neq f(n - 1) = f(1) + q(n - 2)\) (injectivité), on obtient \(f(n + 1) = f(1) + qn\), comme voulu.

Enfin, on a \(f(n) = f(1) + q(n - 1)\). Alors \(q\) ne peut pas valoir \(-1\), sinon on aurait \(f(n) \leq 0\) pour \(n \geq f(1) + 1\), ce qui est impossible. Donc \(q = 1\) et \(f(n) = \big(f(1) - 1\big) + n\) pour tout \(n \in \mathbb{N}\), avec \(f(1) - 1 \geq 0\), comme voulu. \(\blacksquare\)