Aller au contenu

Shortlist 2014, N8

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

Concepts : Valuations p-adiques et lemme LTE · Partie entière et majorations · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 84 (page 85 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

For every real number \(x\), let \(\lVert x \rVert\) denote the distance between \(x\) and the nearest integer. Prove that for every pair \((a, b)\) of positive integers there exist an odd prime \(p\) and a positive integer \(k\) satisfying

\[\left\lVert \frac{a}{p^k} \right\rVert + \left\lVert \frac{b}{p^k} \right\rVert + \left\lVert \frac{a + b}{p^k} \right\rVert = 1. \tag{1}\]
Indices : les idées clés
  • Partie entière : \(\left\lfloor x + \frac{1}{2} \right\rfloor = x \pm \lVert x \rVert\), et une formule de type Legendre : \(v_p\big((2n - 1)!!\big) = \sum_{k \geq 1} \left\lfloor \frac{n}{p^k} + \frac{1}{2} \right\rfloor\).
  • Un nombre bien choisi : \(N = \frac{(2a + 2b - 1)!!}{(2a - 1)!! \, (2b - 1)!!} > 1\) a un diviseur premier \(p\), forcément impair ; une valuation \(v_p(N) > 0\) donne un \(k\) avec \(d_k \geq 1\).
  • Signes : comme \(\lVert x \rVert < \frac{1}{2}\) pour un rationnel à dénominateur impair, \(1 \leq d_k = \pm\lVert \cdot \rVert \pm \lVert \cdot \rVert \pm \lVert \cdot \rVert\) force les trois signes à être \(+\) et \(d_k = 1\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et deux remarques).

Solution

Remarquons d'abord que \(\left\lfloor x + \frac{1}{2} \right\rfloor\) est un entier le plus proche de \(x\), donc \(\lVert x \rVert = \left\lvert \left\lfloor x + \frac{1}{2} \right\rfloor - x \right\rvert\). On a donc

\[\left\lfloor x + \frac{1}{2} \right\rfloor = x \pm \lVert x \rVert. \tag{2}\]

Pour tout rationnel \(r\) et tout nombre premier \(p\), notons \(v_p(r)\) l'exposant de \(p\) dans la décomposition de \(r\). On note \((2n - 1)!!\) le produit de tous les entiers impairs strictement positifs au plus égaux à \(2n - 1\), c'est-à-dire \((2n - 1)!! = 1 \cdot 3 \cdots (2n - 1)\).

Lemme. Pour tout entier \(n \geq 1\) et tout nombre premier impair \(p\),

\[v_p\big((2n - 1)!!\big) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} + \frac{1}{2} \right\rfloor.\]

Preuve. Pour tout entier \(k \geq 1\), comptons les multiples de \(p^k\) parmi les facteurs \(1, 3, \ldots, 2n - 1\). Pour un entier \(\ell\), le nombre \((2\ell - 1)p^k\) est dans la liste si et seulement si

\[0 < (2\ell - 1)p^k \leq 2n \iff \frac{1}{2} < \ell \leq \frac{n}{p^k} + \frac{1}{2} \iff 1 \leq \ell \leq \left\lfloor \frac{n}{p^k} + \frac{1}{2} \right\rfloor.\]

Le nombre de multiples de \(p^k\) parmi les facteurs est donc exactement \(m_k = \left\lfloor \frac{n}{p^k} + \frac{1}{2} \right\rfloor\). On obtient

\[v_p\big((2n - 1)!!\big) = \sum_{i=1}^{n} v_p(2i - 1) = \sum_{i=1}^{n} \sum_{k=1}^{v_p(2i-1)} 1 = \sum_{k=1}^{\infty} \sum_{\ell=1}^{m_k} 1 = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} + \frac{1}{2} \right\rfloor. \qquad \square\]

Pour prouver l'énoncé, considérons le rationnel

\[N = \frac{(2a + 2b - 1)!!}{(2a - 1)!! \cdot (2b - 1)!!} = \frac{(2a + 1)(2a + 3) \cdots (2a + 2b - 1)}{1 \cdot 3 \cdots (2b - 1)}.\]

Clairement \(N > 1\), donc il existe un nombre premier \(p\) tel que \(v_p(N) > 0\). Comme \(N\) est un quotient de deux nombres impairs, \(p\) est impair.

Par le lemme,

\[0 < v_p(N) = \sum_{k=1}^{\infty} \left(\left\lfloor \frac{a + b}{p^k} + \frac{1}{2} \right\rfloor - \left\lfloor \frac{a}{p^k} + \frac{1}{2} \right\rfloor - \left\lfloor \frac{b}{p^k} + \frac{1}{2} \right\rfloor\right).\]

Il existe donc un entier \(k \geq 1\) tel que l'entier

\[d_k = \left\lfloor \frac{a + b}{p^k} + \frac{1}{2} \right\rfloor - \left\lfloor \frac{a}{p^k} + \frac{1}{2} \right\rfloor - \left\lfloor \frac{b}{p^k} + \frac{1}{2} \right\rfloor\]

soit strictement positif, c'est-à-dire \(d_k \geq 1\). Par (2),

\[1 \leq d_k = \frac{a + b}{p^k} - \frac{a}{p^k} - \frac{b}{p^k} \pm \left\lVert \frac{a + b}{p^k} \right\rVert \pm \left\lVert \frac{a}{p^k} \right\rVert \pm \left\lVert \frac{b}{p^k} \right\rVert = \pm \left\lVert \frac{a + b}{p^k} \right\rVert \pm \left\lVert \frac{a}{p^k} \right\rVert \pm \left\lVert \frac{b}{p^k} \right\rVert. \tag{3}\]

Comme \(\lVert x \rVert < \frac{1}{2}\) pour tout rationnel \(x\) à dénominateur impair, la relation (3) n'est possible que si les trois signes du membre de droite sont positifs et \(d_k = 1\). On obtient

\[\left\lVert \frac{a}{p^k} \right\rVert + \left\lVert \frac{b}{p^k} \right\rVert + \left\lVert \frac{a + b}{p^k} \right\rVert = d_k = 1,\]

comme voulu. \(\blacksquare\)

Remarques

Remarque 1. On peut choisir le nombre \(N\) de plusieurs façons. En voici une autre, esquissée.

Soient \(x\) et \(y\) deux rationnels à dénominateurs impairs. On voit facilement que la condition \(\lVert x \rVert + \lVert y \rVert + \lVert x + y \rVert = 1\) est vérifiée si et seulement si

\[\text{soit} \quad \{x\} < \tfrac{1}{2}, \; \{y\} < \tfrac{1}{2}, \; \{x + y\} > \tfrac{1}{2}, \qquad \text{soit} \quad \{x\} > \tfrac{1}{2}, \; \{y\} > \tfrac{1}{2}, \; \{x + y\} < \tfrac{1}{2},\]

où \(\{x\}\) désigne la partie fractionnaire de \(x\).

Dans le contexte du problème, la première condition semble plus maniable. On peut remarquer que

\[\{x\} < \tfrac{1}{2} \iff \kappa(x) = 0 \quad \text{et} \quad \{x\} \geq \tfrac{1}{2} \iff \kappa(x) = 1, \tag{4}\]

où

\[\kappa(x) = \lfloor 2x \rfloor - 2\lfloor x \rfloor.\]

Il est alors naturel de considérer le nombre

\[M = \frac{\binom{2a + 2b}{a + b}}{\binom{2a}{a}\binom{2b}{b}},\]

puisque, par la formule de Legendre (le livret écrit \(\kappa\big(\frac{2(a+b)}{p^k}\big)\) dans le premier terme ; il faut lire \(\kappa\big(\frac{a+b}{p^k}\big)\)),

\[v_p(M) = \sum_{k=1}^{\infty} \left(\kappa\left(\frac{a + b}{p^k}\right) - \kappa\left(\frac{a}{p^k}\right) - \kappa\left(\frac{b}{p^k}\right)\right).\]

On voit que \(M > 1\) et que \(v_2(M) \leq 0\). Il existe donc un nombre premier impair \(p\) et un entier \(k \geq 1\) tels que

\[\kappa\left(\frac{a + b}{p^k}\right) - \kappa\left(\frac{a}{p^k}\right) - \kappa\left(\frac{b}{p^k}\right) > 0.\]

Avec (4), cette inégalité donne

\[\left\{\frac{a}{p^k}\right\} < \frac{1}{2}, \qquad \left\{\frac{b}{p^k}\right\} < \frac{1}{2}, \qquad \left\{\frac{a + b}{p^k}\right\} > \frac{1}{2}, \tag{5}\]

ce que l'on voulait.

Remarque 2. Quand on cherche \(p\) et \(k\) vérifiant (5), il semble naturel de supposer \(a \leq b\) et d'ajouter la contrainte \(p^k > a\). Les inégalités (5) s'écrivent alors

\[2a < p^k, \qquad 2m p^k < 2b < (2m + 1)p^k, \qquad (2m + 1)p^k < 2(a + b) < (2m + 2)p^k\]

pour un entier \(m \geq 1\). Cela signifie exactement que l'un des nombres \(2a + 1, 2a + 3, \ldots, 2a + 2b - 1\) est divisible par un nombre de la forme \(p^k\) supérieur à \(2a\).

Avec des techniques plus avancées, on peut montrer qu'un tel \(p^k\) existe même avec \(k = 1\). C'est un résultat de Laishram et Shorey (2004) ; leurs méthodes sont élémentaires mais assez complexes. Leur résultat généralise un théorème de Sylvester, selon lequel, pour tout couple d'entiers \((n, k)\) avec \(n \geq k \geq 1\), le produit \((n + 1)(n + 2) \cdots (n + k)\) est divisible par un nombre premier \(p > k\). Le théorème de Sylvester lui-même ne semble pas suffire à résoudre le problème.