Shortlist 2018, N1¶
Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Ukraine
Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs
Solution officielle : Shortlist officielle 2018 (avec solutions), p. 54 (page 56 du PDF)
Énoncé¶
Déterminer tous les couples \((n, k)\) d'entiers strictement positifs distincts pour lesquels il existe un entier \(s\) strictement positif tel que \(sn\) et \(sk\) aient le même nombre de diviseurs.
Énoncé original (anglais)
Determine all pairs \((n, k)\) of distinct positive integers such that there exists a positive integer \(s\) for which the numbers of divisors of \(sn\) and of \(sk\) are equal.
Indices : les idées clés
- Nombre de diviseurs : si \(n = \prod p_i^{\alpha_i}\), alors \(d(n) = \prod (\alpha_i + 1)\) ; on cherche \(s = \prod p_i^{\gamma_i}\) qui rende \(\prod \frac{\alpha_i + \gamma_i + 1}{\beta_i + \gamma_i + 1}\) égal à \(1\).
- Inclusion des ensembles de diviseurs : si \(n \mid k\), les diviseurs de \(sn\) forment une partie stricte de ceux de \(sk\).
- Un lemme d'ajustement : chaque facteur \(\frac{\alpha + \gamma + 1}{\beta + \gamma + 1}\) peut être rendu égal à \(\frac{M+1}{M}\) pour tout \(M\) assez grand.
- Produit télescopique : on choisit les facteurs pour que les produits se simplifient en cascade.
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et une remarque).
Réponse : tous les couples \((n, k)\) tels que \(n \nmid k\) et \(k \nmid n\).
Solution¶
On note \(d(n)\) le nombre de diviseurs de \(n\). Si \(n = \prod_i p_i^{\alpha_i}\) est la décomposition de \(n\) en facteurs premiers, alors \(d(n) = \prod_i (\alpha_i + 1)\) (nombre de diviseurs).
Les couples avec \(n \mid k\) ou \(k \mid n\) ne conviennent pas. Supposons \(n \mid k\) (avec \(n \neq k\)) et soit \(s\) un entier positif quelconque. L'ensemble des diviseurs de \(sn\) est alors une partie stricte de celui de \(sk\), donc \(d(sn) < d(sk)\). Le couple \((n, k)\) ne convient pas. Le cas \(k \mid n\) est analogue.
Les autres couples conviennent. Supposons \(n \nmid k\) et \(k \nmid n\). Soient \(p_1, \ldots, p_t\) tous les nombres premiers divisant \(nk\), et
On cherche \(s\) de la forme \(s = \prod_{i=1}^{t} p_i^{\gamma_i}\), avec des exposants entiers \(\gamma_i \geq 0\) choisis pour que
Si \(\alpha_i = \beta_i\) pour un certain \(i\), le facteur correspondant de (1) vaut \(1\) quel que soit \(\gamma_i\) et n'influe pas sur le produit. On peut donc supposer qu'il n'existe pas de tel indice.
Lemme. Soient \(\alpha > \beta\) deux entiers positifs ou nuls. Pour tout entier \(M \geq \beta + 1\), il existe un entier \(\gamma \geq 0\) tel que
Preuve.
Fin de la preuve. Quitte à renuméroter, il existe un indice \(u\) tel que \(\alpha_i > \beta_i\) pour \(i = 1, \ldots, u\) et \(\alpha_i < \beta_i\) pour \(i = u + 1, \ldots, t\). Les conditions \(n \nmid k\) et \(k \nmid n\) signifient exactement que \(1 \leq u \leq t - 1\).
Soit \(X\) un entier plus grand que tous les \(\alpha_i\) et \(\beta_i\). D'après le lemme, on peut choisir les \(\gamma_i\) de sorte que
et
On a alors, par télescopage,
comme voulu. \(\blacksquare\)
Remarques¶
Remarque. Le lemme peut être utilisé de diverses manières pour obtenir une valeur convenable de \(s\). Par exemple, on peut raisonner par récurrence sur le nombre \(t\) de facteurs premiers, en utilisant des identités comme
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2016 N2 ★☆☆☆☆ : Quelles valeurs entières peut prendre le rapport entre le nombre de diviseurs de \(10n\) et ceux qui sont congrus à \(1\) modulo \(3\) ?
- 2011 N1 ★★☆☆☆ : Le plus petit entier à \(2^k\) diviseurs divise le plus petit entier à \(2^{k+1}\) diviseurs.
- 2006 N3 ★★☆☆☆ : La moyenne \(\frac{1}{n}\sum \lfloor n/k \rfloor\) augmente une infinité de fois et diminue une infinité de fois.
- 2020 N6 ★★★★☆ : Le rapport \(\varphi(d(n)) / d(\varphi(n))\), qui mêle indicatrice d'Euler et nombre de diviseurs, est-il borné ?