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)

Énoncé

Pour tout nombre réel \(x\), on note \(\lVert x \rVert\) la distance de \(x\) à l'entier le plus proche. Montrer que, pour tout couple \((a, b)\) d'entiers strictement positifs, il existe un nombre premier impair \(p\) et un entier \(k\) strictement positif vérifiant

\[\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}\]
Énoncé original (anglais)

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)\), \(\kappa\big(\frac{2a}{p^k}\big)\) et \(\kappa\big(\frac{2b}{p^k}\big)\), ici et dans l'inégalité suivante ; il faut lire \(\kappa\big(\frac{a+b}{p^k}\big)\), \(\kappa\big(\frac{a}{p^k}\big)\) et \(\kappa\big(\frac{b}{p^k}\big)\), car \(v_p\binom{2n}{n} = \sum_k \kappa(n/p^k)\)),

\[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.

Problèmes voisins

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

  • 2023 N3 ★★☆☆☆ : Dans \(n!\), la plus grande puissance de \(10\) dépasse parfois celle de \(9\), et parfois non, une infinité de fois chacune.
  • 2016 N7 ★★★★☆ · OIM P3 : Un polygone inscriptible à sommets entiers dont les carrés des côtés sont divisibles par \(n\) : son aire double est divisible par \(n\).
  • 2010 N6 ★★★★☆ : Un coloriage d'un tableau \(2^n \times 2^n\) invariant par une règle de transfert entre lignes utilise au plus \(2^n\) couleurs.
  • 2018 N7 ★★★★★ : Des fractions à numérateurs et dénominateurs distincts au plus \(5n\) en progression arithmétique sont toutes égales.