Shortlist 2020, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : South Africa
Concepts : Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 70 (page 72 du PDF)
Énoncé¶
Soit \(k\) un entier strictement positif. Montrer qu'il existe un nombre premier \(p\) pour lequel on peut choisir des entiers distincts \(a_1, a_2, \ldots, a_{k+3} \in \{1, 2, \ldots, p - 1\}\) tels que \(p\) divise \(a_i a_{i+1} a_{i+2} a_{i+3} - i\) pour tout \(i = 1, 2, \ldots, k\).
Énoncé original (anglais)
Given a positive integer \(k\), show that there exists a prime \(p\) such that one can choose distinct integers \(a_1, a_2, \ldots, a_{k+3} \in \{1, 2, \ldots, p - 1\}\) such that \(p\) divides \(a_i a_{i+1} a_{i+2} a_{i+3} - i\) for all \(i = 1, 2, \ldots, k\).
Indices : les idées clés
- Résoudre d'abord dans les rationnels : on construit des rationnels positifs distincts \(r_1, \ldots, r_{k+3}\) avec \(r_ir_{i+1}r_{i+2}r_{i+3} = i\) exactement.
- Distinguer les termes grâce à trois grands nombres premiers \(x, y, z\) : chaque classe d'indices modulo \(4\) a sa « signature » de divisibilité, et chaque classe est strictement croissante.
- Congruences : on choisit un premier \(p\) qui ne divise aucun des dénominateurs ni aucune des différences, puis on réduit les fractions modulo \(p\) (\(a_iv_i \equiv u_i\)).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2020 (une solution et une remarque).
Solution¶
Étape 1 : des rationnels. Choisissons d'abord des rationnels positifs distincts \(r_1, \ldots, r_{k+3}\) tels que
Prenons \(r_1 = x\), \(r_2 = y\), \(r_3 = z\), trois nombres premiers distincts supérieurs à \(k\) ; les autres termes sont alors déterminés : \(r_4 = \frac{1}{r_1r_2r_3}\) et \(r_{i+4} = \frac{i+1}{i}r_i\) (en divisant la relation au rang \(i+1\) par celle au rang \(i\)). Il en découle que, si l'on écrit les \(r_i\) sous forme de fractions irréductibles, les numérateurs sont divisibles par \(x\) pour \(i \equiv 1 \pmod 4\), par \(y\) pour \(i \equiv 2 \pmod 4\), par \(z\) pour \(i \equiv 3 \pmod 4\), et par aucun d'eux pour \(i \equiv 0 \pmod 4\) (les facteurs \(\frac{i+1}{i}\) ne font intervenir que des entiers au plus \(k+1\), non divisibles par \(x, y, z\)). Remarquons aussi que \(r_i < r_{i+4}\) ; ainsi les suites \(r_1 < r_5 < r_9 < \cdots\), \(r_2 < r_6 < r_{10} < \cdots\), \(r_3 < r_7 < r_{11} < \cdots\), \(r_4 < r_8 < r_{12} < \cdots\) sont croissantes et n'ont aucun terme commun : tous les \(r_i\) sont distincts.
Étape 2 : réduction modulo \(p\). Écrivons chaque \(r_i\) sous forme irréductible \(\frac{u_i}{v_i}\), et choisissons un nombre premier \(p\) qui ne divise ni les \(v_i\) (\(1 \leq i \leq k + 3\)), ni les entiers non nuls \(v_iv_j(r_i - r_j) = v_ju_i - v_iu_j\) pour \(i < j\). Définissons \(a_i \in \{1, \ldots, p - 1\}\) par la congruence \(a_iv_i \equiv u_i \pmod p\) (possible car \(v_i\) est inversible modulo \(p\) ; précision ajoutée : en choisissant aussi \(p\) ne divisant aucun \(u_i\), ce qui n'exclut qu'un nombre fini de premiers, on a bien \(a_i \not\equiv 0\)). Puisque \(r_ir_{i+1}r_{i+2}r_{i+3} = i\),
et donc, en simplifiant par les \(v\) inversibles, \(a_ia_{i+1}a_{i+2}a_{i+3} \equiv i \pmod p\) pour \(1 \leq i \leq k\).
Étape 3 : les \(a_i\) sont distincts. Si \(a_i \equiv a_j \pmod p\) avec \(i < j\), alors \(u_iv_j \equiv a_iv_iv_j \equiv u_jv_i \pmod p\), ce qui contredit le choix de \(p\). \(\blacksquare\)
Remarques¶
Remarque 1. On peut exprimer explicitement les résidus \(b_i \equiv a_1a_2\cdots a_i \pmod p\) en fonction de \(b_1, b_2, b_3\) et \(b_0 = 1\) : comme \(b_{i+3} \equiv i\,b_{i-1}\),
On trouve ensuite les \(a_i\) par les congruences \(b_{i-1}a_i \equiv b_i \pmod p\), et l'on choisit \(p\) pour que les \(a_i\) soient deux à deux non congrus modulo \(p\), d'une manière très semblable à la solution ci-dessus.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N1 ★☆☆☆☆ : Si \(k\) puissances de \(2\), avec \(n < k < 2n\), ont une somme divisible par \(2^n - 1\), trois exposants sont congrus modulo \(n\).
- 2022 N2 ★☆☆☆☆ : Pour quels \(n\) le produit des sommes \(p + q\) de premiers distincts au plus \(n\) est-il divisible par \(n!\) ?
- 2021 N1 ★☆☆☆☆ : Pour quels \(n\) la fraction \((ab + 3b + 8)/(a^2 + b + 3)\) vaut-elle \(n\), avec un dénominateur sans facteur cube ?
- 2018 N2 ★☆☆☆☆ : Un tableau d'entiers congrus à \(1\) modulo \(n\) : les sommes des produits des lignes et des colonnes sont congrues modulo \(n^4\).