Aller au contenu

Shortlist 2015, N3

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

Concepts : Valuations p-adiques et lemme LTE · Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2015 (avec solutions), p. 67 (page 68 du PDF)

Énoncé

Let \(m\) and \(n\) be positive integers such that \(m > n\). Define \(x_k = \frac{m+k}{n+k}\) for \(k = 1, 2, \ldots, n+1\). Prove that if all the numbers \(x_1, x_2, \ldots, x_{n+1}\) are integers, then \(x_1 x_2 \cdots x_{n+1} - 1\) is divisible by an odd prime.

Indices : les idées clés
  • Valuations 2-adiques : montrer que \(P = x_1 \cdots x_{n+1} - 1\) n'est pas une puissance de \(2\) en étudiant la plus grande puissance de \(2\) qui divise chaque \(a_k = x_k - 1\).
  • Divisibilité : \(m - n\) est divisible par tous les \(n + k\), en particulier par l'unique multiple de \(2^c\) parmi \(n+1, \ldots, 2n+1\).
  • Congruences : modulo \(2^{d-c+1}\), un seul facteur \(a_\ell + 1\) n'est pas congru à \(1\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et une remarque).

Solution

Supposons que \(x_1, \ldots, x_{n+1}\) sont des entiers. Posons, pour \(k = 1, 2, \ldots, n+1\),

\[a_k = x_k - 1 = \frac{m + k}{n + k} - 1 = \frac{m - n}{n + k} > 0,\]

qui sont des entiers. Soit \(P = x_1 x_2 \cdots x_{n+1} - 1\). Il faut montrer que \(P\) est divisible par un nombre premier impair, autrement dit que \(P\) n'est pas une puissance de \(2\). Pour cela, on étudie les puissances de \(2\) qui divisent les \(a_k\).

Soit \(2^d\) la plus grande puissance de \(2\) qui divise \(m - n\), et \(2^c\) la plus grande puissance de \(2\) inférieure ou égale à \(2n + 1\). Alors \(2n + 1 \leq 2^{c+1} - 1\), donc \(n + 1 \leq 2^c\). Ainsi \(2^c\) est l'un des nombres \(n+1, n+2, \ldots, 2n+1\), et c'est le seul multiple de \(2^c\) parmi eux. Soit \(\ell\) tel que \(n + \ell = 2^c\). Comme \(\frac{m-n}{n+\ell}\) est entier, \(d \geq c\). Par conséquent (valuations 2-adiques)

\[2^{d-c+1} \nmid a_\ell = \frac{m - n}{n + \ell}, \qquad \text{tandis que} \qquad 2^{d-c+1} \mid a_k \ \text{ pour tout } k \in \{1, \ldots, n+1\} \setminus \{\ell\},\]

car pour \(k \neq \ell\), \(n + k\) n'est pas divisible par \(2^c\).

En calculant modulo \(2^{d-c+1}\) :

\[P = (a_1 + 1)(a_2 + 1) \cdots (a_{n+1} + 1) - 1 \equiv (a_\ell + 1) \cdot 1^n - 1 \equiv a_\ell \not\equiv 0 \pmod{2^{d-c+1}}.\]

Donc \(2^{d-c+1} \nmid P\).

D'autre part, pour \(k \in \{1, \ldots, n+1\} \setminus \{\ell\}\) (un tel \(k\) existe car \(n + 1 \geq 2\)), on a \(2^{d-c+1} \mid a_k\), donc \(P \geq a_k \geq 2^{d-c+1}\). Une puissance de \(2\) supérieure ou égale à \(2^{d-c+1}\) serait divisible par \(2^{d-c+1}\) ; donc \(P\) n'est pas une puissance de \(2\), et il est divisible par un nombre premier impair. \(\blacksquare\)

Remarques

Remarque (trouver directement un facteur impair). Comme \(a_k = \frac{m-n}{n+k}\) est entier, \(m - n\) est divisible par \(n+1, n+2, \ldots, 2n+1\), donc par leur PPCM \(L\). Ainsi \(m - n = qL\) avec \(q\) entier positif, et \(x_k = q \cdot \frac{L}{n+k} + 1\). Puisque \(n + 1 \leq 2^c = n + \ell \leq 2n + 1 \leq 2^{c+1} - 1\), on a \(2^c \mid L\) mais \(2^{c+1} \nmid L\). Donc \(\frac{L}{n+\ell}\) est impair, tandis que \(\frac{L}{n+k}\) est pair pour \(k \neq \ell\). Modulo \(2q\) :

\[x_1 x_2 \cdots x_{n+1} - 1 \equiv (q + 1) \cdot 1^n - 1 \equiv q \pmod{2q}.\]

Donc \(x_1 x_2 \cdots x_{n+1} - 1 = 2qr + q = q(2r + 1)\) pour un entier \(r\). Comme \(x_1 x_2 \cdots x_{n+1} - 1 \geq x_1 x_2 - 1 \geq (q+1)^2 - 1 > q\), on a \(r \geq 1\), et \(2r + 1 > 1\) est un facteur impair.