Aller au contenu

Shortlist 2019, N3

Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Czech Republic

Concepts : Congruences, théorèmes de Fermat et d'Euler · Principe des tiroirs

Solution officielle : Shortlist officielle 2019 (avec solutions), section N3 (livret PDF)

Énoncé

We say that a set \(S\) of integers is rootiful if, for any positive integer \(n\) and any \(a_0, a_1, \ldots, a_n \in S\), all integer roots of the polynomial \(a_0 + a_1 x + \cdots + a_n x^n\) are also in \(S\). Find all rootiful sets of integers that contain all numbers of the form \(2^a - 2^b\) for positive integers \(a\) and \(b\).

Indices : les idées clés
  • Premiers éléments forcés : \(0 = 2^1 - 2^1\) et \(2 = 2^2 - 2^1\) sont dans \(S\), puis \(-1\) et \(1\) comme racines de polynômes simples, et \(-n\) dès que \(n \in S\).
  • Théorème d'Euler (solution 1) : \(t \mid 2^{\varphi(t)} - 1\) pour \(t\) impair, donc tout entier \(n\) a un multiple de la forme \(2^a - 2^b\).
  • Écriture en base \(n\) (solution 1) : si \(0, 1, \ldots, n-1 \in S\) et \(N \in S\) est un multiple de \(n\), l'écriture de \(N\) en base \(n\) fournit un polynôme à coefficients dans \(S\) dont \(n\) est racine.
  • Principe des tiroirs (solution 2) : il y a plus de polynômes \(\sum 2^{a_i} k^i\) (à termes bornés) que de valeurs possibles, donc deux sont égaux.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions).

Réponse : le seul ensemble qui convient est l'ensemble \(\mathbb{Z}\) de tous les entiers.

Solution 1

L'ensemble \(\mathbb{Z}\) est clairement rootiful. Montrons que tout ensemble rootiful \(S\) contenant tous les nombres \(2^a - 2^b\) (\(a, b \in \mathbb{Z}_{>0}\)) est égal à \(\mathbb{Z}\).

D'abord, \(0 = 2^1 - 2^1 \in S\) et \(2 = 2^2 - 2^1 \in S\). Ensuite \(-1 \in S\), car c'est une racine de \(2x + 2\), et \(1 \in S\), car c'est une racine de \(2x^2 - x - 1\). De plus, si \(n \in S\), alors \(-n\) est racine de \(x + n\), donc \(-n \in S\). Il suffit donc de prouver que tous les entiers strictement positifs sont dans \(S\).

Tout entier \(n > 0\) a un multiple dans \(S\). Écrivons \(n = 2^\alpha \cdot t\) avec \(\alpha \geq 0\) et \(t\) impair. Par le théorème d'Euler, \(t \mid 2^{\varphi(t)} - 1\), donc

\[n \mid 2^{\alpha + \varphi(t) + 1} - 2^{\alpha + 1}.\]

Or \(2^{\alpha + \varphi(t) + 1} - 2^{\alpha + 1} \in S\), donc \(S\) contient un multiple de tout entier \(n > 0\).

Récurrence. Montrons par récurrence que tous les entiers positifs sont dans \(S\). Supposons \(0, 1, \ldots, n-1 \in S\), et soit \(N \in S\) un multiple de \(n\). Écrivons \(N\) en base \(n\) :

\[N = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0.\]

Comme \(0 \leq a_i < n\) pour tout \(i\), tous les \(a_i\) sont dans \(S\). De plus \(a_0 = 0\), car \(N\) est un multiple de \(n\). Ainsi

\[a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n - N = 0,\]

donc \(n\) est racine d'un polynôme à coefficients dans \(S\) (les coefficients \(a_k, \ldots, a_1\), et \(-N \in S\)). Donc \(n \in S\), ce qui achève la récurrence. \(\blacksquare\)

Solution 2

Comme dans la solution précédente, \(0\), \(1\) et \(-1\) appartiennent nécessairement à \(S\).

Montrons en fait que tout entier \(k\) avec \(|k| > 2\) est racine d'un polynôme dont les coefficients sont de la forme \(2^a - 2^b\). Il suffit de traiter le cas \(k > 0\) : si \(k\) est racine de \(a_n x^n + \cdots + a_1 x + a_0\), alors \(-k\) est racine de \((-1)^n a_n x^n + \cdots - a_1 x + a_0\).

L'égalité

\[(2^{a_n} - 2^{b_n}) k^n + \cdots + (2^{a_0} - 2^{b_0}) = 0\]

équivaut à

\[2^{a_n} k^n + \cdots + 2^{a_0} = 2^{b_n} k^n + \cdots + 2^{b_0}.\]

Il s'agit donc de montrer que deux nombres de la forme \(2^{a_n} k^n + \cdots + 2^{a_0}\) (pour un \(n\) fixé) sont égaux, avec des exposants \((a_i)\) et \((b_i)\) différents.

On considère les polynômes dont chaque terme \(2^{a_i} k^i\) est au plus \(2k^n\), c'est-à-dire \(2 \leq 2^{a_i} \leq 2k^{n-i}\), ou encore \(1 \leq a_i \leq 1 + (n - i)\log_2 k\). Il y a donc \(1 + \lfloor (n-i) \log_2 k \rfloor\) choix possibles pour \(a_i\). Le nombre de tels polynômes est donc

\[\prod_{i=0}^{n} \big(1 + \lfloor (n-i) \log_2 k \rfloor\big) \geq \prod_{i=0}^{n-1} (n-i) \log_2 k = n! \, (\log_2 k)^n,\]

car \(1 + \lfloor x \rfloor \geq x\).

Comme il y a \(n + 1\) termes, chacun au plus égal à \(2k^n\), la valeur d'un tel polynôme est au plus \(2k^n (n+1)\). Or, pour \(n\) grand, \(n!\,(\log_2 k)^n > 2k^n(n+1)\). Il y a donc plus de polynômes que de valeurs possibles : par le principe des tiroirs, deux d'entre eux prennent la même valeur, ce qu'on voulait. Ainsi tout entier \(k\) est dans \(S\), et \(S = \mathbb{Z}\). \(\blacksquare\)