Shortlist 2011, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : non indiqué
Concepts : Ordre d'un élément et racines primitives · Polynômes à coefficients entiers · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 70 (page 71 du PDF)
Énoncé¶
Let \(P(x)\) and \(Q(x)\) be two polynomials with integer coefficients such that no nonconstant polynomial with rational coefficients divides both \(P(x)\) and \(Q(x)\). Suppose that for every positive integer \(n\) the integers \(P(n)\) and \(Q(n)\) are positive, and \(2^{Q(n)} - 1\) divides \(3^{P(n)} - 1\). Prove that \(Q(x)\) is a constant polynomial.
Indices : les idées clés
- PGCD borné : par Bézout dans \(\mathbb{Q}[x]\), \(P(x)R(x) - Q(x)S(x) = d\) avec \(R\), \(S\) à coefficients entiers, donc \(\gcd(P(n), Q(n)) \leq d\).
- Ordres modulo \(M = 2^{Q(m)} - 1\) : l'ordre de \(2\) est \(a = Q(m)\), celui de \(3\) est un diviseur \(b\) de \(P(m)\), et \(\gcd(a, b) \leq d\).
- Périodicité des polynômes : \(Q(m + ax) \equiv Q(m) \pmod a\) et \(P(m + ax - by) \equiv P(m + ax) \pmod b\) ; on choisit \(1 \leq m + ax - by \leq d\) pour obtenir \(M \leq 3^{P(j)} - 1\) avec \(j \leq d\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et une remarque).
Solution¶
Montrons d'abord qu'il existe un entier \(d\) tel que \(\gcd\big(P(n), Q(n)\big) \leq d\) pour tout entier \(n > 0\).
Comme \(P(x)\) et \(Q(x)\) sont premiers entre eux (en tant que polynômes à coefficients rationnels), l'algorithme d'Euclide fournit des polynômes \(R_0(x)\), \(S_0(x)\) à coefficients rationnels tels que \(P(x)R_0(x) - Q(x)S_0(x) = 1\). En multipliant par un entier \(d > 0\) convenable, on obtient des polynômes \(R(x) = d \cdot R_0(x)\) et \(S(x) = d \cdot S_0(x)\) à coefficients entiers tels que \(P(x)R(x) - Q(x)S(x) = d\). On a alors \(\gcd\big(P(n), Q(n)\big) \leq d\) pour tout entier \(n\).
Pour prouver l'énoncé, supposons que \(Q(x)\) n'est pas constant. Alors la suite \(Q(n)\) n'est pas bornée, et l'on peut choisir un entier \(m > 0\) tel que
Comme \(M = 2^{Q(m)} - 1 \mid 3^{P(m)} - 1\), on a \(2 \nmid M\) et \(3 \nmid M\). Soient \(a\) et \(b\) les ordres multiplicatifs de \(2\) et de \(3\) modulo \(M\) respectivement. Évidemment \(a = Q(m)\), puisque les puissances inférieures de \(2\) n'atteignent pas \(M\). Comme \(M\) divise \(3^{P(m)} - 1\), on a \(b \mid P(m)\). Donc \(\gcd(a, b) \leq \gcd\big(P(m), Q(m)\big) \leq d\).
Comme l'expression \(ax - by\) prend toutes les valeurs entières divisibles par \(\gcd(a, b)\) quand \(x\) et \(y\) parcourent les entiers positifs ou nuls, il existe des entiers \(x, y \geq 0\) tels que
Comme \(Q(m + ax) \equiv Q(m) \pmod a\), on a
et donc
Ensuite, comme \(P(m + ax - by) \equiv P(m + ax) \pmod b\), on a
Comme \(P(m + ax - by) > 0\), cela implique \(M \leq 3^{P(m + ax - by)} - 1\). Mais \(P(m + ax - by)\) figure parmi \(P(1), P(2), \ldots, P(d)\), donc
ce qui contredit (1). \(\blacksquare\)
Remarque¶
Voici une autre variante de la solution ci-dessus. Notons \(k\) le degré de \(P\) et \(p\) son coefficient dominant. Considérons un entier \(n > 0\) quelconque et posons \(a = Q(n)\). Notons encore \(b\) l'ordre multiplicatif de \(3\) modulo \(2^a - 1\). Comme \(2^a - 1 \mid 3^{P(n)} - 1\), on a \(b \mid P(n)\). De plus, comme \(2^{Q(n + at)} - 1 \mid 3^{P(n + at)} - 1\) et \(a = Q(n) \mid Q(n + at)\) pour tout entier \(t > 0\), on a \(2^a - 1 \mid 3^{P(n + at)} - 1\), donc aussi \(b \mid P(n + at)\).
Par conséquent, \(b\) divise \(\gcd\{P(n + at) : t \geq 0\}\) ; il divise donc aussi le nombre
Finalement, \(b \mid \gcd\big(P(n), k! \cdot p \cdot Q(n)^k\big)\), qui est borné par les mêmes arguments qu'au début de la solution. Donc \(3^b - 1\) est borné, et par conséquent \(2^{Q(n)} - 1\) l'est aussi.