Shortlist 2009, N2¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Peru
Concepts : Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Principe des tiroirs
Solution officielle : Shortlist officielle 2009 (avec solutions), p. 71 (page 73 du PDF)
Énoncé¶
Un entier \(N\) strictement positif est dit équilibré si \(N = 1\) ou si \(N\) s'écrit comme produit d'un nombre pair de nombres premiers, pas forcément distincts. Étant donnés des entiers \(a\) et \(b\) strictement positifs, on considère le polynôme \(P\) défini par \(P(x) = (x + a)(x + b)\).
(a) Montrer qu'il existe des entiers \(a\) et \(b\) strictement positifs et distincts tels que tous les nombres \(P(1), P(2), \ldots, P(50)\) soient équilibrés.
(b) Montrer que si \(P(n)\) est équilibré pour tout entier \(n\) strictement positif, alors \(a = b\).
Énoncé original (anglais)
A positive integer \(N\) is called balanced, if \(N = 1\) or if \(N\) can be written as a product of an even number of not necessarily distinct primes. Given positive integers \(a\) and \(b\), consider the polynomial \(P\) defined by \(P(x) = (x + a)(x + b)\).
(a) Prove that there exist distinct positive integers \(a\) and \(b\) such that all the numbers \(P(1), P(2), \ldots, P(50)\) are balanced.
(b) Prove that if \(P(n)\) is balanced for all positive integers \(n\), then \(a = b\).
Indices : les idées clés
- Parité du nombre de facteurs premiers : \(f(n) \in \{0, 1\}\) vérifie \(f(nm) \equiv f(n) + f(m) \pmod 2\).
- (a) Tiroirs : il n'y a que \(2^{50}\) suites \((f(n + 1), \ldots, f(n + 50))\), donc deux entiers \(a \neq b\) donnent la même, et \(f(P(k)) \equiv 2f(a + k) \equiv 0\).
- (b) : avec \(n = k(b - a) - a\), \(P(n) = k(k + 1)(b - a)^2\), donc \(f(k) = f(k + 1)\) pour \(k\) grand, ce que contredisent les premiers et les carrés.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution et une remarque).
Solution¶
Définissons une fonction \(f\) sur les entiers strictement positifs par \(f(n) = 0\) si \(n\) est équilibré et \(f(n) = 1\) sinon. Évidemment, \(f(nm) \equiv f(n) + f(m) \pmod 2\) pour tous entiers \(n, m > 0\).
(a) Pour chaque entier \(n > 0\), considérons la suite binaire \((f(n + 1), f(n + 2), \ldots, f(n + 50))\). Comme il n'y a que \(2^{50}\) telles suites différentes, il existe deux entiers \(a \neq b\) strictement positifs tels que
Cela implique que, pour le polynôme \(P(x) = (x + a)(x + b)\), tous les nombres \(P(1), P(2), \ldots, P(50)\) sont équilibrés, puisque pour tout \(1 \leq k \leq 50\) on a \(f(P(k)) \equiv f(a + k) + f(b + k) \equiv 2f(a + k) \equiv 0 \pmod 2\).
(b) Supposons maintenant que \(P(n)\) soit équilibré pour tout entier \(n > 0\) et que \(a < b\). Posons \(n = k(b - a) - a\) pour \(k\) assez grand, de sorte que \(n\) soit strictement positif. Alors \(P(n) = k(k + 1)(b - a)^2\), et ce nombre ne peut être équilibré que si \(f(k) = f(k + 1)\). La suite \(f(k)\) doit donc devenir constante pour \(k\) assez grand. Mais c'est impossible, puisque \(f(p) = 1\) pour tout nombre premier \(p\) et \(f(t^2) = 0\) pour tout carré \(t^2\). Donc \(a = b\). \(\blacksquare\)
Remarque¶
Pour un entier \(k > 0\) donné, une recherche par ordinateur des couples d'entiers \((a, b)\) tels que \(P(1), P(2), \ldots, P(k)\) soient tous équilibrés donne les résultats suivants, avec \(a + b\) minimal et \(a < b\) :
| \(k\) | \(3\) | \(4\) | \(5\) | \(10\) | \(20\) |
|---|---|---|---|---|---|
| \((a, b)\) | \((2, 4)\) | \((6, 11)\) | \((8, 14)\) | \((20, 34)\) | \((1751, 3121)\) |
Trouver \(a\) et \(b\) dans la partie (a) ne peut donc pas se faire par des calculs élémentaires.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2013 N3 ★★☆☆☆ : Une infinité de \(n\) ont le même plus grand facteur premier pour \(n^4 + n^2 + 1\) et pour \((n + 1)^4 + (n + 1)^2 + 1\).
- 2011 N2 ★★☆☆☆ : Pour \(x\) assez grand, un produit de neuf facteurs \(x + d_i\) a toujours un diviseur premier plus grand que \(20\).
- 2014 N7 ★★★★☆ : Dans la suite \(a_{n+1} = a_n^3 - 4c a_n^2 + 5c^2 a_n + c\), chaque terme à partir du deuxième a un facteur premier nouveau.
- 2016 N8 ★★★★★ : Trouver les polynômes de degré impair dont les rapports de valeurs sont souvent des puissances \(d\)-ièmes proches de \(1\).