Shortlist 2018, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Mexico
Concepts : Principe des tiroirs · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2018 (avec solutions), p. 66 (page 68 du PDF)
Énoncé¶
Let \(f : \{1, 2, 3, \ldots\} \to \{2, 3, \ldots\}\) be a function such that \(f(m + n) \mid f(m) + f(n)\) for all pairs \(m, n\) of positive integers. Prove that there exists a positive integer \(c > 1\) which divides all values of \(f\).
Indices : les idées clés
- Les ensembles \(S_m = \{n : m \mid f(n)\}\) (solution 1) : grâce à \(f(n) \mid f(n-d) + f(d)\), un tel ensemble infini est exactement l'ensemble des multiples de son plus petit élément.
- Cas borné / non borné (solution 1) : si \(f\) est bornée, un nombre de la forme \(N d_1 \cdots d_k + 1\) force un premier fréquent à diviser toutes les valeurs ; sinon, on utilise les « pics » de \(f\), où \(f(k) + f(p - k) = f(p)\).
- Principe des tiroirs (solution 1) : une infinité de valeurs aux pics sont congrues modulo \(f(1)\).
- PGCD et algorithme d'Euclide (solution 2) : \(d_n = \gcd(f(n), f(1))\) décroît pour la divisibilité, et on reproduit l'algorithme d'Euclide pour montrer que \(\gcd(f(a), f(b)) \mid f(1)\) si \(a\) et \(b\) sont premiers entre eux.
- Croissance au plus linéaire contre grands écarts entre premiers (solution 2) : \(f(n) < n + C\), mais des valeurs deux à deux premières entre elles doivent avoir un grand facteur premier.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et une remarque).
Solution 1¶
Pour tout entier \(m \geq 1\), on pose \(S_m = \{n : m \mid f(n)\}\).
Lemme. Si \(S_m\) est infini, alors \(S_m = \{d, 2d, 3d, \ldots\} = d \cdot \mathbb{Z}_{>0}\) pour un certain entier \(d \geq 1\).
Preuve. Soit \(d = \min S_m\) ; par définition, \(m \mid f(d)\). Si \(n \in S_m\) et \(n > d\), alors \(m \mid f(n) \mid f(n - d) + f(d)\), donc \(m \mid f(n - d)\) et \(n - d \in S_m\). Soit \(r \leq d\) le plus petit entier positif tel que \(n \equiv r \pmod d\) ; en répétant cette étape, on obtient \(n - d, n - 2d, \ldots, r \in S_m\). Par minimalité de \(d\), on a \(r = d\), donc \(d \mid n\). En partant d'éléments arbitrairement grands de \(S_m\), ce procédé atteint tous les multiples de \(d\), qui sont donc tous dans \(S_m\). \(\square\)
On distingue deux cas.
Cas 1 : \(f\) est bornée. Un premier \(p\) est dit fréquent si \(S_p\) est infini, c'est-à-dire si \(p\) divise \(f(n)\) pour une infinité de \(n\) ; sinon il est sporadique. Comme \(f\) est bornée, seuls un nombre fini de premiers divisent au moins un \(f(n)\) ; il n'y a donc qu'un nombre fini d'entiers \(n\) tels que \(f(n)\) ait un diviseur premier sporadique. Soit \(N\) un entier plus grand que tous ces \(n\).
Soient \(p_1, \ldots, p_k\) les premiers fréquents. D'après le lemme, \(S_{p_i} = d_i \cdot \mathbb{Z}_{>0}\) pour un certain \(d_i\). Considérons
Comme \(n > N\), tous les diviseurs premiers de \(f(n)\) (il y en a, car \(f(n) \geq 2\)) sont fréquents. Soit \(p_i\) l'un d'eux. Alors \(n \in S_{p_i}\), donc \(d_i \mid n\). Mais \(n \equiv 1 \pmod{d_i}\), donc \(d_i = 1\). Ainsi \(S_{p_i} = \mathbb{Z}_{>0}\), et \(p_i\) divise toutes les valeurs de \(f\).
Cas 2 : \(f\) n'est pas bornée. Montrons que \(f(1)\) divise tous les \(f(n)\). Soit \(a = f(1)\). Comme \(1 \in S_a\), d'après le lemme il suffit de montrer que \(S_a\) est infini.
Un entier \(p \geq 1\) est un pic si \(f(p) > \max\big(f(1), \ldots, f(p - 1)\big)\). Comme \(f\) n'est pas bornée, il y a une infinité de pics. Soit \(1 = p_1 < p_2 < \cdots\) la suite des pics, et \(h_k = f(p_k)\). Pour tout pic \(p_i\) et tout \(k < p_i\), on a \(f(p_i) \mid f(k) + f(p_i - k) < 2f(p_i)\), donc
Par le principe des tiroirs, une infinité des nombres \(h_1, h_2, \ldots\) sont congrus entre eux modulo \(a\). Soit \(k_0 < k_1 < k_2 < \cdots\) une suite infinie d'indices telle que \(h_{k_0} \equiv h_{k_1} \equiv \cdots \pmod a\). D'après (1),
donc \(p_{k_i} - p_{k_0} \in S_a\) pour tout \(i \geq 1\). Cela fournit une infinité d'éléments de \(S_a\). Donc \(S_a\) est infini, et \(f(1) = a\) divise \(f(n)\) pour tout \(n\) ; comme \(a \geq 2\), c'est le \(c\) cherché. \(\blacksquare\)
Solution 2¶
Soit \(d_n = \gcd\big(f(n), f(1)\big)\). Comme \(d_{n+1} \mid f(1)\) et \(d_{n+1} \mid f(n+1) \mid f(n) + f(1)\), on a \(d_{n+1} \mid f(n)\), puis \(d_{n+1} \mid \gcd\big(f(n), f(1)\big) = d_n\). Ainsi chaque terme de la suite \(d_1, d_2, \ldots\) divise les précédents. Soit \(d = \min(d_1, d_2, \ldots) = \gcd(d_1, d_2, \ldots) = \gcd\big(f(1), f(2), \ldots\big)\) ; il faut montrer que \(d \geq 2\).
Par l'absurde, supposons \(d = 1\) : il existe alors un indice \(n_0\) tel que \(d_n = 1\) pour tout \(n \geq n_0\), c'est-à-dire que \(f(n)\) est premier avec \(f(1)\).
Affirmation 1. Si \(2^k \geq n_0\), alors \(f(2^k) \leq 2^k\).
Preuve. Par hypothèse, \(f(2n) \mid 2f(n)\) ; une récurrence immédiate donne \(f(2^k) \mid 2^k f(1)\). Si \(2^k \geq n_0\), \(f(2^k)\) est premier avec \(f(1)\), donc divise \(2^k\). \(\square\)
Affirmation 2. Il existe une constante \(C\) telle que \(f(n) < n + C\) pour tout \(n\).
Preuve. Soit \(K = 2^k\) la première puissance de \(2\) supérieure ou égale à \(n_0\). D'après l'affirmation 1, \(f(K) \leq K\). Comme \(f(n + K) \mid f(n) + f(K)\), on a \(f(n + K) \leq f(n) + f(K) \leq f(n) + K\). Si \(n = tK + r\) avec \(t \geq 0\) et \(1 \leq r \leq K\), on obtient
donc l'affirmation est vraie avec \(C = \max\big(f(1), \ldots, f(K)\big)\). \(\square\)
Affirmation 3. Si \(a, b \geq 1\) sont premiers entre eux, alors \(\gcd\big(f(a), f(b)\big) \mid f(1)\). En particulier, si \(a, b \geq n_0\) sont premiers entre eux, alors \(f(a)\) et \(f(b)\) sont premiers entre eux.
Preuve. Soit \(\delta = \gcd\big(f(a), f(b)\big)\). On reproduit l'algorithme d'Euclide ; formellement, on raisonne par récurrence sur \(a + b\). Si \(a = 1\) ou \(b = 1\), on a bien \(\delta \mid f(1)\). Sinon, sans perte de généralité \(1 < a < b\). Alors \(\delta \mid f(a)\) et \(\delta \mid f(b) \mid f(a) + f(b - a)\), donc \(\delta \mid f(b - a)\). Ainsi \(\delta\) divise \(\gcd\big(f(a), f(b - a)\big)\), qui divise \(f(1)\) par hypothèse de récurrence. \(\square\)
Soit \(p_1 < p_2 < \cdots\) la suite des nombres premiers ; pour tout \(k\), soit \(q_k\) la plus petite puissance de \(p_k\) telle que \(q_k \geq n_0\). (Il n'y a qu'un nombre fini d'indices \(k\) avec \(q_k \neq p_k\).)
Soit \(N\) un entier positif, et considérons les nombres
Ce sont \(N + 1\) nombres, tous supérieurs à \(1\), deux à deux premiers entre eux d'après l'affirmation 3. Ils ont donc au total au moins \(N + 1\) diviseurs premiers distincts, et le plus grand est au moins \(p_{N+1}\). Ainsi \(\max\big(f(1), f(q_1), \ldots, f(q_N)\big) \geq p_{N+1}\).
Choisissons \(N\) tel que \(\max(q_1, \ldots, q_N) = p_N\) (c'est le cas pour \(N\) assez grand) et \(p_{N+1} - p_N > C\) (c'est possible car il existe des écarts arbitrairement grands entre nombres premiers consécutifs). On obtient la contradiction
ce qui prouve l'énoncé. \(\blacksquare\)
Remarques¶
Remarque (sur la solution 1). En prolongeant la solution 1, on peut montrer que si \(f\) n'est pas bornée, alors \(f(n) = an\) avec \(a = f(1)\). Il suffit de montrer que \(f(n + 1) = f(n) + a\) pour tout \(n\), puis de conclure par récurrence. Soit \(p\) un pic tel que \(p > n + 2\) et \(h = f(p) > f(n) + 2a\). D'après (1), \(f(p - 1) = f(p) - f(1) = h - a\) et \(f(n + 1) = f(p) - f(p - n - 1) = h - f(p - n - 1)\). De \(h - a = f(p - 1) \mid f(n) + f(p - n - 1) < f(n) + h < 2(h - a)\), on tire \(f(n) + f(p - n - 1) = h - a\). Alors
En revanche, il existe une large famille de fonctions bornées vérifiant les conditions, par exemple