Shortlist 2017, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : U.S.A.
Concepts : Polynômes à coefficients entiers · Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois · Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2017 (avec solutions), p. 85 (page 87 du PDF)
Problème 6 de l'OIM 2017
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2017, où il était le problème 6 (jour 2).
Énoncé¶
Say that an ordered pair \((x, y)\) of integers is an irreducible lattice point if \(x\) and \(y\) are relatively prime. For any finite set \(S\) of irreducible lattice points, show that there is a homogenous polynomial in two variables, \(f(x, y)\), with integer coefficients, of degree at least \(1\), such that \(f(x, y) = 1\) for each \((x, y)\) in the set \(S\).
Note: A homogenous polynomial of degree \(n\) is any nonzero polynomial of the form
Indices : les idées clés
- Polynômes « interpolateurs » : \(g_i = \prod_{j \neq i} (y_j x - x_j y)\) s'annule en tous les points sauf \((x_i, y_i)\) ; on corrige ainsi les valeurs point par point.
- Polynômes à coefficients entiers : tout se ramène à un polynôme homogène à coefficients entiers valant \(1\) modulo \(a\) en tous les couples premiers entre eux.
- Congruences, théorèmes de Fermat et d'Euler : \((x^{p-1} + y^{p-1})^{\varphi(a)} \equiv 1\) (solution 1) ; \(g(x_n, y_n)^{p-1} \equiv 1 \pmod p\) (solution 2).
- Théorème des restes chinois (solution 1) : on recolle les polynômes obtenus pour chaque puissance de premier grâce à une relation de Bézout entre les \(a/q_i\).
- Divisibilité, PGCD et algorithme d'Euclide : Bézout donne \(cx + dy = 1\) pour un point irréductible, d'où un polynôme de degré 1 valant \(1\) en ce point.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2017 (deux solutions et une remarque).
Solution 1¶
Remarquons d'abord qu'il suffit de trouver un polynôme homogène \(f\) avec \(f(x, y) = \pm 1\) sur \(S\), car alors \(f^2(x, y) = 1\). Notons \((x_1, y_1), \ldots, (x_n, y_n)\) les points irréductibles. Si deux d'entre eux, \((x_i, y_i)\) et \((x_j, y_j)\), sont sur une même droite passant par l'origine, alors \((x_j, y_j) = (-x_i, -y_i)\), car les deux points sont irréductibles. On a alors \(f(x_j, y_j) = \pm f(x_i, y_i)\) pour tout \(f\) homogène ; on peut donc supposer, en oubliant les points en trop, que deux points ne sont jamais alignés avec l'origine.
Considérons les polynômes homogènes \(\ell_i(x, y) = y_i x - x_i y\) et posons
Alors \(\ell_i(x_j, y_j) = 0\) si et seulement si \(j = i\), car chaque droite passant par l'origine ne contient qu'un des points. Ainsi \(g_i(x_j, y_j) = 0\) pour tout \(j \neq i\). Posons \(a_i = g_i(x_i, y_i)\) ; on a \(a_i \neq 0\). Le polynôme \(g_i\) est homogène de degré \(n - 1\) et vérifie :
- \(g_i(x_j, y_j) = 0\) si \(j \neq i\) ;
- \(g_i(x_i, y_i) = a_i\).
Pour tout \(N \geq n - 1\), il existe aussi un polynôme homogène de degré \(N\) ayant ces deux propriétés. En effet, soit \(I_i(x, y)\) un polynôme homogène de degré 1 tel que \(I_i(x_i, y_i) = 1\) ; il existe car \((x_i, y_i)\) est irréductible (Bézout). Alors \(I_i(x, y)^{N - (n-1)} g_i(x, y)\) convient et est de degré \(N\).
On ramène alors le problème à l'affirmation suivante.
Affirmation. Pour tout entier \(a \geq 1\), il existe un polynôme homogène \(f_a(x, y)\) à coefficients entiers, de degré au moins 1, tel que \(f_a(x, y) \equiv 1 \pmod a\) pour tous \(x, y\) premiers entre eux.
Pourquoi l'affirmation suffit. Prenons pour \(a\) le PPCM des \(a_i\) (\(1 \leq i \leq n\)). Soit \(f_a\) donné par l'affirmation ; choisissons une puissance \(f_a(x, y)^k\) de degré \(N \geq n - 1\). Pour chaque \(i\), \(f_a(x_i, y_i)^k - 1\) est divisible par \(a\), donc par \(a_i\) ; en soustrayant à \(f_a^k\) les multiples convenables \(\frac{f_a(x_i, y_i)^k - 1}{a_i} \cdot I_i^{N-(n-1)} g_i\), on obtient un polynôme homogène à coefficients entiers, de degré \(N\), valant \(1\) en chaque \((x_i, y_i)\).
Preuve de l'affirmation. On décompose \(a\) en facteurs premiers. D'abord, si \(a = p^k\) est une puissance d'un nombre premier, on peut prendre :
- \(f_a(x, y) = \left(x^{p-1} + y^{p-1}\right)^{\varphi(a)}\) si \(p\) est impair ;
- \(f_a(x, y) = \left(x^2 + xy + y^2\right)^{\varphi(a)}\) si \(p = 2\).
Précision ajoutée : pour \(x, y\) premiers entre eux, \(x^{p-1} + y^{p-1}\) vaut \(1\) ou \(2\) modulo \(p\) (\(p\) impair), et \(x^2 + xy + y^2\) est impair ; dans les deux cas la base est première avec \(a\), et le théorème d'Euler donne \(f_a \equiv 1 \pmod a\).
Soit maintenant \(a\) quelconque, \(a = q_1 q_2 \cdots q_k\) où les \(q_i\) sont des puissances de nombres premiers deux à deux premières entre elles. Soient \(f_{q_i}\) les polynômes construits ci-dessus, et \(F_{q_i}\) des puissances de ceux-ci ayant toutes le même degré. On a
pour tous \(x, y\) premiers entre eux. Par le lemme de Bézout, une combinaison linéaire entière des \(\frac{a}{q_i}\) vaut \(1\) (c'est l'argument des restes chinois). Il existe donc une combinaison linéaire \(\sum c_i \frac{a}{q_i} F_{q_i}\) des \(F_{q_i}\) qui est \(\equiv 1 \pmod a\) en tout couple \((x, y)\) premier entre eux ; et ce polynôme est homogène car tous les \(F_{q_i}\) ont le même degré. \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, notons \((x_1, y_1), \ldots, (x_n, y_n)\) les points irréductibles et supposons sans perte de généralité que deux points ne sont jamais alignés avec l'origine. On construit par récurrence sur \(n\) un polynôme homogène \(f\) tel que \(f(x_i, y_i) = 1\) pour tout \(1 \leq i \leq n\).
Si \(n = 1\). Comme \(x_1\) et \(y_1\) sont premiers entre eux, il existe des entiers \(c, d\) avec \(cx_1 + dy_1 = 1\) (Bézout). Alors \(f(x, y) = cx + dy\) convient.
Si \(n \geq 2\). Par hypothèse de récurrence, on dispose d'un polynôme homogène \(g\) tel que \(g(x_1, y_1) = \cdots = g(x_{n-1}, y_{n-1}) = 1\). Soient \(j = \deg g\),
et \(a_n = g_n(x_n, y_n)\). Par hypothèse, \(a_n \neq 0\). Prenons des entiers \(c, d\) tels que \(cx_n + dy_n = 1\). On cherche \(f\) sous la forme
où \(K, L\) sont des entiers positifs et \(C\) un entier ; on impose \(L = Kj - n + 1\) pour que \(f\) soit homogène.
Comme \(g(x_i, y_i) = 1\) et \(g_n(x_i, y_i) = 0\) pour \(i \leq n - 1\), on a automatiquement \(f(x_1, y_1) = \cdots = f(x_{n-1}, y_{n-1}) = 1\), quels que soient \(K\), \(L\), \(C\). De plus,
Si l'on trouve un exposant \(K\) tel que \(g(x_n, y_n)^K \equiv 1 \pmod{a_n}\), on peut choisir \(C\) de sorte que \(f(x_n, y_n) = 1\). Choisissons un tel \(K\).
Soit \(p\) un diviseur premier quelconque de \(a_n\). Comme
il existe \(1 \leq k < n\) tel que \(x_k y_n \equiv x_n y_k \pmod p\). Montrons d'abord que \(x_k x_n\) ou \(y_k y_n\) est premier avec \(p\). C'est immédiat si \(x_k y_n \equiv x_n y_k \not\equiv 0 \pmod p\). Sinon, \(x_k y_n \equiv x_n y_k \equiv 0 \pmod p\). Si par exemple \(p \mid x_k\), alors \(p \nmid y_k\) car \((x_k, y_k)\) est irréductible, donc \(p \mid x_n\), puis \(p \nmid y_n\) car \((x_n, y_n)\) est irréductible. En résumé, \(p \mid x_k\) entraîne \(p \nmid y_k y_n\). De même, \(p \mid y_n\) entraîne \(p \nmid x_k x_n\).
(Le livret écrit « car \((x_k, y_k)\) est irréductible » pour \(p \nmid y_n\) ; il faut lire \((x_n, y_n)\).)
Par homogénéité de \(g\) (de degré \(d = j\)), on a les congruences
et
(Le livret note \(d\) le degré de \(g\), appelé \(j\) plus haut.)
Si \(p \nmid x_k x_n\), on élève (1.1) à la puissance \(p - 1\) ; sinon, on élève (1.2) à la puissance \(p - 1\). Par le théorème de Fermat, dans les deux cas,
Si \(p^\alpha \mid a_n\), on a alors
(le livret écrit « \(p^\alpha \mid m\) » ; il faut lire \(p^\alpha \mid a_n\)), de sorte que l'exposant \(K = n \cdot \varphi(a_n)\), multiple de tous les \(p^{\alpha-1}(p-1)\), convient. (Le facteur \(n\) sert seulement à avoir \(K \geq n\), donc \(L > 0\).) \(\blacksquare\)
Remarques¶
Remarque 1 (pas de borne uniforme sur le degré). Il n'existe pas de constante \(C\) telle que, pour deux points irréductibles quelconques, il existe un polynôme homogène à coefficients entiers de degré au plus \(C\) valant \(1\) en ces deux points. En effet, si l'un des points est \((1, 0)\) et l'autre \((a, b)\), le polynôme \(f(x, y) = a_0 x^n + a_1 x^{n-1} y + \cdots + a_n y^n\) doit vérifier \(a_0 = 1\), donc \(a^n \equiv 1 \pmod b\). Pour \(a = 3\) et \(b = 2^k\) avec \(k \geq 3\), on obtient \(n \geq 2^{k-2}\). En choisissant \(2^{k-2} > C\), on aboutit à une contradiction.