Aller au contenu

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

\[r_ir_{i+1}r_{i+2}r_{i+3} = i \qquad \text{pour } 1 \leq i \leq k.\]

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\),

\[iv_iv_{i+1}v_{i+2}v_{i+3} = r_iv_i \cdot r_{i+1}v_{i+1} \cdot r_{i+2}v_{i+2} \cdot r_{i+3}v_{i+3} = u_iu_{i+1}u_{i+2}u_{i+3} \equiv a_iv_ia_{i+1}v_{i+1}a_{i+2}v_{i+2}a_{i+3}v_{i+3} \pmod p,\]

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}\),

\[b_{i+3} = i(i - 4)(i - 8)\cdots(i - 4m + 4)\,b_r, \qquad \text{où } i + 3 = 4m + r,\ 0 \leq r < 4.\]

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\).