Shortlist 2016, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 75 (page 78 du PDF)
Problème 4 de l'OIM 2016
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2016, où il était le problème 4 (jour 2).
Énoncé¶
Define \(P(n) = n^2 + n + 1\). For any positive integers \(a\) and \(b\), the set
is said to be fragrant if none of its elements is relatively prime to the product of the other elements. Determine the smallest size of a fragrant set.
Indices : les idées clés
- PGCD par combinaisons linéaires : des identités comme \((2n+7)P(n) - (2n-1)P(n+2) = 14\) bornent \(\gcd(P(n), P(n+k))\) pour \(k = 1, 2, 3\).
- Congruences : on détermine exactement quand ces PGCD sont \(> 1\) en testant les résidus modulo \(7\) et modulo \(3\).
- Impossibilité pour \(5\) éléments : l'élément central est premier avec ses deux voisins, ce qui force des conditions incompatibles modulo \(3\).
- Théorème des restes chinois : il construit un ensemble parfumé de taille \(6\), en combinant des conditions modulo \(19\), \(7\) et \(3\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2016 (une solution et une remarque).
Réponse. \(6\).
Solution¶
Notons \((u, v)\) le PGCD de \(u\) et \(v\). On a les observations suivantes.
(i) \((P(n), P(n+1)) = 1\) pour tout \(n\). En effet,
Comme \(n^2 + n + 1\) est impair et que \((n^2 + n + 1, n + 1) = (1, n + 1) = 1\) (car \(n^2 + n + 1 = n(n+1) + 1\)), l'affirmation suit.
(ii) \((P(n), P(n+2)) = 1\) si \(n \not\equiv 2 \pmod 7\), et \((P(n), P(n+2)) = 7\) si \(n \equiv 2 \pmod 7\). On a
et \(P(n)\) est impair, donc \((P(n), P(n+2))\) divise \(7\). On conclut en examinant directement \(n \equiv 0, 1, \ldots, 6 \pmod 7\).
(iii) \((P(n), P(n+3)) = 1\) si \(n \not\equiv 1 \pmod 3\), et \(3 \mid (P(n), P(n+3))\) si \(n \equiv 1 \pmod 3\). On a
et \(P(n)\) est impair, donc \((P(n), P(n+3))\) divise \(9\). On conclut en examinant directement \(n \equiv 0, 1, 2 \pmod 3\).
Pas d'ensemble parfumé à \(5\) éléments ou moins. Supposons qu'il existe un ensemble parfumé d'au plus \(5\) éléments. On peut supposer qu'il en a exactement \(5\), \(P(a), P(a+1), \ldots, P(a+4)\), car l'argument suivant fonctionne aussi avec moins d'éléments. Considérons \(P(a+2)\). D'après (i), il est premier avec \(P(a+1)\) et \(P(a+3)\). Par symétrie, on peut supposer \((P(a), P(a+2)) > 1\). D'après (ii), \(a \equiv 2 \pmod 7\). La même observation montre alors que \((P(a+1), P(a+3)) = 1\) (car \(a + 1 \not\equiv 2 \pmod 7\)). Pour que l'ensemble soit parfumé, \(P(a+1)\) (premier avec \(P(a)\), \(P(a+2)\) et \(P(a+3)\)) doit avoir un facteur commun avec \(P(a+4)\), et \(P(a+3)\) (premier avec \(P(a+1)\), \(P(a+2)\), \(P(a+4)\)) doit avoir un facteur commun avec \(P(a)\) : il faut donc \((P(a), P(a+3)) > 1\) et \((P(a+1), P(a+4)) > 1\). D'après (iii), cela n'arrive que si \(a\) et \(a + 1\) sont tous deux congrus à \(1\) modulo \(3\), ce qui est absurde.
Un ensemble parfumé à \(6\) éléments. Par le théorème des restes chinois, on peut choisir un entier \(a > 0\) tel que
Par exemple, \(a = 197\) convient. D'après (ii), \(P(a+1)\) et \(P(a+3)\) sont divisibles par \(7\). D'après (iii), \(P(a+2)\) et \(P(a+5)\) sont divisibles par \(3\). Enfin, comme \(19 \mid P(7) = 57\) et \(19 \mid P(11) = 133\), et que \(a \equiv 7\), \(a + 4 \equiv 11 \pmod{19}\), les nombres \(P(a)\) et \(P(a+4)\) sont divisibles par \(19\). L'ensemble \(\{P(a), P(a+1), \ldots, P(a+5)\}\) est donc parfumé.
La plus petite taille d'un ensemble parfumé est donc \(6\). \(\blacksquare\)
Remarques¶
Remarque 1. « Fragrant Harbour » (« port parfumé ») est la traduction anglaise de « Hong Kong ».
Remarque 2 (version renforcée). Il existe un ensemble parfumé de taille \(k\) pour tout \(k \geq 6\). Pour tout entier pair \(m\) non divisible par \(3\), on a \(m^2 + 3 \equiv 3 \pmod 4\), donc on peut trouver un nombre premier \(p_m \equiv 3 \pmod 4\) divisant \(m^2 + 3\) ; clairement \(p_m > 3\).
-
Si \(b = 2t \geq 6\), on choisit \(a\) tel que \(3 \mid 2(a + t) + 1\) et \(p_m \mid 2(a + t) + 1\) pour chaque \(1 \leq m \leq b\) avec \(m \equiv 2, 4 \pmod 6\). Pour \(0 \leq r \leq t\) avec \(3 \mid r\), on a \(a + t \pm r \equiv 1 \pmod 3\), donc \(3 \mid P(a + t \pm r)\). Pour \(0 \leq r \leq t\) avec \((r, 3) = 1\),
\[4P(a + t \pm r) \equiv (-1 \pm 2r)^2 + 2(-1 \pm 2r) + 4 = 4r^2 + 3 \equiv 0 \pmod{p_{2r}}.\]Donc \(\{P(a), P(a+1), \ldots, P(a+b)\}\) est parfumé.
-
Si \(b = 2t + 1 \geq 7\) (le cas \(b = 5\) est celui du problème), on choisit \(a\) comme ci-dessus et, en plus, \(a + b \equiv 9 \pmod{13}\) ; un tel \(a\) existe par le théorème des restes chinois car \(p_m \neq 13\) pour tout \(m\). Le cas pair montre que \(\{P(a), \ldots, P(a+b-1)\}\) est parfumé ; de plus, comme \(13 \mid P(9) = 91\) et \(13 \mid P(3) = 13\), les nombres \(P(a+b)\) et \(P(a+b-6)\) sont divisibles par \(13\).