Shortlist 2013, N4

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

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

Solution officielle : Shortlist officielle 2013 (avec solutions), p. 56 (page 56 du PDF)

Énoncé

Determine whether there exists an infinite sequence of nonzero digits \(a_1, a_2, a_3, \ldots\) and a positive integer \(N\) such that for every integer \(k > N\), the number \(\overline{a_k a_{k-1} \ldots a_1}\) is a perfect square.

Indices : les idées clés

• Différences de carrés : avec \(y_k = x_k^2\) le nombre à \(k\) chiffres, \((x_{k+1} - x_k)(x_{k+1} + x_k) = a_{k+1} \cdot 10^k\).
• Valuation \(5\)-adique (solution 1) : si \(5^{\gamma_n} \parallel x_n\) avec \(2\gamma_n < n\), la valuation resterait constante et une majoration \(5^{k - \gamma} < 2 \cdot 10^{(k+1)/2}\) échoue ; donc \(2\gamma_n \geq n\), d'où \(a_{2k+2} = 5\).
• Conclusion : \((A_k - B_k)(A_k + B_k) = 2^{2k+1}\) avec \(A_k\), \(B_k\) impairs force \(A_k = 2^{2k-1} + 1\), et \(y_{2k+2}\) aurait trop de chiffres.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions).

Réponse : non.

Solution 1

Supposons qu'une suite \(a_1, a_2, a_3, \ldots\) convienne. Pour tout entier \(k \geq 1\), posons \(y_k = \overline{a_k a_{k-1} \ldots a_1}\). Par hypothèse, pour tout \(k > N\), il existe un entier \(x_k > 0\) tel que \(y_k = x_k^2\).

I. Pour tout \(n\), soit \(5^{\gamma_n}\) la plus grande puissance de \(5\) qui divise \(x_n\). Montrons d'abord que \(2\gamma_n \geq n\) pour tout entier \(n > N\).

Supposons au contraire qu'il existe un entier \(n > N\) tel que \(2\gamma_n < n\), ce qui donne

\[y_{n+1} = \overline{a_{n+1} a_n \ldots a_1} = 10^n a_{n+1} + \overline{a_n a_{n-1} \ldots a_1} = 10^n a_{n+1} + y_n = 5^{2\gamma_n}\left(2^n 5^{n - 2\gamma_n} a_{n+1} + \frac{y_n}{5^{2\gamma_n}}\right).\]

Comme \(5 \nmid \frac{y_n}{5^{2\gamma_n}}\), on obtient \(\gamma_{n+1} = \gamma_n < n < n + 1\). Par les mêmes arguments, \(\gamma_n = \gamma_{n+1} = \gamma_{n+2} = \cdots\) ; notons \(\gamma\) cette valeur commune.

Pour tout \(k \geq n\), on a

\[(x_{k+1} - x_k)(x_{k+1} + x_k) = x_{k+1}^2 - x_k^2 = y_{k+1} - y_k = a_{k+1} \cdot 10^k.\]

L'un des nombres \(x_{k+1} - x_k\) et \(x_{k+1} + x_k\) n'est pas divisible par \(5^{\gamma+1}\), sinon on aurait \(5^{\gamma+1} \mid \big((x_{k+1} - x_k) + (x_{k+1} + x_k)\big) = 2x_{k+1}\). D'autre part, \(5^k \mid (x_{k+1} - x_k)(x_{k+1} + x_k)\), donc \(5^{k-\gamma}\) divise l'un de ces deux facteurs. On obtient

\[5^{k - \gamma} \leq \max\{x_{k+1} - x_k, x_{k+1} + x_k\} < 2x_{k+1} = 2\sqrt{y_{k+1}} < 2 \cdot 10^{(k+1)/2},\]

ce qui implique \(5^{2k} < 4 \cdot 5^{2\gamma} \cdot 10^{k+1}\), soit \(\left(\frac{5}{2}\right)^k < 40 \cdot 5^{2\gamma}\). Cette inégalité est clairement fausse pour \(k\) assez grand. Cette contradiction montre que \(2\gamma_n \geq n\) pour tout \(n > N\).

II. Considérons maintenant un entier \(k > \max\{N/2, 2\}\). Comme \(2\gamma_{2k+1} \geq 2k + 1\) et \(2\gamma_{2k+2} \geq 2k + 2\), on a \(\gamma_{2k+1} \geq k + 1\) et \(\gamma_{2k+2} \geq k + 1\). De \(y_{2k+2} = a_{2k+2} \cdot 10^{2k+1} + y_{2k+1}\), on tire donc \(5^{2k+2} \mid y_{2k+2} - y_{2k+1} = a_{2k+2} \cdot 10^{2k+1}\), d'où \(5 \mid a_{2k+2}\), ce qui implique \(a_{2k+2} = 5\). Donc

\[(x_{2k+2} - x_{2k+1})(x_{2k+2} + x_{2k+1}) = x_{2k+2}^2 - x_{2k+1}^2 = y_{2k+2} - y_{2k+1} = 5 \cdot 10^{2k+1} = 2^{2k+1} \cdot 5^{2k+2}.\]

En posant \(A_k = \frac{x_{2k+2}}{5^{k+1}}\) et \(B_k = \frac{x_{2k+1}}{5^{k+1}}\), qui sont entiers, on obtient

\[(A_k - B_k)(A_k + B_k) = 2^{2k+1}. \tag{1}\]

Les nombres \(A_k\) et \(B_k\) sont impairs, sinon \(y_{2k+2}\) ou \(y_{2k+1}\) serait multiple de \(10\), ce qui est faux car \(a_1 \neq 0\) ; donc l'un des nombres \(A_k - B_k\) et \(A_k + B_k\) n'est pas divisible par \(4\). Par (1), \(A_k - B_k = 2\) et \(A_k + B_k = 2^{2k}\), d'où \(A_k = 2^{2k-1} + 1\) et

\[x_{2k+2} = 5^{k+1} A_k = 10^{k+1} \cdot 2^{k-2} + 5^{k+1} > 10^{k+1},\]

puisque \(k \geq 2\). Cela implique \(y_{2k+2} > 10^{2k+2}\), ce qui contredit le fait que \(y_{2k+2}\) a \(2k + 2\) chiffres. Le résultat suit. \(\blacksquare\)

Solution 2

Supposons à nouveau qu'une suite \(a_1, a_2, a_3, \ldots\) vérifie les conditions, introduisons \(x_k\) et \(y_k\) comme dans la solution précédente, et remarquons que

\[y_{k+1} - y_k = (x_{k+1} - x_k)(x_{k+1} + x_k) = 10^k a_{k+1} \tag{2}\]

pour tout \(k > N\). Considérons un tel \(k\). Comme \(a_1 \neq 0\), les nombres \(x_k\) et \(x_{k+1}\) ne sont pas multiples de \(10\), donc \(p_k = x_{k+1} - x_k\) et \(q_k = x_{k+1} + x_k\) ne peuvent pas être tous deux multiples de \(20\) ; l'un d'eux n'est donc divisible ni par \(4\), ni par \(5\). Avec (2), cela signifie que l'autre est divisible par \(5^k\) ou par \(2^{k-1}\). Remarquons aussi que \(p_k\) et \(q_k\) ont la même parité, donc sont tous deux pairs.

D'autre part, \(x_{k+1}^2 = x_k^2 + 10^k a_{k+1} \geq x_k^2 + 10^k > 2x_k^2\), donc \(\frac{x_{k+1}}{x_k} > \sqrt{2}\), ce qui implique

\[1 < \frac{q_k}{p_k} = 1 + \frac{2}{x_{k+1}/x_k - 1} < 1 + \frac{2}{\sqrt{2} - 1} < 6. \tag{3}\]

Si l'un des nombres \(p_k\), \(q_k\) est divisible par \(5^k\), on a donc

\[10^{k+1} > 10^k a_{k+1} = p_k q_k \geq \frac{(5^k)^2}{6},\]

d'où \(\left(\frac{5}{2}\right)^k < 60\), ce qui est faux pour \(k\) assez grand. Pour \(k\) grand, \(2^{k-1}\) divise donc l'un des nombres \(p_k\) et \(q_k\). Ainsi

\[\{p_k, q_k\} = \{2^{k-1} \cdot 5^{r_k} b_k, \; 2 \cdot 5^{k - r_k} c_k\}\]

avec des entiers positifs ou nuls \(b_k\), \(c_k\), \(r_k\) tels que \(b_k c_k = a_{k+1}\).

De plus, (3) donne

\[6 > \frac{2^{k-1} \cdot 5^{r_k} b_k}{2 \cdot 5^{k - r_k} c_k} \geq \frac{1}{36} \cdot \left(\frac{2}{5}\right)^k \cdot 5^{2r_k} \quad \text{et} \quad 6 > \frac{2 \cdot 5^{k - r_k} c_k}{2^{k-1} \cdot 5^{r_k} b_k} \geq \frac{4}{9} \cdot \left(\frac{5}{2}\right)^k \cdot 5^{-2r_k},\]

donc

\[\alpha k + c_1 < r_k < \alpha k + c_2 \quad \text{pour } \alpha = \tfrac{1}{2} \log_5\left(\tfrac{5}{2}\right) < 1 \text{ et des constantes } c_2 > c_1. \tag{4}\]

Par conséquent, pour \(C = c_2 - c_1 + 1 - \alpha > 0\),

\[(k + 1) - r_{k+1} \leq k - r_k + C. \tag{5}\]

On utilise ensuite le lemme facile suivant.

Lemme. Soit \(s\) un entier strictement positif. Alors \(5^{s + 2^s} \equiv 5^s \pmod{10^s}\).

Preuve. Le théorème d'Euler donne \(5^{2^s} \equiv 1 \pmod{2^s}\), donc \(5^{s + 2^s} - 5^s = 5^s(5^{2^s} - 1)\) est divisible par \(2^s\) et par \(5^s\). \(\square\)

Pour tout \(k\) assez grand, on a

\[x_{k+1} = \frac{p_k + q_k}{2} = 5^{r_k} \cdot 2^{k-2} b_k + 5^{k - r_k} c_k \equiv 5^{k - r_k} c_k \pmod{10^{r_k}}, \tag{6}\]

puisque \(r_k \leq k - 2\) par (4) ; donc \(y_{k+1} \equiv 5^{2(k - r_k)} c_k^2 \pmod{10^{r_k}}\). Soit \(s\) un grand entier, et choisissons le plus petit \(k\) tel que \(2(k - r_k) \geq s + 2^s\) ; il existe par (4). Posons \(d = 2(k - r_k) - (s + 2^s)\). Par (4), on a \(2^s < 2(k - r_k) < \left(\frac{2}{\alpha} - 2\right) r_k - \frac{2c_1}{\alpha}\) ; si \(s\) est grand, cela implique \(r_k > s\), donc (6) est aussi vraie modulo \(10^s\). Alors (6) et le lemme donnent

\[y_{k+1} \equiv 5^{2(k - r_k)} c_k^2 = 5^{s + 2^s} \cdot 5^d c_k^2 \equiv 5^s \cdot 5^d c_k^2 \pmod{10^s}. \tag{7}\]

Par (5) et la minimalité de \(k\), on a \(d \leq 2C\), donc \(5^d c_k^2 \leq 5^{2C} \cdot 81 = D\). Avec \(5^4 < 10^3\), on obtient

\[5^s \cdot 5^d c_k^2 < 10^{3s/4} D < 10^{s-1}\]

pour \(s\) assez grand. Avec (7), cela montre que le \(s\)-ème chiffre en partant de la droite de \(y_{k+1}\), qui est \(a_s\), est nul. Cela contredit l'hypothèse du problème. \(\blacksquare\)