Shortlist 2014, N4

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

Concepts : Congruences, théorèmes de Fermat et d'Euler · Partie entière et majorations · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 73 (page 74 du PDF)

Énoncé

Let \(n > 1\) be a given integer. Prove that infinitely many terms of the sequence \((a_k)_{k \geq 1}\), defined by

\[a_k = \left\lfloor \frac{n^k}{k} \right\rfloor,\]

are odd. (For a real number \(x\), \(\lfloor x \rfloor\) denotes the largest integer not exceeding \(x\).)

Indices : les idées clés

• \(n\) impair : avec \(k = n^m\), \(a_k = n^{n^m - m}\) est impair.
• Partie entière : si \(k \mid n^k - r\) avec \(0 \leq r < k\), alors \(\left\lfloor \frac{n^k}{k} \right\rfloor = \frac{n^k - r}{k}\) ; il s'agit de choisir \(k\) pour que ce quotient soit impair.
• Petit théorème de Fermat (solution 1) : \(k = p \cdot 2^m\) avec \(p\) premier impair divisant \(n^{2^m} - 2^m\) ; ou des puissances \(k = p^i\) d'un premier \(p \mid n - 1\), dont on contrôle la valuation (solution 2).

Solutions

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

Solution 1

Si \(n\) est impair, prenons \(k = n^m\) pour \(m = 1, 2, \ldots\) Alors \(a_k = n^{n^m - m}\), qui est impair pour tout \(m\).

Supposons désormais \(n\) pair, \(n = 2t\) avec \(t \geq 1\) entier. Pour tout \(m \geq 2\), l'entier \(n^{2^m} - 2^m = 2^m(2^{2^m - m} \cdot t^{2^m} - 1)\) a un diviseur premier impair \(p\), puisque \(2^m - m > 1\). Pour \(k = p \cdot 2^m\), on a alors

\[n^k = (n^{2^m})^p \equiv (2^m)^p = (2^p)^m \equiv 2^m,\]

les congruences étant modulo \(p\) (on rappelle que \(2^p \equiv 2 \pmod p\) par le petit théorème de Fermat). De plus, \(n^k - 2^m < n^k < n^k + 2^m(p - 1)\) montre que la fraction \(\frac{n^k}{k}\) est strictement comprise entre les entiers consécutifs \(\frac{n^k - 2^m}{p \cdot 2^m}\) et \(\frac{n^k + 2^m(p - 1)}{p \cdot 2^m}\) (ce sont bien des entiers, car \(2^m \mid n^k\) et \(p \mid n^k - 2^m\)). Donc

\[\left\lfloor \frac{n^k}{k} \right\rfloor = \frac{n^k - 2^m}{p \cdot 2^m}.\]

Enfin, \(\frac{n^k - 2^m}{p \cdot 2^m} = \frac{\frac{n^k}{2^m} - 1}{p}\) est un entier impair, car l'entier \(\frac{n^k}{2^m} - 1\) est impair (on rappelle que \(k > m\)). Pour des valeurs différentes de \(m\), on obtient des valeurs différentes de \(k\), puisque la puissance de \(2\) dans la décomposition de \(k\) est différente. \(\blacksquare\)

Solution 2

Le cas (trivial) \(n\) impair se traite comme dans la solution 1.

Supposons \(n\) pair et \(n > 2\). Soit \(p\) un diviseur premier de \(n - 1\).

Montrons par récurrence sur \(i\) que \(p^{i+1}\) divise \(n^{p^i} - 1\) pour tout \(i \geq 0\). Le cas \(i = 0\) est vrai par le choix de \(p\). Supposons le résultat vrai pour un \(i \geq 0\). La factorisation

\[n^{p^{i+1}} - 1 = (n^{p^i} - 1)\left[n^{p^i(p-1)} + n^{p^i(p-2)} + \cdots + n^{p^i} + 1\right],\]

avec le fait que chacun des \(p\) termes entre crochets est congru à \(1\) modulo \(p\), montre que le résultat est vrai pour \(i + 1\).

Donc

\[\left\lfloor \frac{n^{p^i}}{p^i} \right\rfloor = \frac{n^{p^i} - 1}{p^i},\]

un entier impair, pour tout \(i \geq 1\).

Considérons enfin le cas \(n = 2\). Montrons que \(3 \cdot 4^i\) divise \(2^{3 \cdot 4^i} - 4^i\) pour tout \(i \geq 1\). D'abord, \(4^i\) divise \(2^{3 \cdot 4^i} - 4^i\), car \(3 \cdot 4^i > 2i\). Ensuite, \(2^{3 \cdot 4^i}\) et \(4^i\) sont tous deux congrus à \(1\) modulo \(3\), donc \(3 \mid 2^{3 \cdot 4^i} - 4^i\). Ainsi

\[\left\lfloor \frac{2^{3 \cdot 4^i}}{3 \cdot 4^i} \right\rfloor = \frac{2^{3 \cdot 4^i} - 4^i}{3 \cdot 4^i} = \frac{2^{3 \cdot 4^i - 2i} - 1}{3},\]

qui est impair pour tout \(i \geq 1\). \(\blacksquare\)

Remarque. Le cas \(n\) pair et \(n > 2\) se traite aussi en définissant par récurrence la suite \((k_i)_{i \geq 1}\) par \(k_1 = 1\) et \(k_{i+1} = n^{k_i} - 1\). La suite \((k_i)\) est strictement croissante, et l'on montre par récurrence sur \(i\) que \(k_i \mid n^{k_i} - 1\) pour tout \(i \geq 1\) ; les \(k_i\) conviennent donc.

Le cas \(n = 2\) peut aussi se traiter ainsi. Soit \(i \geq 2\). Par le postulat de Bertrand, il existe un nombre premier \(p\) tel que \(2^{2i-1} < p \cdot 2^i < 2^{2i}\). Cela donne

\[p \cdot 2^i < 2^{2i} < 2p \cdot 2^i. \tag{1}\]

De plus, \(p \cdot 2^i\) divise \(2^{p \cdot 2^i} - 2^{2i}\) ; avec (1), on obtient

\[\left\lfloor \frac{2^{p \cdot 2^i}}{p \cdot 2^i} \right\rfloor = \frac{2^{p \cdot 2^i} - 2^{2i} + p \cdot 2^i}{p \cdot 2^i} = \frac{2^{p \cdot 2^i - i} - 2^{2i - i} + p}{p},\]

qui est un entier impair.

Solution 3

Le cas (trivial) \(n\) impair se traite comme dans la solution 1.

Soit \(n\) pair, et \(p\) un diviseur premier de \(n + 1\). Définissons la suite \((a_i)_{i \geq 1}\) par

\[a_i = \min\{a \in \mathbb{Z}_{>0} : 2^i \text{ divise } ap + 1\}.\]

Il existe \(a\) avec \(1 \leq a < 2^i\) tel que \(ap \equiv -1 \pmod{2^i}\), donc chaque \(a_i\) vérifie \(1 \leq a_i < 2^i\). Cela implique \(a_i p + 1 < p \cdot 2^i\). De plus, \(a_i \to \infty\) quand \(i \to \infty\), donc il existe une infinité d'indices \(i\) tels que \(a_i < a_{i+1}\). On se restreint désormais à ces \(i\).

Le nombre \(p\) divise \(n^p + 1\), qui divise à son tour \(n^{p \cdot 2^i} - 1\). Il s'ensuit que \(p \cdot 2^i\) divise \(n^{p \cdot 2^i} - (a_i p + 1)\), et l'entier

\[\left\lfloor \frac{n^{p \cdot 2^i}}{p \cdot 2^i} \right\rfloor = \frac{n^{p \cdot 2^i} - (a_i p + 1)}{p \cdot 2^i}\]

est donc impair, puisque \(2^{i+1}\) divise \(n^{p \cdot 2^i}\) mais pas \(a_i p + 1\). \(\blacksquare\)