Shortlist 2012, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 46 (page 46 du PDF)
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
For a nonnegative integer \(n\) define \(\operatorname{rad}(n) = 1\) if \(n = 0\) or \(n = 1\), and \(\operatorname{rad}(n) = p_1 p_2 \cdots p_k\) where \(p_1 < p_2 < \cdots < p_k\) are all prime factors of \(n\). Find all polynomials \(f(x)\) with nonnegative integer coefficients such that \(\operatorname{rad}(f(n))\) divides \(\operatorname{rad}\big(f(n^{\operatorname{rad}(n)})\big)\) for every nonnegative integer \(n\).
Indices : les idées clés
- Traduire : pour tout premier \(p\), \(f(n) \equiv 0 \pmod p\) implique \(f\big(n^{\operatorname{rad}(n)^k}\big) \equiv 0 \pmod p\) pour tout \(k\).
- Petit théorème de Fermat : si \(p - 1 \mid n\) et \(p \mid f(n)\) avec \(\operatorname{pgcd}(p, n) = 1\), alors \(n^{\operatorname{rad}(n)^k} \equiv 1\), donc \(p \mid f(1)\) ; on prend \(n = (p - 1)t\) avec \(p \mid g(-t)\).
- Diviseurs premiers d'un polynôme : les valeurs \(g(-t)\) n'auraient qu'un nombre fini de facteurs premiers, donc \(g\) est constant (Schur) et \(f(x) = ax^m\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2012 (deux solutions et une remarque).
Solution 1¶
Réponse : \(f(x) = ax^m\), avec \(a\) et \(m\) entiers positifs ou nuls.
Montrons que \(f(x) = ax^m\) pour des entiers \(a, m \geq 0\). Si \(f\) est le polynôme nul, c'est terminé ; supposons donc que \(f\) a au moins un coefficient strictement positif. En particulier \(f(1) > 0\).
Soit \(p\) un nombre premier. La condition dit que \(f(n) \equiv 0 \pmod p\) implique
Comme \(\operatorname{rad}\big(n^{\operatorname{rad}(n)^k}\big) = \operatorname{rad}(n)\) pour tout \(k\), en appliquant plusieurs fois cette implication, on voit que si \(p\) divise \(f(n)\), alors
L'idée est de construire un nombre premier \(p\) et un entier \(n > 0\) tels que \(p - 1\) divise \(n\) et \(p\) divise \(f(n)\). Dans ce cas, pour \(k\) assez grand, \(p - 1\) divise \(\operatorname{rad}(n)^k\). Donc, si \(\operatorname{pgcd}(p, n) = 1\), alors \(n^{\operatorname{rad}(n)^k} \equiv 1 \pmod p\) par le petit théorème de Fermat, de sorte que
Écrivons \(f(x) = g(x) x^m\) avec \(g(0) \neq 0\). Soit \(t\) un entier strictement positif, \(p\) un facteur premier quelconque de \(g(-t)\) et \(n = (p - 1)t\). Alors \(p - 1\) divise \(n\) et \(f(n) = f\big((p - 1)t\big) \equiv f(-t) \equiv 0 \pmod p\), donc soit \(\operatorname{pgcd}(p, n) > 1\), soit (2) est vraie. Si \(\operatorname{pgcd}\big(p, (p - 1)t\big) > 1\), alors \(p\) divise \(t\) et \(g(0) \equiv g(-t) \equiv 0 \pmod p\), donc \(p\) divise \(g(0)\).
En conclusion, tout facteur premier de \(g(-t)\) divise \(g(0) f(1) \neq 0\), donc l'ensemble des facteurs premiers des \(g(-t)\), quand \(t\) parcourt les entiers strictement positifs, est fini. On sait que cela implique que \(g\) est un polynôme constant ; donc \(f(x) = ax^m\). \(\blacksquare\)
Solution 2¶
Soit \(f(x)\) un polynôme à coefficients entiers (pas forcément positifs) tel que \(\operatorname{rad}(f(n))\) divise \(\operatorname{rad}\big(f(n^{\operatorname{rad}(n)})\big)\) pour tout entier \(n \geq 0\). On donne une description complète de ces polynômes. Plus précisément, on affirme que si \(\xi\) est une racine de \(f(x)\), alors \(\xi^d\) l'est aussi pour tout entier \(d \geq 1\).
Chaque racine de \(f(x)\) est donc nulle ou est une racine de l'unité. En particulier, si une racine de l'unité \(\xi\) est racine de \(f(x)\), alors \(1 = \xi^d\) l'est aussi (pour un certain entier \(d \geq 1\)). Dans le problème posé, \(f(x)\) a des coefficients positifs ou nuls ; donc soit \(f(x)\) est nul, soit \(f(1) > 0\) et \(\xi = 0\) est la seule racine possible. Dans les deux cas, \(f(x) = ax^m\) avec \(a\) et \(m\) entiers positifs ou nuls.
Pour prouver l'affirmation, soit \(\xi\) une racine de \(f(x)\), et \(g(x)\) un facteur irréductible de \(f(x)\) tel que \(g(\xi) = 0\). Si \(0\) ou \(1\) est racine de \(g(x)\), alors \(\xi = 0\) ou \(\xi = 1\) (puisque \(g\) est irréductible), et c'est terminé. Supposons donc \(g(0), g(1) \neq 0\). En décomposant \(d\) en produit de nombres premiers, il suffit de traiter le cas où \(d = p\) est premier. On raisonne pour \(p = 2\). Comme \(\operatorname{rad}(2^k) = 2\) pour tout \(k\), on a
Montrons que \(g(x)\) divise \(f(x^2)\). Supposons le contraire. Comme \(g(x)\) est irréductible, il existe des polynômes à coefficients entiers \(a(x)\), \(b(x)\) et un entier \(N\) tels que
Chaque facteur premier \(p\) de \(g(2^k)\) divise \(f(2^k)\), donc, par \(\operatorname{rad}(f(2^k)) \mid \operatorname{rad}(f(2^{2k}))\), il divise aussi \(f(2^{2k})\). Par l'égalité ci-dessus avec \(x = 2^k\), il s'ensuit que \(p\) divise \(N\).
En résumé, tout diviseur premier de \(g(2^k)\) divise \(N\), pour tout \(k \geq 0\). Soient \(p_1, \ldots, p_n\) les nombres premiers impairs qui divisent \(N\), et supposons
Si \(k\) est divisible par \(\varphi\big(p_1^{\alpha_1 + 1} \cdots p_n^{\alpha_n + 1}\big)\), alors
Il s'ensuit que, pour chaque \(i\), la plus grande puissance de \(p_i\) qui divise \(g(2^k)\) et \(g(1)\) est la même, à savoir \(p_i^{\alpha_i}\). D'autre part, pour \(k\) assez grand, la plus grande puissance de \(2\) qui divise \(g(2^k)\) et \(g(0) \neq 0\) est la même. Par ce qui précède, pour \(k\) divisible par \(\varphi\big(p_1^{\alpha_1 + 1} \cdots p_n^{\alpha_n + 1}\big)\) et assez grand, on obtient que \(g(2^k)\) divise \(g(0) \cdot g(1)\). C'est impossible, car \(g(0), g(1) \neq 0\) sont fixés et \(g(2^k)\) est arbitrairement grand.
En conclusion, \(g(x)\) divise \(f(x^2)\). Comme \(\xi\) est une racine de \(f(x)\) avec \(g(\xi) = 0\), on a \(f(\xi^2) = 0\) : \(\xi^2\) est une racine de \(f(x)\).
De même, si \(\xi\) est une racine de \(f(x)\) et \(p\) un nombre premier quelconque, alors \(\xi^p\) est aussi racine. L'argument est entièrement analogue : dans la preuve ci-dessus, on remplace simplement \(2\) par \(p\) et « premier impair » par « premier différent de \(p\) ». \(\blacksquare\)
Remarque¶
On peut aussi prouver l'affirmation de la seconde solution en faisant varier \(n\) modulo \(p\) dans (1). Par exemple, on obtient
pour tout entier \(k \geq 1\). On peut montrer que si \(\operatorname{pgcd}(n, p) = 1\), alors \(\operatorname{rad}(n + pk)\) parcourt toutes les classes \(r\) modulo \(p - 1\) telles que \(\operatorname{pgcd}(r, p - 1)\) soit sans facteur carré. Donc si \(f(n) \equiv 0 \pmod p\), alors \(f(n^r) \equiv 0 \pmod p\) pour tous ces entiers \(r\). Cela implique l'affirmation par un argument menant à l'identité (3).