Aller au contenu

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é

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

\[(f(a + 1), f(a + 2), \ldots, f(a + 50)) = (f(b + 1), f(b + 2), \ldots, f(b + 50)).\]

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.