Shortlist 2024, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★★ · Proposé par : Japan
Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2024 (avec solutions), section N7 (livret PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
Let \(\mathbb{Z}_{>0}\) denote the set of positive integers. Let \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) be a function satisfying the following property: for \(m, n \in \mathbb{Z}_{>0}\), the equation
holds if and only if \(m\) and \(n\) are coprime.
For each positive integer \(n\), determine all the possible values of \(f(n)\).
Indices : les idées clés
- Équations fonctionnelles : substitutions : \(P(1,1)\), \(P(1, f(1))\), ... donnent \(f(1) = 1\), puis \(f(f(n)) = f(n)\), \(f(m^2) = f(m)\), et une forme simplifiée \(Q(m, n)\) de l'hypothèse.
- Divisibilité, PGCD : l'équation caractérise la coprimalité, ce qui permet de transporter des informations « premier avec » entre \(n\), \(f(n)\) et \(f(k)\).
- Valuations p-adiques (solution 1) : en choisissant \(X\) qui minimise \(\nu_p(f(X))\), on obtient \(3m \leq 2m\), absurde.
- Graphes : degrés, chemins, arbres (solution 2) : le graphe sur les nombres premiers où \(p \sim q\) si \(p \mid f(q)\) a pour composantes des graphes complets, qui sont en fait réduits à un sommet.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions et une remarque).
Réponse : les valeurs possibles de \(f(n)\) sont exactement les entiers ayant le même ensemble de facteurs premiers que \(n\) (en particulier \(f(1) = 1\)).
On note \(P(m, n)\) la propriété de l'énoncé, et \(\operatorname{rad}(n)\) le radical de \(n\) : le produit des nombres premiers distincts divisant \(n\).
Solution 1¶
On commence par une série de substitutions :
- \(P(1, 1)\) donne \(f(1)^2 = f(1) f(f(1))^2\), donc \(f(1) = f(f(1))^2\).
- \(P(1, f(1))\) donne \(f(f(1))^2 = f(1) f(f(f(1))) f(f(f(1)))\), donc \(f(f(f(1))) = 1\).
- \(P(1, f(f(1)))\) donne \(f(f(f(1)))^2 = f(1) f(f(f(f(1)))) f(f(f(f(1))))\), ce qui se simplifie en \(1 = f(1)^3\), donc \(f(1) = 1\).
- \(P(1, n)\) donne alors \(f(n) = f(f(n))\) pour tout \(n\).
- \(P(m, 1)\) donne \(f(m) = f(m^2)\) pour tout \(m\).
- En simplifiant \(P(m, n)\), on obtient : \(f(mn)^2 = f(m) f(n) f(m f(n))\) si et seulement si \(m\) et \(n\) sont premiers entre eux. On note cette propriété \(Q(m, n)\).
- \(Q(m, f(n))\) donne : \(f(m f(n)) = f(m) f(n)\) si et seulement si \(m\) et \(f(n)\) sont premiers entre eux. On note cette propriété \(R(m, n)\).
Affirmation 1. Si \(f(a) = 1\), alors \(a = 1\).
Preuve. Si \(a \neq 1\), \(Q(a, a)\) donne \(f(a)^2 \neq f(a)^2 f(a f(a))\). Si \(f(a) = 1\), les deux membres valent \(1\) : contradiction. \(\square\)
Affirmation 2. Si \(n \neq 1\), alors \(\operatorname{pgcd}(n, f(n)) \neq 1\).
Preuve. Si \(\operatorname{pgcd}(n, f(n)) = 1\), \(Q(f(n), n)\) donne \(f(n f(n))^2 = f(n)^3\), et \(Q(n, f(n))\) donne \(f(n f(n))^2 = f(n)^2 f(n f(n))\) ; ensemble, cela donne \(f(n) = 1\), ce qui contredit l'affirmation 1. \(\square\)
Affirmation 3. Pour tout \(n\), \(\operatorname{rad}(n) \mid f(n)\).
Preuve. Soit \(p\) premier divisant \(n\) ; écrivons \(n = p^v n'\) avec \(p \nmid n'\). \(Q(p^v, n')\) donne \(f(n)^2 = f(p^v) f(n') f(p^v f(n'))\). Comme \(\operatorname{pgcd}(p^v, f(p^v)) \neq 1\), on a \(p \mid f(p^v)\), donc \(p \mid f(n)\). \(\square\)
Affirmation 4. Si \(n\) est premier avec \(f(k)\), alors \(f(n)\) est premier avec \(f(k)\).
Preuve. \(Q(f(k), n)\) donne \(f(n f(k))^2 = f(k) f(n) f(f(k) f(n))\) ; en appliquant \(R(n, k)\) au membre de gauche, on obtient \(f(k) f(n) = f(f(k) f(n))\). Alors \(R(f(n), k)\) montre que \(f(n)\) est premier avec \(f(k)\). \(\square\)
Affirmation 5. Si \(p\) est premier, \(f(p)\) est une puissance de \(p\).
Preuve. Sinon, on sait que \(p \mid f(p)\) ; soit \(q \neq p\) un autre premier divisant \(f(p)\).
Si, pour un entier \(N\), \(p \nmid f(N)\), alors \(p\) est premier avec \(f(N)\), donc \(f(p)\) est premier avec \(f(N)\) (affirmation 4), donc \(q \nmid f(N)\), et donc \(q \nmid N\) (affirmation 3). Ainsi, si \(q \mid N\), alors \(p \mid f(N)\) (en particulier \(p \mid f(q)\)).
De même, si \(q \nmid f(N)\), alors \(f(q)\) est premier avec \(f(N)\) ; comme \(p \mid f(q)\), on a \(p \nmid f(N)\), donc \(p \nmid N\). Ainsi, si \(p \mid N\), alors \(q \mid f(N)\).
Avec \(\operatorname{rad}(n) \mid f(n)\), on obtient : pour tout \(n\) non premier avec \(pq\), on a \(pq \mid f(n)\).
Soit \(m = \min\{\nu_p(f(x)) : x \text{ non premier avec } pq\}\), et \(X\) un entier non premier avec \(pq\) tel que \(\nu_p(f(X)) = m\). Ce qui précède montre que \(m \geq 1\). Écrivons \(f(X) = p^m q^y X'\) avec \(y \geq 1\), \(p \nmid X'\) et \(q \nmid X'\). Comme \(f(f(X)) = f(X)\), on a \(f(p^m q^y X') = p^m q^y X'\). La propriété \(Q(p^m, q^y X')\) donne
Chacun des trois facteurs du membre de droite est la valeur de \(f\) en un entier non premier avec \(pq\), donc a une valuation \(p\)-adique au moins \(m\) : le membre de droite est divisible par \(p^{3m}\), alors que le membre de gauche ne l'est que par \(p^{2m}\). Contradiction. \(\square\)
Affirmation 6. Pour tout entier \(n\), \(\operatorname{rad}(f(n)) = \operatorname{rad}(n)\).
Preuve. On sait déjà que \(\operatorname{rad}(n) \mid f(n)\) ; il reste à voir qu'aucun autre premier ne divise \(f(n)\). Si \(p\) est premier et \(p \nmid n\), l'affirmation 5 montre que \(n\) est premier avec \(f(p)\), donc (affirmation 4) \(f(n)\) est premier avec \(f(p)\), c'est-à-dire \(p \nmid f(n)\). \(\square\)
Toutes ces valeurs sont atteintes. Étant donnés des entiers \(e(p) \geq 1\) pour chaque premier \(p\), la fonction
convient. En effet, pour chaque premier \(p\) divisant \(mn\), l'exposant de \(p\) vaut \(2e(p)\) dans \(f(mn)^2\), et \(e(p)\big([p \mid m] + [p \mid n] + [p \mid mn]\big)\) dans \(f(m^2) f(f(n)) f(m f(n)) = f(m) f(n) f(mn)\) ; ces exposants sont égaux pour tout \(p\) si et seulement si aucun \(p\) ne divise à la fois \(m\) et \(n\). Comme \(f(n)\) peut prendre ainsi n'importe quelle valeur de même radical que \(n\), la réponse est démontrée. \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, il existe des fonctions \(f\) qui conviennent et donnent toutes les valeurs annoncées, et l'on a :
- \(f(1) = 1\) ;
- \(f(m) = f(m^2)\) pour tout \(m\) ;
- \(f(n) = f(f(n))\) pour tout \(n\) ;
- \(f(mn)^2 = f(m) f(n) f(m f(n))\) si et seulement si \(m\) et \(n\) sont premiers entre eux : propriété \(Q(m, n)\).
En combinant \(Q(m, n)\) et \(Q(n, m)\), on obtient \(f(m f(n)) = f(n f(m))\) si \(m\) et \(n\) sont premiers entre eux.
Supposons maintenant \(m\) premier avec \(n\) et avec \(f(n)\). On a \(f(mn)^2 = f(m) f(n) f(m f(n))\) ; en élevant au carré et en utilisant \(Q(m, f(n))\),
Donc \(f(m f(n)) = f(m) f(n)\), puis \(f(mn)^2 = f(m)^2 f(n)^2\), d'où \(f(mn) = f(m) f(n) = f(m f(n)) = f(n f(m))\).
Si \(m\) est premier avec \(n\) et avec \(f(n)\), mais que \(n\) n'est pas premier avec \(f(m)\), on aurait
ce qui est absurde. Ainsi, pour \(m\) et \(n\) premiers entre eux, \(m\) est premier avec \(f(n)\) si et seulement si \(n\) est premier avec \(f(m)\). En particulier, pour deux premiers distincts \(p\) et \(q\), \(p \mid f(q)\) si et seulement si \(q \mid f(p)\) ; de même, pour tout \(k \geq 1\), \(p \mid f(q^k)\) si et seulement si \(q \mid f(p)\). Plus généralement, si \(p \nmid n\), alors \(p \mid f(n)\) si et seulement si \(n\) n'est pas premier avec \(f(p)\).
Le graphe. On forme un graphe dont les sommets sont les nombres premiers, avec une arête entre \(p \neq q\) si et seulement si \(p \mid f(q)\) (ce qui équivaut à \(q \mid f(p)\)) ; chaque sommet est de degré fini. Pour tout entier \(n\), les premiers divisant \(f(n)\) sont tous les voisins des premiers \(q \mid n\), plus éventuellement certains premiers \(p \mid n\).
Pour deux premiers distincts \(p\) et \(q\), on a \(f(p f(q)) = f(q f(p))\). Le membre de gauche est divisible par tous les premiers voisins de \(p\) ou voisins de voisins de \(q\), et éventuellement par \(p\) et par certains voisins de \(q\) ; l'énoncé symétrique vaut pour le membre de droite. Donc tout voisin d'un voisin de \(q\) est : \(p\), \(q\), un voisin de \(q\), ou à distance \(1\) ou \(2\) de \(p\). Or un premier \(r\) à distance \(2\) de \(q\) n'est à distance au plus \(2\) que d'un nombre fini de premiers ; en choisissant convenablement \(p\) (selon \(q\)), on conclut que tout voisin d'un voisin de \(q\) est \(q\) lui-même ou un voisin de \(q\).
Les composantes connexes du graphe sont donc des graphes complets (finis). Si \(m\) n'a de facteurs premiers que dans une composante et \(n\) que dans une autre, alors \(f(mn) = f(m) f(n)\). Si \(n\) est divisible par plusieurs premiers d'une même composante, en appliquant la formule de \(f(mn)^2\) successivement aux diviseurs de \(n\) qui sont des puissances de premiers, on voit que \(f(n)\) est divisible par tous les premiers de cette composante. En revanche, \(f(p^k)\) est divisible par tous les premiers de la composante de \(p\) sauf peut-être \(p\) lui-même ; on ne sait pas encore que \(p \mid f(p^k)\).
On distingue selon l'ordre (le nombre de sommets) de la composante.
Pour tout premier \(p\), on ne peut pas avoir \(f(p^k) = 1\), car \(Q(p^k, p^k)\) donne \(f(p^{2k})^2 \neq f(p^k) f(p^k) f(p^k f(p^k))\), ce qui, avec \(f(m^2) = f(m)\), deviendrait \(1 \neq 1\). Ainsi, pour une composante d'ordre \(1\), \(f(p^k)\) est une puissance non triviale de \(p\), qui a bien les mêmes facteurs premiers que \(p^k\).
Considérons une composante d'ordre au moins \(2\). Comme \(f(f(n)) = f(n)\), si la composante est d'ordre au moins \(3\), alors pour tout \(n \neq 1\) dont les facteurs premiers sont dans la composante, \(f(n)\) est divisible par tous les premiers de la composante. Si elle est d'ordre \(2\), on a vu que c'est vrai sauf peut-être pour \(n = p^k\). Mais si la composante est \(\{p, q\}\) et que \(f(p^k) = q^\ell\), alors \(f(q^\ell) = f(f(p^k)) = f(p^k) = q^\ell\), ce qui contredit \(p \mid f(q^\ell)\). Donc, dans une composante d'ordre au moins \(2\), pour tout \(n \neq 1\) dont les facteurs premiers sont dans la composante, \(f(n)\) est divisible par tous les premiers de la composante.
Dans une telle composante, soit \(R\) le produit de ses premiers, et \(t\) le plus grand entier tel que \(R^t \mid f(n)\) pour tout \(n \neq 1\) à facteurs premiers dans la composante ; on a vu que \(t \geq 1\). Si \(m\) et \(n\) sont des entiers \(> 1\) premiers entre eux, à facteurs premiers dans la composante, \(Q(m, n)\) montre que \(R^{3t}\) divise \(f(mn)^2\), donc \(R^{3t/2} \mid f(mn)\) (au sens \(R^{\lceil 3t/2 \rceil}\)). Pour tout \(n' \neq 1\) à facteurs premiers dans la composante, \(f(n')\) est divisible par tous les premiers de la composante, donc s'écrit comme un tel produit \(mn\) ; ainsi \(R^{3t/2} \mid f(f(n')) = f(n')\). Cela donne \(t \geq \frac{3t}{2}\), contradiction. Le livret note \(m\) le produit des premiers de la composante, comme la variable de \(Q(m, n)\) ; nous l'avons noté \(R\).
Toutes les composantes sont donc d'ordre \(1\) : \(f(p^k)\) est une puissance non triviale de \(p\), et \(f\) est multiplicative sur les puissances de premiers distincts, donc \(f(n)\) a exactement les mêmes facteurs premiers que \(n\). \(\blacksquare\)
Remarques¶
Remarque. Une preuve plus rapide, mais moins naturelle, de \(f(1) = 1\) : soit \(M\) la plus petite valeur prise par \(f\), atteinte en \(n\). Alors \(P(1, n)\) donne \(M^2 = f(n)^2 = f(1) f(f(n))^2 \geq M^3\), donc \(M = 1\), puis \(f(1) = 1\).