Shortlist 2006, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Estonia
Concepts : Congruences, théorèmes de Fermat et d'Euler · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2006 (avec solutions), p. 63 (page 64 du PDF)
Énoncé¶
Montrer que, pour tout entier \(n\) strictement positif, il existe un entier \(m\) tel que \(2^m + m\) soit divisible par \(n\).
Énoncé original (anglais)
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
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
Pour tout \(i = 0, 1, \ldots, d - 1\), considérons la suite
Modulo \(a\), ces nombres sont respectivement congrus à
Les \(d\) suites contiennent en tout \(a'd = a\) nombres. Montrons que deux d'entre eux ne sont jamais congrus modulo \(a\).
Supposons que
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
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\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N7 ★★★★☆ · OIM P3 : Les fonctions telles que \(f(a)\) divise \(b^a - f(b)^{f(a)}\) : quelle est la meilleure constante \(c\) avec \(f(n) \leq cn\) ?
- 2024 N6 ★★★★☆ : Pour quels \(n\) tout polynôme entier \(P\) admet-il un \(Q\) de degré \(2\) tel que \(Q(k)(P(k) + Q(k))\) ne soit jamais divisible par \(n\) ?
- 2022 N7 ★★★★☆ · OIM P3 : Il y a au plus une façon de disposer des premiers en cercle avec des produits voisins de la forme \(x^2 + x + k\).
- 2015 N7 ★★★★☆ : Pour quels \(k\) existe-t-il \(f\) telle que \(\gcd(f(m) + n, f(n) + m) \leq k\) pour tous \(m \neq n\) ?