Aller au contenu

Shortlist 2017, N4

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

Concepts : Ordre d'un élément et racines primitives · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2017 (avec solutions), p. 78 (page 80 du PDF)

Énoncé

Call a rational number short if it has finitely many digits in its decimal expansion. For a positive integer \(m\), we say that a positive integer \(t\) is \(m\)-tastic if there exists a number \(c \in \{1, 2, 3, \ldots, 2017\}\) such that \(\dfrac{10^t - 1}{c \cdot m}\) is short, and such that \(\dfrac{10^k - 1}{c \cdot m}\) is not short for any \(1 \leq k < t\). Let \(S(m)\) be the set of \(m\)-tastic numbers. Consider \(S(m)\) for \(m = 1, 2, \ldots\). What is the maximum number of elements in \(S(m)\)?

Indices : les idées clés
  • Caractériser les nombres « courts » : \(x \in \mathbb{Q}\) est court si et seulement si \(2^a 5^b x \in \mathbb{Z}\) pour certains \(a, b \geq 0\) ; on peut donc supposer \(\gcd(m, 10) = 1\).
  • Ordre de \(10\) modulo \(cm\) : \(S(m) = \{\operatorname{ord}_{cm}(10) : c \in C\}\), où \(C\) est l'ensemble des \(c \leq 2017\) premiers avec \(10\), d'où \(|S(m)| \leq |C| = 807\).
  • Construction : \(m = 10^\alpha - 1\), où tout premier \(p \leq 2017\) autre que \(2, 5\) divise \(10^\alpha - 1\) ; on obtient alors \(\operatorname{ord}_{cm}(10) = c\alpha\), valeurs toutes distinctes.
  • Lemme LTE : \(\nu_p(10^{\ell\alpha} - 1) = \nu_p(10^\alpha - 1) + \nu_p(\ell)\) pour \(p\) impair, \(p \neq 5\), divisant \(10^\alpha - 1\).
Solutions

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

Réponse : le nombre maximal d'éléments de \(S(m)\) est \(807\).

Solution 1

Nombres courts. Remarquons d'abord que \(x \in \mathbb{Q}\) est court si et seulement s'il existe des exposants \(a, b \geq 0\) tels que \(2^a \cdot 5^b \cdot x \in \mathbb{Z}\). En effet, si \(x\) est court, alors \(x = \frac{n}{10^k}\) pour un certain \(k\), et l'on peut prendre \(a = b = k\). Réciproquement, si \(2^a \cdot 5^b \cdot x = q \in \mathbb{Z}\), alors \(x = \frac{2^b \cdot 5^a \cdot q}{10^{a+b}}\), donc \(x\) est court.

Réduction. Si \(m = 2^a \cdot 5^b \cdot s\) avec \(\gcd(s, 10) = 1\), alors \(\frac{10^t - 1}{m}\) est court si et seulement si \(s\) divise \(10^t - 1\) (le nombre \(10^t - 1\) étant premier avec \(10\)). On peut donc supposer, sans perte de généralité, que \(\gcd(m, 10) = 1\) ; de même, seule la partie de \(c\) première avec \(10\) compte. Posons

\[C = \{1 \leq c \leq 2017 : \gcd(c, 10) = 1\}.\]

Les nombres \(m\)-tastiques sont alors exactement les plus petits exposants \(t > 0\) tels que \(10^t \equiv 1 \pmod{cm}\) pour un certain \(c \in C\), c'est-à-dire les ordres de \(10\) modulo \(cm\) :

\[S(m) = \{\operatorname{ord}_{cm}(10) : c \in C\}.\]

Comme il y a \(4 \cdot 201 + 3 = 807\) entiers \(c\) avec \(1 \leq c \leq 2017\) et \(\gcd(c, 10) = 1\) (ceux qui sont \(\equiv 1, 3, 7, 9 \pmod{10}\)), on a

\[|S(m)| \leq |C| = 807.\]

Construction avec \(|S(m)| = 807\). Soit

\[P = \{1 < p \leq 2017 : p \text{ premier},\ p \neq 2, 5\}.\]

Choisissons un entier \(\alpha > 0\) tel que tout \(p \in P\) divise \(10^\alpha - 1\) (par exemple \(\alpha = \varphi(T)\), où \(T\) est le produit des nombres premiers de \(P\), par le théorème d'Euler), et posons \(m = 10^\alpha - 1\).

Affirmation. Pour tout \(c \in C\), \(\operatorname{ord}_{cm}(10) = c\alpha\).

Comme conséquence immédiate, les \(807\) ordres sont distincts, donc \(|S(m)| = |C| = 807\), ce qui conclut.

Preuve. Évidemment \(\operatorname{ord}_m(10) = \alpha\). Soit \(t = \operatorname{ord}_{cm}(10)\). Alors

\[cm \mid 10^t - 1 \implies m \mid 10^t - 1 \implies \alpha \mid t.\]

Donc \(t = k\alpha\) pour un certain entier \(k > 0\). Montrons que \(k = c\).

Notons \(\nu_p(n)\) l'exposant de \(p\) dans \(n\) (le plus grand \(\beta\) tel que \(p^\beta \mid n\)). Pour tout \(\ell \geq 1\) et tout \(p \in P\), le lemme LTE donne

\[\nu_p(10^{\ell\alpha} - 1) = \nu_p\big((10^\alpha)^\ell - 1\big) = \nu_p(10^\alpha - 1) + \nu_p(\ell) = \nu_p(m) + \nu_p(\ell).\]

Les facteurs premiers de \(c\) sont dans \(P\), et pour un premier \(p \notin P\), \(\nu_p(cm) = \nu_p(m) \leq \nu_p(10^{k\alpha} - 1)\) automatiquement. Donc

\[\begin{aligned} cm \mid 10^{k\alpha} - 1 &\iff \forall p \in P,\ \nu_p(cm) \leq \nu_p(10^{k\alpha} - 1) \\ &\iff \forall p \in P,\ \nu_p(m) + \nu_p(c) \leq \nu_p(m) + \nu_p(k) \\ &\iff \forall p \in P,\ \nu_p(c) \leq \nu_p(k) \\ &\iff c \mid k. \end{aligned}\]

Le plus petit tel \(k\) est \(k = c\), donc \(\operatorname{ord}_{cm}(10) = c\alpha\). \(\blacksquare\)

Remarques

Remarque 1 (le lemme LTE). Pour tout nombre premier impair \(p\), tous entiers \(a, b\) premiers avec \(p\) tels que \(p \mid a - b\), et tout entier \(n > 0\),

\[\nu_p(a^n - b^n) = \nu_p(a - b) + \nu_p(n),\]

et, pour \(p = 2\) (avec \(a, b\) impairs et \(n\) pair),

\[\nu_2(a^n - b^n) = \nu_2(a^2 - b^2) + \nu_2(n) - 1.\]

Les deux énoncés se démontrent par récurrence sur \(n\).