Aller au contenu

Shortlist 2006, N7

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

Concepts : Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois · Récurrence et constructions récursives

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

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Prove that, for every positive integer \(n\), there exists an integer \(m\) such that \(2^m + m\) is divisible by \(n\).

Indices : les idées clés
  • Énoncé renforcé : pour tout \(d\) et tout \(N\), il existe \(b_0, \ldots, b_{d-1} > N\) tels que \(2^{b_i} + b_i \equiv i \pmod d\) ; on prouve cela par récurrence forte sur \(d\).
  • Période des puissances de \(2\) : modulo \(a\), les restes de \(2^i\) sont périodiques de période \(k < a\) à partir d'un rang \(M\) ; on applique l'hypothèse à \(d = \gcd(a, k) < a\).
  • Relèvement : les nombres \(2^{b_i + mk} + b_i + mk \equiv 2^{b_i} + b_i + mk \pmod a\) (\(0 \leq m < a/d\)) sont deux à deux distincts modulo \(a\), donc prennent tous les restes.
Solutions

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

Solution

Prouvons par récurrence sur \(d\) que, pour tout entier \(N > 0\), il existe des entiers strictement positifs \(b_0, b_1, \ldots, b_{d-1}\) tels que, pour tout \(i = 0, 1, 2, \ldots, d - 1\), on ait \(b_i > N\) et

\[2^{b_i} + b_i \equiv i \pmod d.\]

Cela donne l'énoncé avec \(m = b_0\).

Le cas de base \(d = 1\) est trivial. Prenons \(a > 1\) et supposons l'énoncé vrai pour tout \(d < a\). Remarquons que les restes de \(2^i\) modulo \(a\) se répètent périodiquement à partir d'un certain exposant \(M\). Soit \(k\) la longueur de la période ; cela signifie que \(2^{M+k'} \equiv 2^M \pmod a\) n'est vrai que pour les \(k'\) multiples de \(k\). Remarquons de plus que la période ne peut pas contenir les \(a\) restes, puisque \(0\) en est soit absent, soit l'unique élément. Donc \(k < a\).

Soient \(d = \gcd(a, k)\), \(a' = a/d\) et \(k' = k/d\). Comme \(0 < k < a\), on a aussi \(0 < d < a\). D'après l'hypothèse de récurrence, il existe des entiers strictement positifs \(b_0, b_1, \ldots, b_{d-1}\) tels que \(b_i > \max(2^M, N)\) et

\[2^{b_i} + b_i \equiv i \pmod d \qquad \text{pour } i = 0, 1, 2, \ldots, d - 1. \tag{1}\]

Pour tout \(i = 0, 1, \ldots, d - 1\), considérons la suite

\[2^{b_i} + b_i, \quad 2^{b_i + k} + (b_i + k), \quad \ldots, \quad 2^{b_i + (a'-1)k} + \big(b_i + (a' - 1)k\big). \tag{2}\]

Modulo \(a\), ces nombres sont respectivement congrus à

\[2^{b_i} + b_i, \quad 2^{b_i} + (b_i + k), \quad \ldots, \quad 2^{b_i} + \big(b_i + (a' - 1)k\big).\]

Les \(d\) suites contiennent en tout \(a'd = a\) nombres. Montrons que deux d'entre eux ne sont jamais congrus modulo \(a\).

Supposons que

\[2^{b_i} + (b_i + mk) \equiv 2^{b_j} + (b_j + nk) \pmod a \tag{3}\]

pour certaines valeurs \(i, j \in \{0, 1, \ldots, d - 1\}\) et \(m, n \in \{0, 1, \ldots, a' - 1\}\). Comme \(d\) est un diviseur de \(a\), on a aussi

\[2^{b_i} + (b_i + mk) \equiv 2^{b_j} + (b_j + nk) \pmod d.\]

Comme \(d\) est un diviseur de \(k\), et vu (1), on obtient \(i \equiv j \pmod d\). Comme \(i, j \in \{0, 1, \ldots, d - 1\}\), cela signifie simplement que \(i = j\). En reportant dans (3), on obtient \(mk \equiv nk \pmod a\). Donc \(mk' \equiv nk' \pmod{a'}\) ; et comme \(a'\) et \(k'\) sont premiers entre eux, on obtient \(m \equiv n \pmod{a'}\). Donc aussi \(m = n\).

Il s'ensuit que les \(a\) nombres formant les \(d\) suites (2) remplissent toutes les conditions (ils prennent tous les restes modulo \(a\)) ; ils sont certainement tous supérieurs à \(N\), puisqu'on a choisi chaque \(b_i > \max(2^M, N)\). L'énoncé est donc vrai pour \(a\), ce qui termine la récurrence. \(\blacksquare\)