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é

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).

Solution

Réponse : tous les couples \((n, k)\) tels que \(n \nmid k\) et \(k \nmid n\).

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

\[n = \prod_{i=1}^{t} p_i^{\alpha_i}, \qquad k = \prod_{i=1}^{t} p_i^{\beta_i}.\]

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

\[\frac{d(sn)}{d(sk)} = \prod_{i=1}^{t} \frac{\alpha_i + \gamma_i + 1}{\beta_i + \gamma_i + 1} = 1. \tag{1}\]

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

\[\frac{\alpha + \gamma + 1}{\beta + \gamma + 1} = 1 + \frac{1}{M} = \frac{M + 1}{M}.\]

Preuve.

\[\frac{\alpha + \gamma + 1}{\beta + \gamma + 1} = 1 + \frac{1}{M} \iff \frac{\alpha - \beta}{\beta + \gamma + 1} = \frac{1}{M} \iff \gamma = M(\alpha - \beta) - (\beta + 1) \geq 0. \qquad \square\]

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

\[\frac{\alpha_i + \gamma_i + 1}{\beta_i + \gamma_i + 1} = \frac{uX + i}{uX + i - 1} \quad \text{pour } i = 1, 2, \ldots, u,\]

et

\[\frac{\beta_{u+i} + \gamma_{u+i} + 1}{\alpha_{u+i} + \gamma_{u+i} + 1} = \frac{(t-u)X + i}{(t-u)X + i - 1} \quad \text{pour } i = 1, 2, \ldots, t - u.\]

On a alors, par télescopage,

\[\frac{d(sn)}{d(sk)} = \prod_{i=1}^{u} \frac{uX + i}{uX + i - 1} \cdot \prod_{i=1}^{t-u} \frac{(t-u)X + i - 1}{(t-u)X + i} = \frac{u(X+1)}{uX} \cdot \frac{(t-u)X}{(t-u)(X+1)} = 1,\]

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

\[\frac{n}{n-1} = \frac{n^2}{n^2 - 1} \cdot \frac{n + 1}{n}.\]