Shortlist 2011, N4

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

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

Solution officielle : Shortlist officielle 2011 (avec solutions), p. 67 (page 68 du PDF)

Énoncé

For each positive integer \(k\), let \(t(k)\) be the largest odd divisor of \(k\). Determine all positive integers \(a\) for which there exists a positive integer \(n\) such that all the differences

\[t(n + a) - t(n), \quad t(n + a + 1) - t(n + 1), \quad \ldots, \quad t(n + 2a - 1) - t(n + a - 1)\]

are divisible by \(4\).

Indices : les idées clés

• Exemples : les couples \((a, n) = (1, 1)\), \((3, 1)\) et \((5, 4)\) conviennent.
• \(a\) pair : avec \(a = 2^\alpha d\), on trouve un \(n + i\) de valuation \(2\)-adique exactement \(\alpha - 1\) ; alors \(t(n + a + i) \equiv t(n + i) + 2 \pmod 4\).
• \(a\) impair : modulo \(4\), un \(n + i = 2d\) (\(d\) impair) donne \(t(n + i) \not\equiv t(n + i + 4)\) alors que \(t(n + a + i) \equiv t(n + a + i + 4)\) ; le cas \(a = 7\) se traite à part.

Solutions

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

Réponse : \(a = 1\), \(3\) ou \(5\).

Solution

Un couple \((a, n)\) vérifiant la condition du problème sera appelé un couple gagnant. On vérifie directement que les couples \((1, 1)\), \((3, 1)\) et \((5, 4)\) sont gagnants.

Supposons maintenant que \(a\) est un entier strictement positif différent de \(1\), \(3\) et \(5\). Montrons qu'il n'y a pas de couple gagnant \((a, n)\), en distinguant trois cas.

Cas 1 : \(a\) est pair. Dans ce cas, \(a = 2^\alpha d\) pour un entier \(\alpha \geq 1\) et un entier \(d\) impair. Comme \(a \geq 2^\alpha\), pour tout entier \(n > 0\), il existe un \(i \in \{0, 1, \ldots, a - 1\}\) tel que \(n + i = 2^{\alpha-1}e\), où \(e\) est un entier impair. On a alors \(t(n + i) = t(2^{\alpha-1}e) = e\) et

\[t(n + a + i) = t(2^\alpha d + 2^{\alpha-1}e) = 2d + e \equiv e + 2 \pmod 4.\]

Donc \(t(n + i) - t(n + a + i) \equiv 2 \pmod 4\), et \((a, n)\) n'est pas un couple gagnant.

Cas 2 : \(a\) est impair et \(a > 8\). Pour tout entier \(n > 0\), il existe un \(i \in \{0, 1, \ldots, a - 5\}\) tel que \(n + i = 2d\) pour un \(d\) impair. On a

\[t(n + i) = d \not\equiv d + 2 = t(n + i + 4) \pmod 4\]

et

\[t(n + a + i) = n + a + i \equiv n + a + i + 4 = t(n + a + i + 4) \pmod 4.\]

Les entiers \(t(n + a + i) - t(n + i)\) et \(t(n + a + i + 4) - t(n + i + 4)\) ne peuvent donc pas être tous deux divisibles par \(4\), et il n'y a pas de couple gagnant dans ce cas.

Cas 3 : \(a = 7\). Pour tout entier \(n > 0\), il existe un \(i \in \{0, 1, \ldots, 6\}\) tel que \(n + i\) soit de la forme \(8k + 3\) ou de la forme \(8k + 6\), où \(k\) est un entier positif ou nul. Or

\[t(8k + 3) \equiv 3 \not\equiv 1 \equiv 4k + 5 = t(8k + 3 + 7) \pmod 4\]

et

\[t(8k + 6) = 4k + 3 \equiv 3 \not\equiv 1 \equiv t(8k + 6 + 7) \pmod 4.\]

Il n'y a donc pas de couple gagnant de la forme \((7, n)\). \(\blacksquare\)