Aller au contenu

Shortlist 2008, N2

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

Solution officielle : Shortlist officielle 2008 (avec solutions), p. 45 (page 46 du PDF)

Énoncé

Let \(a_1, a_2, \ldots, a_n\) be distinct positive integers, \(n \geq 3\). Prove that there exist distinct indices \(i\) and \(j\) such that \(a_i + a_j\) does not divide any of the numbers \(3a_1, 3a_2, \ldots, 3a_n\).

Indices : les idées clés
  • Normalisation : \(a_1 < \cdots < a_n\) premiers entre eux dans leur ensemble ; une somme \(a_n + a_i\) non divisible par \(3\) ne peut diviser aucun \(a_j \leq a_n\).
  • Résidus modulo \(3\) : par l'absurde, tous les \(a_i\) (\(i < n\)) sont congrus à \(-a_n\), et \(a_n \not\equiv 0\) ; alors \(a_{n-1} + a_i \not\equiv 0\), d'où \(a_{n-1} + a_i \mid a_n\).
  • Conclusion : on obtient \(a_n = 2a_{n-1}\), puis \(a_{n-1} + a_1\) strictement entre \(a_n/2\) et \(a_n\) divise \(a_n\), contradiction.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2008 (une solution).

Solution

Sans perte de généralité, soit \(0 < a_1 < a_2 < \cdots < a_n\). On peut aussi supposer que \(a_1, a_2, \ldots, a_n\) sont premiers entre eux dans leur ensemble. Sinon, la division par leur plus grand diviseur commun ramène la question à la nouvelle suite, dont les termes sont premiers entre eux.

Supposons l'affirmation fausse. Alors, pour chaque \(i < n\), il existe un \(j\) tel que \(a_n + a_i\) divise \(3a_j\). Si \(a_n + a_i\) n'est pas divisible par \(3\), alors \(a_n + a_i\) divise \(a_j\), ce qui est impossible puisque \(0 < a_j \leq a_n < a_n + a_i\). Donc \(a_n + a_i\) est un multiple de \(3\) pour \(i = 1, \ldots, n - 1\), de sorte que \(a_1, a_2, \ldots, a_{n-1}\) sont tous congrus (à \(-a_n\)) modulo \(3\).

Maintenant, \(a_n\) n'est pas divisible par \(3\), sinon tous les autres \(a_i\) le seraient aussi, ce qui signifierait que \(a_1, a_2, \ldots, a_n\) ne sont pas premiers entre eux. Donc \(a_n \equiv r \pmod 3\) avec \(r \in \{1, 2\}\), et \(a_i \equiv 3 - r \pmod 3\) pour tout \(i = 1, \ldots, n - 1\).

Considérons une somme \(a_{n-1} + a_i\) avec \(1 \leq i \leq n - 2\). Il en existe au moins une, puisque \(n \geq 3\). Soit \(j\) un indice tel que \(a_{n-1} + a_i\) divise \(3a_j\). Remarquons que \(a_{n-1} + a_i\) n'est pas divisible par \(3\), puisque \(a_{n-1} + a_i \equiv 2a_i \not\equiv 0 \pmod 3\). Il s'ensuit que \(a_{n-1} + a_i\) divise \(a_j\), en particulier \(a_{n-1} + a_i \leq a_j\). Donc \(a_{n-1} < a_j \leq a_n\), ce qui implique \(j = n\). Ainsi \(a_n\) est divisible par toutes les sommes \(a_{n-1} + a_i\), \(1 \leq i \leq n - 2\). En particulier, \(a_{n-1} + a_i \leq a_n\) pour \(i = 1, \ldots, n - 2\).

Soit \(j\) tel que \(a_n + a_{n-1}\) divise \(3a_j\). Si \(j \leq n - 2\), alors \(a_n + a_{n-1} \leq 3a_j < a_j + 2a_{n-1}\). Cela donne \(a_n < a_{n-1} + a_j\) ; or \(a_{n-1} + a_j \leq a_n\) pour \(j \leq n - 2\). Donc \(j = n - 1\) ou \(j = n\).

Pour \(j = n - 1\), on obtient \(3a_{n-1} = k(a_n + a_{n-1})\) avec \(k\) entier, et l'on voit directement que \(k = 1\) (\(k \leq 0\) et \(k \geq 3\) contredisent \(0 < a_{n-1} < a_n\) ; \(k = 2\) mène à \(a_{n-1} = 2a_n > a_{n-1}\)). Donc \(3a_{n-1} = a_n + a_{n-1}\), c'est-à-dire \(a_n = 2a_{n-1}\).

De même, si \(j = n\), alors \(3a_n = k(a_n + a_{n-1})\) pour un certain entier \(k\), et seul \(k = 2\) est possible. Donc \(a_n = 2a_{n-1}\) dans les deux cas restants, \(j = n - 1\) et \(j = n\).

Or \(a_n = 2a_{n-1}\) implique que la somme \(a_{n-1} + a_1\) est strictement comprise entre \(a_n/2\) et \(a_n\). Mais \(a_{n-1}\) et \(a_1\) sont distincts puisque \(n \geq 3\), donc, d'après ce qui précède, \(a_{n-1} + a_1\) divise \(a_n\). Cela fournit la contradiction voulue. \(\blacksquare\)