Aller au contenu

Shortlist 2022, N7

Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : U.S.A.

Concepts : Congruences, théorèmes de Fermat et d'Euler · Polynômes : racines, relations de Viète, factorisation · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 69 (page 71 du PDF)

Problème 3 de l'OIM 2022

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2022, où il était le problème 3 (jour 1).

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(k\) be a positive integer and let \(S\) be a finite set of odd prime numbers. Prove that there is at most one way (modulo rotation and reflection) to place the elements of \(S\) around a circle such that the product of any two neighbors is of the form \(x^2 + x + k\) for some positive integer \(x\).

Indices : les idées clés
  • Congruence du second degré modulo un premier : \(x^2 + x + k \equiv 0 \pmod r\) a au plus deux solutions, donc le plus grand premier \(r\) a au plus deux partenaires plus petits.
  • Relations de Viète : les deux solutions vérifient \(x + y \equiv -1 \pmod r\), d'où \(x + y = r - 1\).
  • Identité \((X^2 + K)(Y^2 + K) = (XY - K)^2 + K(X+Y)^2\) (preuve 1) : elle montre que les deux voisins de \(r\) forment eux-mêmes une paire spéciale ; la preuve 2 obtient une formule symétrique en \(p, q, r\).
  • Récurrence sur \(|S|\) : on retire le plus grand premier du cercle.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution, avec deux preuves de l'affirmation clé, et une remarque).

Solution

Autorisons aussi la valeur \(x = 0\) ; nous prouvons l'énoncé sous cette contrainte plus générale, ce qui implique évidemment l'énoncé original.

Appelons spéciale une paire \(\{p, q\}\) de premiers avec \(p \neq q\) si \(pq = x^2 + x + k\) pour un entier \(x \geq 0\). Le mécanisme clé du problème est l'affirmation suivante.

Affirmation. (a) Pour tout premier \(r\), il y a au plus deux premiers inférieurs à \(r\) formant une paire spéciale avec \(r\). (b) Si deux tels premiers \(p\) et \(q\) existent, alors \(\{p, q\}\) est elle-même spéciale.

Nous en donnons deux preuves.

Preuve 1. On s'intéresse aux entiers \(0 \leq x < r\) tels que

\[x^2 + x + k \equiv 0 \pmod r. \tag{1}\]

(Précision ajoutée : si \(pr = x^2 + x + k\) avec \(p < r\), alors \(x^2 < pr < r^2\), donc \(x < r\).) Comme une congruence du second degré modulo le premier \(r\) a au plus deux solutions modulo \(r\), il y a au plus deux valeurs possibles de \(x\), et chacune détermine le premier \(p = (x^2 + x + k)/r\). Cela prouve (a).

Supposons maintenant qu'il existe des premiers \(p < q < r\) et des entiers \(x, y \geq 0\) tels que

\[x^2 + x + k = pr, \qquad y^2 + y + k = qr.\]

De \(p < q < r\) on déduit \(0 \leq x < y \leq r - 1\). Les nombres \(x, y\) sont les deux solutions de (1) ; par les relations de Viète, on doit avoir \(x + y \equiv -1 \pmod r\), donc \(x + y = r - 1\).

Posons \(K = 4k - 1\), \(X = 2x + 1\) et \(Y = 2y + 1\). On obtient

\[4pr = X^2 + K, \qquad 4qr = Y^2 + K,\]

avec \(X + Y = 2r\). En multipliant ces deux égalités,

\[16pqr^2 = (X^2 + K)(Y^2 + K) = (XY - K)^2 + K(X + Y)^2 = (XY - K)^2 + 4Kr^2,\]

d'où

\[4pq = \left(\frac{XY - K}{2r}\right)^2 + K.\]

En particulier, le nombre \(Z = \frac{XY - K}{2r}\) doit être un entier (son carré \(4pq - K\) est entier et c'est un rationnel), et \(4pq = Z^2 + K\). Par parité, \(Z\) est impair, donc

\[pq = z^2 + z + k \quad \text{avec } z = \frac{Z - 1}{2},\]

et \(\{p, q\}\) est spéciale. (Précision : quitte à remplacer \(Z\) par \(-Z\), on peut supposer \(Z > 0\), donc \(z \geq 0\).) \(\square\)

Preuve 2. Comme ci-dessus, supposons

\[x^2 + x + k = pr, \qquad y^2 + y + k = qr.\]

En soustrayant,

\[(x + y + 1)(x - y) = r(p - q).\]

Comme précédemment, \(x + y = r - 1\), donc \(x - y = p - q\), et

\[x = \tfrac{1}{2}(r + p - q - 1), \qquad y = \tfrac{1}{2}(r + q - p - 1).\]

Alors

\[\begin{aligned} k = pr - x^2 - x &= \tfrac{1}{4}\left(4pr - (r + p - q - 1)^2 - 2(r + p - q - 1)\right) \\ &= \tfrac{1}{4}\left(4pr - (r + p - q)^2 + 1\right) \\ &= \tfrac{1}{4}\left(2pq + 2pr + 2qr - p^2 - q^2 - r^2 + 1\right), \end{aligned}\]

expression symétrique en \(p, q, r\). Donc

\[pq = z^2 + z + k \quad \text{avec } z = \tfrac{1}{2}(p + q - r - 1),\]

et \(\{p, q\}\) est spéciale. (Précision ajoutée : \(z\) est entier car \(p, q, r\) sont impairs ; si \(z < 0\), on le remplace par \(-1 - z \geq 0\), ce qui ne change pas \(z^2 + z\).) \(\square\)

Conclusion par récurrence. On raisonne par récurrence sur \(|S|\), le cas \(|S| \leq 3\) étant clair. Supposons le résultat établi pour \(|S| = n\) et considérons \(|S| = n + 1\). Soit \(r\) le plus grand premier de \(S\) ; l'affirmation montre que, dans tout cercle valide :

  • les voisins de \(r\) sont déterminés de manière unique (par (a), ce sont les deux seuls premiers plus petits que \(r\) formant une paire spéciale avec \(r\)) ;
  • retirer \(r\) du cercle donne un cercle valide plus petit (par (b), ses deux voisins forment une paire spéciale et deviennent voisins).

Par hypothèse de récurrence, le cercle réduit est unique, et \(r\) doit être inséré entre ses deux voisins imposés. Il y a donc au plus un cercle valide, ce qui achève la récurrence. \(\blacksquare\)

Remarques

Remarque. L'énoncé n'est pas aussi vide qu'il pourrait sembler. Par exemple, pour \(k = 41\), le livret donne un cercle valide formé de \(385\) nombres premiers, qui commence par \(53, 4357, 104173, 65921, 36383, \ldots\) et se termine par \(\ldots, 19603, 82847, 21851, 61\) (voir la liste complète dans le livret officiel).