Shortlist 2007, N7

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

Concepts : Valuations p-adiques et lemme LTE · Principe des tiroirs

Solution officielle : Shortlist officielle 2007 (avec solutions), p. 63 (page 64 du PDF)

Énoncé

For a prime \(p\) and a positive integer \(n\), denote by \(\nu_p(n)\) the exponent of \(p\) in the prime factorization of \(n!\). Given a positive integer \(d\) and a finite set \(\{p_1, \ldots, p_k\}\) of primes. Show that there are infinitely many positive integers \(n\) such that \(d \mid \nu_{p_i}(n)\) for all \(1 \leq i \leq k\).

Indices : les idées clés

• Lemme d'additivité (valuations) : si \(p^k > r\), alors \(\nu_p(qp^k + r) = \nu_p(qp^k) + \nu_p(r)\).
• Fonction modulo \(d\) : \(f(n) = (\nu_{p_1}(n) \bmod d, \ldots, \nu_{p_k}(n) \bmod d)\) est additive sur les sommes \(n_{\ell_1} + \cdots + n_{\ell_m}\) de la suite \(n_{\ell+1} = (p_1 \cdots p_k)^{n_\ell}\).
• Tiroirs : \(f\) ne prend qu'un nombre fini de valeurs ; \(d\) termes de même image donnent \(f = d \cdot f(n_\ell) = 0\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2007 (deux solutions et une remarque).

Solution 1

Pour un nombre premier \(p\) et un entier \(n > 0\) quelconques, notons \(\operatorname{ord}_p(n)\) l'exposant de \(p\) dans \(n\). Ainsi,

\[\nu_p(n) = \operatorname{ord}_p(n!) = \sum_{i=1}^{n}\operatorname{ord}_p(i).\]

Lemme. Soient \(p\) un nombre premier, \(q\) un entier strictement positif, et \(k\) et \(r\) des entiers strictement positifs tels que \(p^k > r\). Alors \(\nu_p(qp^k + r) = \nu_p(qp^k) + \nu_p(r)\).

Preuve. Montrons que \(\operatorname{ord}_p(qp^k + i) = \operatorname{ord}_p(i)\) pour tout \(0 < i < p^k\). En effet, si \(d = \operatorname{ord}_p(i)\), alors \(d < k\), donc \(qp^k + i\) est divisible par \(p^d\), mais seul le premier terme est divisible par \(p^{d+1}\) ; la somme ne l'est donc pas.

Avec cette affirmation, on obtient

\[\nu_p(qp^k + r) = \sum_{i=1}^{qp^k}\operatorname{ord}_p(i) + \sum_{i=qp^k+1}^{qp^k+r}\operatorname{ord}_p(i) = \sum_{i=1}^{qp^k}\operatorname{ord}_p(i) + \sum_{i=1}^{r}\operatorname{ord}_p(i) = \nu_p(qp^k) + \nu_p(r). \qquad \square\]

Pour tout entier \(a\), notons \(\overline{a}\) son reste modulo \(d\). L'addition des restes se fait aussi modulo \(d\), c'est-à-dire \(\overline{a} + \overline{b} = \overline{a + b}\). Pour tout entier \(n > 0\), posons \(f(n) = (f_1(n), \ldots, f_k(n))\), où \(f_i(n) = \overline{\nu_{p_i}(n)}\).

Définissons la suite \(n_1 = 1\), \(n_{\ell+1} = (p_1p_2 \cdots p_k)^{n_\ell}\). Montrons que

\[f(n_{\ell_1} + n_{\ell_2} + \cdots + n_{\ell_m}) = f(n_{\ell_1}) + f(n_{\ell_2}) + \cdots + f(n_{\ell_m})\]

pour tous \(\ell_1 < \ell_2 < \cdots < \ell_m\). (L'addition des \(k\)-uplets se fait composante par composante.) Le cas de base \(m = 1\) est trivial.

Supposons \(m > 1\). Par construction de la suite, \(p_i^{n_{\ell_1}}\) divise \(n_{\ell_2} + \cdots + n_{\ell_m}\) ; évidemment, \(p_i^{n_{\ell_1}} > n_{\ell_1}\) pour tout \(1 \leq i \leq k\). On peut donc appliquer le lemme avec \(p = p_i\), \(k = r = n_{\ell_1}\) et \(qp^k = n_{\ell_2} + \cdots + n_{\ell_m}\) pour obtenir

\[f_i(n_{\ell_1} + n_{\ell_2} + \cdots + n_{\ell_m}) = f_i(n_{\ell_1}) + f_i(n_{\ell_2} + \cdots + n_{\ell_m}) \qquad \text{pour tout } 1 \leq i \leq k,\]

et donc

\[f(n_{\ell_1} + n_{\ell_2} + \cdots + n_{\ell_m}) = f(n_{\ell_1}) + f(n_{\ell_2} + \cdots + n_{\ell_m}) = f(n_{\ell_1}) + f(n_{\ell_2}) + \cdots + f(n_{\ell_m})\]

par l'hypothèse de récurrence.

Considérons maintenant les valeurs \(f(n_1), f(n_2), \ldots\) La fonction \(f\) ne prend qu'un nombre fini de valeurs. Il existe donc une suite infinie d'indices \(\ell_1 < \ell_2 < \cdots\) telle que \(f(n_{\ell_1}) = f(n_{\ell_2}) = \cdots\), et donc

\[f(n_{\ell_{m+1}} + n_{\ell_{m+2}} + \cdots + n_{\ell_{m+d}}) = f(n_{\ell_{m+1}}) + \cdots + f(n_{\ell_{m+d}}) = d \cdot f(n_{\ell_1}) = (\overline{0}, \ldots, \overline{0})\]

pour tout \(m\). On a trouvé une infinité de nombres convenables. \(\blacksquare\)

Solution 2

On utilise le même lemme et la même définition de la fonction \(f\).

Soit \(S = \{f(n) : n \in \mathbb{N}\}\). Évidemment, l'ensemble \(S\) est fini. Pour tout \(s \in S\), choisissons le plus petit \(n_s\) tel que \(f(n_s) = s\). Notons \(N = \max_{s \in S} n_s\). De plus, soit \(g\) un entier tel que \(p_i^g > N\) pour tout \(i = 1, 2, \ldots, k\). Posons \(P = (p_1p_2 \cdots p_k)^g\).

Montrons que

\[\{f(n) \mid n \in [mP, mP + N]\} = S \tag{1}\]

pour tout entier \(m > 0\). En particulier, comme \((\overline{0}, \ldots, \overline{0}) = f(1) \in S\), il s'ensuit que, pour tout \(m\), il existe un \(n \in [mP, mP + N]\) tel que \(f(n) = (\overline{0}, \ldots, \overline{0})\). Il y a donc une infinité de nombres convenables.

Pour prouver (1), posons \(a_i = f_i(mP)\). Considérons tous les nombres de la forme \(n_{m,s} = mP + n_s\) avec \(s = (s_1, \ldots, s_k) \in S\) (évidemment, tous les \(n_{m,s}\) appartiennent à \([mP, mP + N]\)). Comme \(n_s \leq N < p_i^g\) et \(p_i^g \mid mP\), on peut appliquer le lemme pour les valeurs \(p = p_i\), \(r = n_s\), \(k = g\), \(qp^k = mP\) pour obtenir

\[f_i(n_{m,s}) = f_i(mP) + f_i(n_s) = a_i + s_i ;\]

donc, pour \(s \neq t\) dans \(S\), on a \(f(n_{m,s}) \neq f(n_{m,t})\).

Ainsi, la fonction \(f\) prend au moins \(\lvert S \rvert\) valeurs distinctes dans \([mP, mP + N]\). Comme toutes ces valeurs appartiennent à \(S\), \(f\) doit prendre toutes les valeurs possibles dans \([mP, mP + N]\). \(\blacksquare\)

Remarque

Les deux solutions se prolongent pour prouver les énoncés suivants.

Affirmation 1. Pour tout \(K\), il existe une infinité de \(n\) divisibles par \(K\) tels que \(d \mid \nu_{p_i}(n)\) pour tout \(i\).

Affirmation 2. Pour tout \(s \in S\), il existe une infinité de \(n \in \mathbb{N}\) tels que \(f(n) = s\).