Shortlist 2015, N2¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : United Kingdom
Concepts : Divisibilité, PGCD et algorithme d'Euclide
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 66 (page 67 du PDF)
Énoncé¶
Let \(a\) and \(b\) be positive integers such that \(a!\,b!\) is a multiple of \(a! + b!\). Prove that \(3a \geq 2b + 2\).
Indices : les idées clés
- Réduction : avec \(c = b - a\) et \(M = (a+1)(a+2)\cdots(a+c)\), l'hypothèse devient \(1 + M \mid a!\).
- PGCD et divisibilité (solution 1) : \(c! \mid M\), donc \(1 + M\) est premier avec \(c!\) et divise \(\frac{a!}{c!}\).
- Comparer des produits : un produit d'au plus \(c\) entiers \(\leq a\) est plus petit que \(M\), produit de \(c\) entiers \(> a\).
- Localiser les facteurs premiers (solution 2) : tout facteur premier de \(N = 1 + M\) est dans \(\left] \frac{a+c}{2}, a \right]\) et y apparaît avec l'exposant \(1\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et deux remarques).
Solution 1¶
Si \(a > b\), on a immédiatement \(3a \geq 2b + 2\). Si \(a = b\), l'inégalité équivaut à \(a \geq 2\), ce qui est vrai car \((a, b) = (1, 1)\) ne vérifie pas \(a! + b! \mid a!\,b!\). On suppose désormais \(a < b\) et l'on pose \(c = b - a\). L'inégalité à prouver devient \(a \geq 2c + 2\).
Supposons par l'absurde que \(a \leq 2c + 1\). Posons
Comme \(a! + b! = a!(1 + M)\) et \(a!\,b! = a! \cdot a!\,M\), l'hypothèse donne \(1 + M \mid a!\,M\), donc \(1 + M \mid a!\) (car \(1 + M\) est premier avec \(M\)). On a nécessairement \(c < a\) : sinon \(M > a^c \geq a!\), donc \(1 + M > a!\), ce qui est impossible. Par ailleurs, \(c! \mid M\) car \(M\) est un produit de \(c\) entiers consécutifs. Donc \(\operatorname{pgcd}(1 + M, c!) = 1\), ce qui entraîne
Si \(a \leq 2c\) : \(\frac{a!}{c!}\) est un produit de \(a - c \leq c\) entiers au plus égaux à \(a\), alors que \(M\) est un produit de \(c\) entiers strictement supérieurs à \(a\). Donc \(1 + M > \frac{a!}{c!}\), ce qui contredit (1).
Si \(a = 2c + 1\) : comme \(a + 1 = 2(c+1)\), on a \(c + 1 \mid M\), donc \(1 + M\) est premier avec \(c + 1\) et (1) donne \(1 + M \mid (c+2)(c+3)\cdots a\). Or ce produit compte \(a - c - 1 = c\) entiers au plus égaux à \(a\) ; il est donc plus petit que \(1 + M\). Contradiction là encore. \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, on peut supposer \(a < b\) et poser \(c = b - a\). Supposons par l'absurde que \(a \leq 2c + 1\). De \(a! + b! \mid a!\,b!\), on déduit
donc tous les facteurs premiers de \(N\) sont au plus égaux à \(a + c\).
Localisation des facteurs premiers. Soit \(p\) un facteur premier de \(N\). Si \(p \leq c\) ou \(p \geq a + 1\), alors \(p\) divise l'un des nombres \(a + 1, \ldots, a + c\) (et donc \(N - 1\)), ce qui est impossible. Donc \(c + 1 \leq p \leq a\). De plus, on a \(2p > a + c\) : sinon \(a + 1 \leq 2c + 2 \leq 2p \leq a + c\), donc \(2p\) est l'un des facteurs \(a+1, \ldots, a+c\) et \(p \mid N - 1\), encore impossible. Ainsi
Par conséquent \(p^2 \nmid N\).
Si \(a \leq c + 2\), l'intervalle \(\left] \frac{a+c}{2}, a \right]\) contient au plus un entier, donc au plus un nombre premier, qui ne peut être que \(a\). Comme \(p^2 \nmid N\), on aurait \(N = p = a\) ou \(N = 1\), ce qui est absurde car \(N > a \geq 1\). Donc \(a \geq c + 3\), d'où \(\frac{a + c + 1}{2} \geq c + 2\) : tout facteur premier \(p\) de \(N\) est dans l'intervalle \([c + 2, a]\).
Ainsi, tout nombre premier de la décomposition de \(N\) est dans \([c + 2, a]\) et y figure avec l'exposant \(1\). Donc \(N \mid (c+2)(c+3)\cdots a\). Mais ce produit compte \(a - c - 1 \leq c\) facteurs au plus égaux à \(a\), donc il est inférieur à \(N\). Contradiction. \(\blacksquare\)
Remarques¶
Remarque 1 (une version plus faible de (1)). On peut se contenter d'une version affaiblie de (1). Si \(a \leq 2c + 1\), alors \(\left\lfloor \frac{a}{2} \right\rfloor \leq c\), donc \(\left\lfloor \frac{a}{2} \right\rfloor! \mid M\), et
Ce produit compte \(\left\lceil \frac{a}{2} \right\rceil\) entiers au plus égaux à \(a\). Si \(a\) est pair, c'est contradictoire car \(\left\lceil \frac{a}{2} \right\rceil = \frac{a}{2} \leq c\) et \(M\) est un produit de \(c\) entiers supérieurs à \(a\). Si \(a\) est impair, on obtient de plus \(1 + M \mid \left(\frac{a+3}{2}\right)\left(\frac{a+5}{2}\right)\cdots a\), car \(\left\lfloor \frac{a}{2} \right\rfloor + 1 = \frac{a+1}{2}\) divise \(a + 1\) (donc \(M\)). Ce produit compte \(\frac{a-1}{2} \leq c\) entiers au plus égaux à \(a\) : contradiction.
Remarque 2. L'énoncé original demandait aussi de déterminer les cas d'égalité \(3a = 2b + 2\). On vérifie que ce sont \((a, b) = (2, 2)\) et \((4, 5)\).