Aller au contenu

Shortlist 2012, N1

Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué

Concepts : Divisibilité, PGCD et algorithme d'Euclide

Solution officielle : Shortlist officielle 2012 (avec solutions), p. 42 (page 42 du PDF)

Énoncé

On dit qu'un ensemble \(A\) d'entiers est admissible s'il a la propriété suivante :

si \(x, y \in A\) (éventuellement \(x = y\)), alors \(x^2 + kxy + y^2 \in A\) pour tout entier \(k\).

Déterminer tous les couples \(m, n\) d'entiers non nuls tels que le seul ensemble admissible contenant à la fois \(m\) et \(n\) soit l'ensemble de tous les entiers.

Énoncé original (anglais)

Call admissible a set \(A\) of integers that has the following property:

If \(x, y \in A\) (possibly \(x = y\)) then \(x^2 + kxy + y^2 \in A\) for every integer \(k\).

Determine all pairs \(m, n\) of nonzero integers such that the only admissible set containing both \(m\) and \(n\) is the set of all integers.

Indices : les idées clés
  • Si \(\operatorname{pgcd}(m, n) = d > 1\), les multiples de \(d\) forment un ensemble admissible différent de \(\mathbb{Z}\).
  • Deux règles : \(kx^2 \in A\) pour \(x \in A\) (prendre \(y = x\)), et \((x + y)^2 \in A\) pour \(x, y \in A\) (prendre \(k = 2\)).
  • Bézout : \(am^2 + bn^2 = 1\), donc \(1 = (am^2 + bn^2)^2 \in A\), puis \(k \in A\) pour tout \(k\).
Solutions

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

Réponse : les couples tels que \(\operatorname{pgcd}(m, n) = 1\).

Solution

Un couple d'entiers \(m, n\) convient si et seulement si \(\operatorname{pgcd}(m, n) = 1\). Supposons \(\operatorname{pgcd}(m, n) = d > 1\). L'ensemble

\[A = \{\ldots, -2d, -d, 0, d, 2d, \ldots\}\]

est admissible, car si \(d\) divise \(x\) et \(y\), il divise \(x^2 + kxy + y^2\) pour tout entier \(k\). De plus, \(m, n \in A\) et \(A \neq \mathbb{Z}\).

Soit maintenant \(\operatorname{pgcd}(m, n) = 1\), et \(A\) un ensemble admissible contenant \(m\) et \(n\). On utilise les observations suivantes pour prouver que \(A = \mathbb{Z}\) :

  • (i) \(kx^2 \in A\) pour tout \(x \in A\) et tout entier \(k\) ;
  • (ii) \((x + y)^2 \in A\) pour tous \(x, y \in A\).

Pour (i), on prend \(y = x\) dans la définition d'un ensemble admissible ; pour (ii), on prend \(k = 2\).

Comme \(\operatorname{pgcd}(m, n) = 1\), on a aussi \(\operatorname{pgcd}(m^2, n^2) = 1\). Par Bézout, il existe des entiers \(a\), \(b\) tels que \(am^2 + bn^2 = 1\). Par (i), \(am^2 \in A\) et \(bn^2 \in A\). Par (ii), \(1 = (am^2 + bn^2)^2 \in A\). Mais si \(1 \in A\), alors (i) donne \(k \in A\) pour tout entier \(k\). \(\blacksquare\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2025 N2 ★☆☆☆☆ : Un koala traverse un tableau \(n \times n\) dont la case \((i, j)\) porte \(\gcd(i, j)\) feuilles : combien peut-il en manger au plus ?
  • 2024 N1 ★☆☆☆☆ : Trouver les \(n\) tels que, pour chaque diviseur \(d\), soit \(d + 1\) divise \(n\), soit \(d + 1\) est premier.
  • 2023 N1 ★☆☆☆☆ · OIM P1 : Quels entiers composés ont chaque diviseur qui divise la somme des deux diviseurs suivants ?
  • 2015 N2 ★☆☆☆☆ : Si \(a! + b!\) divise \(a!\,b!\), alors \(3a \geq 2b + 2\).