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é¶
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.