Aller au contenu

Shortlist 2020, N2

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

Concepts : Graphes : degrés, chemins, arbres · Résidus quadratiques · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 72 (page 74 du PDF)

Énoncé

For each prime \(p\), there is a kingdom of \(p\)-Landia consisting of \(p\) islands numbered \(1, 2, \ldots, p\). Two distinct islands numbered \(n\) and \(m\) are connected by a bridge if and only if \(p\) divides \((n^2 - m + 1)(m^2 - n + 1)\). The bridges may pass over each other, but cannot cross. Prove that for infinitely many \(p\) there are two islands in \(p\)-Landia not connected by a chain of bridges.

Indices : les idées clés
  • Flèches \(m \to m^2 + 1\) : chaque pont correspond à au moins une flèche, et chaque île émet au plus une flèche ; on compte les ponts via les flèches.
  • Graphes (solution 1) : si \(x^2 - x + 1 \equiv 0 \pmod p\), les îles \(x\) et \(p + 1 - x\) n'émettent aucune flèche, donc il y a au plus \(p - 2\) ponts, trop peu pour relier \(p\) îles.
  • Infinité de nombres premiers à la Euclide : \((p_1 \cdots p_k)^2 - p_1 \cdots p_k + 1\) fournit un nouveau premier divisant un nombre de la forme \(x^2 - x + 1\).
  • Résidus quadratiques (solution 2) : si \(3\) n'est pas un résidu quadratique modulo \(p\), une paire d'îles est isolée du reste ; cela arrive pour \(p \equiv -1 \pmod 4\).
Solutions

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

Dans les deux solutions, on dit simplement qu'un pont « relie » \(m\) et \(n\). Un pont relie \(m\) et \(n\) si et seulement si \(n \equiv m^2 + 1 \pmod p\) ou \(m \equiv n^2 + 1 \pmod p\). Si \(m^2 + 1 \equiv n \pmod p\), on dessine une flèche partant de \(m\) sur le pont qui relie \(m\) et \(n\). Il part exactement une flèche de \(m\) si \(m^2 + 1 \not\equiv m \pmod p\), et aucune sinon. Le nombre total de ponts ne dépasse pas le nombre total de flèches.

Solution 1

Montrons que pour tout premier \(p > 3\) divisant un nombre de la forme \(x^2 - x + 1\) (\(x\) entier), il y a deux îles non reliées dans \(p\)-Landia.

Supposons \(x^2 - x + 1 \equiv 0 \pmod p\) ; on peut supposer \(1 \leq x \leq p\). Alors \(x^2 + 1 \equiv x\), donc aucune flèche ne part de \(x\). Comme \((1 - x)^2 - (1 - x) + 1 = x^2 - x + 1\), on a \((p + 1 - x)^2 + 1 \equiv p + 1 - x \pmod p\), et aucune flèche ne part non plus de \(p + 1 - x\). Si l'on avait \(x = p + 1 - x\), c'est-à-dire \(x = \frac{p+1}{2}\), alors \(4(x^2 - x + 1) = p^2 + 3\), qui n'est pas divisible par \(p\) (car \(p > 3\)) : contradiction. Les îles \(x\) et \(p + 1 - x\) sont donc différentes, et aucune flèche ne part d'elles. Il s'ensuit que le nombre total de ponts de \(p\)-Landia ne dépasse pas \(p - 2\).

Considérons le graphe \(G_p\) de sommets \(1, 2, \ldots, p\), où une arête relie \(m\) et \(n\) si et seulement s'il y a un pont entre \(m\) et \(n\). Il a \(p\) sommets et moins de \(p - 1\) arêtes ; un graphe connexe à \(p\) sommets ayant au moins \(p - 1\) arêtes, \(G_p\) n'est pas connexe : il existe deux îles non reliées par une chaîne de ponts.

Il reste à montrer qu'il existe une infinité de premiers \(p > 3\) divisant \(x^2 - x + 1\) pour un certain entier \(x\). Soit \(p_1, p_2, \ldots, p_k\) une famille finie de tels premiers (on peut y inclure \(3\), qui divise \(2^2 - 2 + 1\)). Le nombre \((p_1p_2\cdots p_k)^2 - p_1p_2\cdots p_k + 1\) est supérieur à \(1\) et n'est divisible par aucun des \(p_i\) ; il a donc un autre diviseur premier, qui a la propriété voulue. \(\blacksquare\)

Solution 2

On peut montrer, par des méthodes purement arithmétiques, que pour une infinité de \(p\), le royaume de \(p\)-Landia contient deux îles qui ne sont reliées à aucune autre île, sinon entre elles.

Les flèches ont le même sens que dans la solution précédente. Supposons qu'un entier positif \(a < p\) vérifie \(a^2 - a + 1 \equiv 0 \pmod p\). On a vu dans la solution 1 que \(b = p + 1 - a\) la vérifie aussi, et que \(b \neq a\) lorsque \(p > 3\). Il s'ensuit que \(ab \equiv a(1 - a) \equiv 1 \pmod p\).

Si une flèche va de \(t\) vers \(a\), alors \(t\) vérifie la congruence \(t^2 + 1 \equiv a \equiv a^2 + 1 \pmod p\) ; le seul tel \(t \neq a\) est \(p - a\). De même, la seule flèche qui puisse arriver en \(b\) part de \(p - b\). Si l'un des nombres \(p - a\), \(p - b\), disons \(p - a\), n'est l'extrémité d'aucune flèche, alors la paire \(\{a, p - a\}\) n'est pas reliée au reste des îles (aucune flèche ne part de \(a\), la seule flèche liée à \(a\) vient de \(p - a\), et la flèche partant de \(p - a\) va en \(a\)). C'est le cas si au moins une des congruences \(x^2 + 1 \equiv -a\), \(x^2 + 1 \equiv -b\) n'a pas de solution, c'est-à-dire si \(-a - 1\) ou \(-b - 1\) n'est pas un résidu quadratique modulo \(p\).

Or \(x^2 - x + 1 \equiv x^2 - (a + b)x + ab \equiv (x - a)(x - b) \pmod p\). En substituant \(x = -1\), on obtient \((-1 - a)(-1 - b) \equiv 3 \pmod p\). Si \(3\) n'est pas un résidu quadratique modulo \(p\), alors l'un des nombres \(-1 - a\) et \(-1 - b\) ne l'est pas non plus.

Il suffit donc de trouver une infinité de premiers \(p > 3\) divisant \(x^2 - x + 1\) pour un certain entier \(x\) et tels que \(3\) ne soit pas un résidu quadratique modulo \(p\).

Si \(x^2 - x + 1 \equiv 0 \pmod p\), alors \((2x - 1)^2 \equiv -3 \pmod p\) : \(-3\) est un résidu quadratique modulo \(p\). Donc \(3\) n'est pas un résidu quadratique si et seulement si \(-1\) n'en est pas un, c'est-à-dire si et seulement si \(p \equiv -1 \pmod 4\).

Comme dans la première solution, soient \(p_1, \ldots, p_k\) des premiers congrus à \(-1\) modulo \(4\) divisant des nombres de la forme \(x^2 - x + 1\) (on peut y inclure \(3\)). Le nombre \((2p_1\cdots p_k)^2 - 2p_1\cdots p_k + 1\) n'est divisible par aucun \(p_i\) et est congru à \(-1\) modulo \(4\) ; il a donc un diviseur premier \(p \equiv -1 \pmod 4\), qui a les propriétés voulues. \(\blacksquare\)

Note : la précision « on peut y inclure \(3\) » (dans les deux solutions) n'est pas dans le livret ; elle garantit que le nouveau premier obtenu est bien supérieur à \(3\).