Shortlist 2019, N4¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Croatia
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Principe des tiroirs
Solution officielle : Shortlist officielle 2019 (avec solutions), section N4 (livret PDF)
Énoncé¶
Let \(\mathbb{Z}_{>0}\) be the set of positive integers. A positive integer constant \(C\) is given. Find all functions \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) such that, for all positive integers \(a\) and \(b\) satisfying \(a + b > C\),
Indices : les idées clés
- Substitutions bien choisies : \(a = 1\) et \(b = 1\) donnent des encadrements de \(f\) ; \(a = nb - f(b)\) donne \(b \mid f(b)^2\) (solution 1).
- Divisibilité et PGCD : un entier fixé divisible par des nombres arbitrairement grands est nul ; \(\operatorname{pgcd}(a + kp, p) = 1\) pour \(p\) premier grand (solution 1).
- Principe des tiroirs (version infinie, solutions 1 et 2) : un quotient borné prend une même valeur \(k\) une infinité de fois.
- Combinaison linéaire puis comparaison de croissance (solution 3) : on élimine le terme en \(c\,f(c)\) et on compare une quantité en \(O(c)\) à un diviseur en \(\Omega(c^2)\).
- Interprétation géométrique (solution 4) : les points \((b, f(b))\) sont sur un nombre fini de droites passant par un point \(A'\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (quatre solutions et deux remarques).
Réponse : les fonctions \(f(a) = ka\), pour une constante \(k \in \mathbb{Z}_{>0}\) (quelle que soit la valeur de \(C\)).
Remarques communes. Notons \((\ast)\) la divisibilité de l'énoncé. On vérifie facilement que les fonctions \(f(a) = ka\) satisfont \((\ast)\) : \(a + kb \mid a^2 + kab = a(a + kb)\). Les preuves ci-dessous ne traitent donc que la réciproque : \((\ast)\) entraîne \(f(a) = ka\).
Toutes utilisent des encadrements simples de \(f\). En prenant \(a = 1\) dans \((\ast)\), on obtient la majoration
pour tout \(b\) assez grand. La minoration est à peine plus difficile : en prenant \(b = 1\),
pour tout \(a\) assez grand, d'où
encore pour tout \(a\) assez grand.
Solution 1¶
On montre d'abord que \(b \mid f(b)^2\) pour tout \(b\). Choisissons un entier \(n\) assez grand pour que \(nb - f(b) \geq C\). En prenant \(a = nb - f(b)\) dans \((\ast)\) (substitution), on obtient
donc \(b \mid f(b)^2\).
En particulier, \(p \mid f(p)\) pour tout nombre premier \(p\). Écrivons \(f(p) = k(p) \cdot p\). La majoration \(f(p) \leq f(1) \cdot p\) (valable pour \(p\) assez grand) montre, par le principe des tiroirs, qu'une certaine valeur \(k\) de \(k(p)\) est atteinte pour une infinité de nombres premiers \(p\). Montrons que \(f(a) = ka\) pour tout \(a\). Prenons \(b = p\) dans \((\ast)\), où \(p\) est un nombre premier assez grand avec \(k(p) = k\) :
Pour \(p\) assez grand, \(\operatorname{pgcd}(a + kp, p) = 1\), donc
Cela ne peut avoir lieu pour des \(p\) arbitrairement grands que si \(f(a) - ka = 0\). \(\blacksquare\)
Solution 2¶
On prend d'abord \(b = 1\) dans \((\ast)\) ; on obtient que
est un entier strictement positif pour tout \(a\) assez grand. Comme \(f(a) \leq a f(1)\) pour \(a\) assez grand, ce quotient est aussi au plus \(f(1)\). Il existe donc (principe des tiroirs) un entier \(k > 0\) tel que ce quotient vaille \(k\) pour une infinité de valeurs de \(a\) ; autrement dit,
pour une infinité de \(a\).
Fixons maintenant \(a\) quelconque dans \((\ast)\) : la quantité
est un entier pour une infinité de \(b\) (les mêmes \(b\) que ci-dessus, à un nombre fini d'exceptions près). D'autre part, pour \(b\) assez grand, cette quantité devient arbitrairement proche de \(\frac{f(a)}{k}\). Ce n'est possible que si \(\frac{f(a)}{k}\) est un entier et si
pour une infinité de \(b\). Cela se réécrit
Donc \(a^2\) est divisible par \(a + f(1)(k - f(1))\), et par conséquent \(f(1)^2 (k - f(1))^2\) l'est aussi (car \(a \equiv -f(1)(k - f(1))\) modulo ce nombre). Comme cela doit valoir pour tout \(a\), la seule possibilité est \(k = f(1)\), et alors \((\ast\ast)\) donne \(f(a) = ka\) pour tout \(a\). \(\blacksquare\)
Solution 3¶
Fixons deux entiers positifs distincts \(a\) et \(b\). D'après \((\ast)\), les deux entiers
sont tous deux multiples de \((a + f(c))(b + f(c))\) pour tout \(c\) assez grand. En prenant une combinaison linéaire adaptée (la première multipliée par \(f(b)\), moins la seconde multipliée par \(f(a)\)) pour éliminer le terme en \(c f(c)\), on trouve après développement que l'entier
est aussi un multiple de \((a + f(c))(b + f(c))\).
Mais quand \(c\) varie, \((\dagger)\) est majoré en valeur absolue par un multiple de \(c\) (car \(f(c) \leq f(1) c\)), alors que \((a + f(c))(b + f(c))\) est minoré par un multiple positif de \(c^2\) (par la minoration de \(f\)). Cette divisibilité n'est possible que si
pour tout \(c\) assez grand. Comme le coefficient de \(c\) dans cette relation linéaire est non nul, il existe des constantes \(k\), \(\ell\) telles que \(f(c) = kc + \ell\) pour tout \(c\) assez grand ; les constantes \(k\) et \(\ell\) sont nécessairement entières.
La valeur de \(\ell\) vérifie
donc \(b \mid \ell a^2 f(b)\) pour tous \(a\) et \(b\). En prenant \(b\) assez grand pour que \(f(b) = kb + \ell\), on obtient \(b \mid \ell^2 a^2\) pour tout \(b\) assez grand ; cela impose \(\ell = 0\). Alors \((\dagger\dagger\dagger)\) donne \(\frac{f(a)}{a} = \frac{f(b)}{b}\) pour tous \(a \neq b\) : il existe une constante \(k\) telle que \(f(a) = ka\) pour tout \(a\) (\(k\) est la constante définie plus haut). \(\blacksquare\)
Solution 4¶
Soit \(\Gamma\) l'ensemble des points \((a, f(a))\) ; c'est une partie infinie du quart de plan supérieur droit. À un point \(A = (a, f(a))\) de \(\Gamma\), on associe le point \(A' = \big(-f(a), -f(a)^2/a\big)\) du quart de plan inférieur gauche, et l'on note \(\Gamma'\) l'ensemble de ces points \(A'\). (Voir la figure du livret officiel.)
Affirmation. Pour tout point \(A \in \Gamma\), l'ensemble \(\Gamma\) est contenu dans un nombre fini de droites passant par \(A'\).
Preuve. Soit \(A = (a, f(a))\). L'équation fonctionnelle (avec \(a\) et \(b\) échangés) se réécrit \(b + f(a) \mid a f(b) - b f(a)\) ; donc tous les points de \(\Gamma\) sauf un nombre fini sont sur l'une des droites d'équation
Géométriquement, ce sont les droites passant par \(A' = (-f(a), -f(a)^2/a)\) de pente \(\frac{f(a) + m}{a}\). Comme \(\Gamma\) est contenu, à un nombre fini d'exceptions près, dans la région \(0 \leq y \leq f(1) \cdot x\), et que \(A'\) est strictement dans le quart de plan inférieur gauche, il n'y a qu'un nombre fini de valeurs de \(m\) pour lesquelles cette droite rencontre \(\Gamma\). \(\square\)
Soient maintenant \(A\), \(B\) deux points distincts de \(\Gamma\). Il est clair que \(A'\) et \(B'\) sont distincts. Une droite passant par \(A'\) et une droite passant par \(B'\) n'ont plus d'un point commun que si elles sont toutes deux égales à la droite \(A'B'\). D'après l'affirmation, la droite \(A'B'\) contient donc tous les points de \(\Gamma\) sauf un nombre fini. Si \(C\) est un autre point de \(\Gamma\), la droite \(A'C'\) contient elle aussi tous les points de \(\Gamma\) sauf un nombre fini, ce qui n'est possible que si \(A'C' = A'B'\).
Il existe donc une droite \(\ell\) qui passe par tous les points de \(\Gamma'\) et par tous les points de \(\Gamma\) sauf un nombre fini. Montrons qu'elle passe par l'origine \(O\) et par tous les points de \(\Gamma\). Par construction, \(A\), \(O\), \(A'\) sont alignés pour tout \(A \in \Gamma\). Comme \(\ell = AA'\) pour tous les points \(A \in \Gamma\) sauf un nombre fini, on a \(O \in \ell\). Ainsi tout point \(A \in \Gamma\) est sur la droite \(\ell = A'O\).
Comme \(\Gamma\) est contenu dans une droite passant par \(O\), il existe une constante réelle \(k\) (la pente de \(\ell\)) telle que \(f(a) = ka\) pour tout \(a\). Le nombre \(k\) est évidemment un entier strictement positif. \(\blacksquare\)
Remarques¶
Remarque 1 (autre preuve de \(p \mid f(p)\)). Il y a d'autres façons d'obtenir \(p \mid f(p)\) pour \(p\) premier, seul fait utilisé dans la solution 1. Par exemple, si \(f(p)\) n'était pas divisible par \(p\), la progression arithmétique \(p^2 + b f(p)\) prendrait des valeurs premières pour une infinité de \(b\) (théorème de Dirichlet) ; pour ces couples \((p, b)\), on aurait \(p + f(b) = p^2 + b f(p)\). En substituant \(a \mapsto b\) et \(b \mapsto p\) dans \((\ast)\), on obtient alors que \((f(p)^2 - p^2)(p - 1)\) est divisible par \(b + f(p)\), donc est nul, ce qui est impossible puisque \(p \nmid f(p)\).
Remarque 2. Sans la condition \(a + b > C\), le problème se traite par des méthodes bien plus naïves. Par exemple, en utilisant la divisibilité pour \(a, b \in \{1, 2, 3\}\), une vérification de cas un peu fastidieuse donne \(f(2) = 2f(1)\) et \(f(3) = 3f(1)\) ; c'est le point de départ d'une récurrence établissant \(f(n) = n f(1)\) pour tout \(n\).