Aller au contenu

Shortlist 2016, N2

Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué

Concepts : Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs · Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 73 (page 76 du PDF)

Énoncé

Let \(\tau(n)\) be the number of positive divisors of \(n\). Let \(\tau_1(n)\) be the number of positive divisors of \(n\) which have remainders \(1\) when divided by \(3\). Find all possible integral values of the fraction \(\dfrac{\tau(10n)}{\tau_1(10n)}\).

Indices : les idées clés
  • Nombre de diviseurs : \(\tau\) se calcule à partir des exposants de la décomposition en facteurs premiers ; on obtient de même une formule pour \(\tau_1\).
  • Congruences modulo 3 : un diviseur est \(\equiv 1 \pmod 3\) si et seulement s'il n'est pas divisible par \(3\) et contient un nombre pair de facteurs premiers \(\equiv 2 \pmod 3\) (comptés avec multiplicité).
  • Discussion de parité : selon la parité de \(c = (y+2)(z+2)\prod (b_j + 1)\), le quotient vaut \(2(x+1)\) ou \(\frac{2(x+1)c}{c+1}\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2016 (une solution).

Réponse. Les nombres composés, ainsi que \(2\).

Solution

Dans toute la solution, les \(p_i\) désignent des nombres premiers congrus à \(1\) modulo \(3\), et les \(q_j\) des nombres premiers congrus à \(2\) modulo \(3\). Dans les décompositions en facteurs premiers, on autorise des exposants nuls (ce qui inclut le cas \(m = 1\)). Calculons d'abord \(\tau_1(m)\).

Affirmation. Si \(m = 3^x p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s} q_1^{b_1} q_2^{b_2} \cdots q_t^{b_t}\), alors

\[\tau_1(m) = \prod_{i=1}^{s} (a_i + 1) \left\lceil \frac{1}{2} \prod_{j=1}^{t} (b_j + 1) \right\rceil. \tag{1}\]

Preuve. Un diviseur de \(m\) congru à \(1\) modulo \(3\) ne peut pas contenir le facteur \(3\) ; il n'y a aucune contrainte sur les facteurs premiers congrus à \(1\) modulo \(3\) ; enfin, il doit contenir un nombre pair de facteurs premiers congrus à \(2\) modulo \(3\) (comptés avec multiplicité).

Si \(\prod_{j=1}^{t} (b_j + 1)\) est pair, on peut supposer que \(b_1 + 1\) est pair. On choisit librement les exposants de \(q_2, q_3, \ldots, q_t\), de \(\prod_{j=2}^{t} (b_j + 1)\) façons. La parité de l'exposant de \(q_1\) est alors imposée, et il y a \(\frac{1}{2}(b_1 + 1)\) façons de choisir cet exposant. Donc (1) est vraie dans ce cas.

Si \(\prod_{j=1}^{t} (b_j + 1)\) est impair, on compte par récurrence sur \(t\). Pour \(t = 1\), il y a \(\left\lceil \frac{b_1 + 1}{2} \right\rceil\) choix d'exposant pair et \(\left\lfloor \frac{b_1 + 1}{2} \right\rfloor\) choix d'exposant impair. Pour l'hérédité, le nombre de choix comportant un nombre pair de facteurs premiers est

\[\left\lceil \frac{1}{2} \prod_{j=1}^{t-1} (b_j + 1) \right\rceil \cdot \left\lceil \frac{b_t + 1}{2} \right\rceil + \left\lfloor \frac{1}{2} \prod_{j=1}^{t-1} (b_j + 1) \right\rfloor \cdot \left\lfloor \frac{b_t + 1}{2} \right\rfloor = \left\lceil \frac{1}{2} \prod_{j=1}^{t} (b_j + 1) \right\rceil,\]

et il y a donc \(\left\lfloor \frac{1}{2} \prod_{j=1}^{t} (b_j + 1) \right\rfloor\) choix comportant un nombre impair de facteurs premiers. Donc (1) est vraie aussi dans ce cas. \(\square\)

Précision ajoutée sur l'égalité ci-dessus : si \(u = \prod_{j=1}^{t-1}(b_j + 1) = 2k + 1\) et \(b_t + 1 = 2l + 1\), le membre de gauche vaut \((k+1)(l+1) + kl = 2kl + k + l + 1 = \left\lceil \frac{(2k+1)(2l+1)}{2} \right\rceil\).

Écrivons maintenant \(n = 3^x 2^y 5^z p_1^{a_1} \cdots p_s^{a_s} q_1^{b_1} \cdots q_t^{b_t}\) (ici les \(q_j\) sont différents de \(2\) et \(5\), qui sont eux-mêmes congrus à \(2\) modulo \(3\)). Par la formule classique du nombre de diviseurs,

\[\tau(10n) = (x + 1)(y + 2)(z + 2) \prod_{i=1}^{s} (a_i + 1) \prod_{j=1}^{t} (b_j + 1). \tag{2}\]

D'après l'affirmation,

\[\tau_1(10n) = \prod_{i=1}^{s} (a_i + 1) \left\lceil \frac{1}{2} (y + 2)(z + 2) \prod_{j=1}^{t} (b_j + 1) \right\rceil. \tag{3}\]

Posons \(c = (y + 2)(z + 2) \prod_{j=1}^{t} (b_j + 1)\).

Si \(c\) est pair, (2) et (3) donnent

\[\frac{\tau(10n)}{\tau_1(10n)} = 2(x + 1).\]

Dans ce cas, le quotient peut prendre toutes les valeurs entières paires strictement positives quand \(x\) parcourt les entiers positifs ou nuls.

Si \(c\) est impair, c'est-à-dire si \(y\) et \(z\) sont impairs et si tous les \(b_j\) sont pairs, (2) et (3) donnent

\[\frac{\tau(10n)}{\tau_1(10n)} = \frac{2(x + 1)c}{c + 1}. \tag{4}\]

Pour que ce soit un entier, il faut que \(c + 1\) divise \(2(x + 1)\), puisque \(c\) et \(c + 1\) sont premiers entre eux. Posons \(2(x + 1) = k(c + 1)\). Alors (4) devient

\[\frac{\tau(10n)}{\tau_1(10n)} = kc = k(y + 2)(z + 2) \prod_{j=1}^{t} (b_j + 1). \tag{5}\]

Comme \(y\) et \(z\) sont impairs, les entiers \(y + 2\) et \(z + 2\) sont au moins égaux à \(3\) ; le quotient est donc un nombre composé. Réciproquement, pour tout nombre composé impair \(ab\) avec \(a, b \geq 3\) (impairs), on peut prendre \(n = 3^{\frac{ab - 1}{2}} \cdot 2^{a - 2} \cdot 5^{b - 2}\), et (5) donne \(\frac{\tau(10n)}{\tau_1(10n)} = ab\) (avec \(k = 1\)).

Conclusion. Le quotient peut être n'importe quel entier pair ou n'importe quel nombre composé impair ; de façon équivalente, il peut valoir \(2\) ou n'importe quel nombre composé. \(\blacksquare\)