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é

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

Solution

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

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