Shortlist 2018, N4¶

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 62 (page 64 du PDF)

Problème 5 de l'OIM 2018

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2018, où il était le problème 5 (jour 2).

Énoncé¶

Let $a_1, a_2, \ldots, a_n, \ldots$ be a sequence of positive integers such that

\[\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}\]

is an integer for all $n \geq k$, where $k$ is some positive integer. Prove that there exists a positive integer $m$ such that $a_n = a_{n+1}$ for all $n \geq m$.

Indices : les idées clés

Regarder la différence $s_{n+1} - s_n$ : elle ne fait intervenir que $a_1$, $a_n$ et $a_{n+1}$, et doit être entière pour $n \geq k$.
PGCD (solution 1) : deux petits lemmes de divisibilité montrent que $d_n = \gcd(a_1, a_n)$ divise $d_{n+1}$, donc se stabilise, puis que $a_{n+1} \mid a_n$ à partir d'un certain rang.
Valuations $p$-adiques (solution 2) : pour chaque premier $p$ (en nombre fini), la suite $v_p(a_n)$ est monotone et bornée à partir d'un certain rang.
Suite monotone d'entiers bornée : elle est stationnaire.

Solutions

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

Solution 1¶

L'argument repose sur deux faits. Soient $a, b, c$ des entiers positifs tels que $N = \frac{b}{c} + \frac{c - b}{a}$ soit un entier.

Si $\gcd(a, c) = 1$, alors $c$ divise $b$.
Si $\gcd(a, b, c) = 1$, alors $\gcd(a, b) = 1$.

Pour (1), on écrit $ab = c(aN + b - c)$ ; comme $\gcd(a, c) = 1$, $c$ divise $b$. Pour (2), on écrit $c^2 - bc = a(cN - b)$, donc $a$ divise $c^2 - bc$. Si $d = \gcd(a, b)$, alors $d$ divise $c^2$ ; comme $d$ et $c$ sont premiers entre eux par hypothèse, $d = 1$.

Posons $s_n = \frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$ et $\delta_n = \gcd(a_1, a_n, a_{n+1})$. On a

\[s_{n+1} - s_n = \frac{a_n}{a_{n+1}} + \frac{a_{n+1} - a_n}{a_1} = \frac{a_n/\delta_n}{a_{n+1}/\delta_n} + \frac{a_{n+1}/\delta_n - a_n/\delta_n}{a_1/\delta_n}.\]

Soit $n \geq k$ ; ce nombre est entier. Comme $\gcd(a_1/\delta_n, a_n/\delta_n, a_{n+1}/\delta_n) = 1$, le fait (2) donne $\gcd(a_1/\delta_n, a_n/\delta_n) = 1$. Soit $d_n = \gcd(a_1, a_n)$. Alors $d_n = \delta_n \cdot \gcd(a_1/\delta_n, a_n/\delta_n) = \delta_n$, donc $d_n$ divise $a_{n+1}$, et par conséquent $d_n$ divise $d_{n+1}$.

Ainsi, à partir d'un certain rang, les $d_n$ forment une suite croissante (au sens large) d'entiers majorés par $a_1$ : il existe $\ell$ tel que $d_n = d$ pour tout $n \geq \ell$.

Enfin, pour $n \geq \ell$, on a $\gcd(a_1/d, a_{n+1}/d) = 1$ et $\delta_n = d$ ; le fait (1) (avec $a = a_1/d$, $b = a_n/d$, $c = a_{n+1}/d$) montre que $a_{n+1}/d$ divise $a_n/d$, donc $a_n \geq a_{n+1}$ pour tout $n \geq \ell$. Une suite décroissante d'entiers positifs est stationnaire, d'où la conclusion. $\blacksquare$

Solution 2¶

On garde la notation $s_n$. Cette fois, on étudie les exposants des nombres premiers dans la décomposition des $a_n$ pour $n \geq k$.

Pour tout $n \geq k$, le nombre

\[s_{n+1} - s_n = \frac{a_n}{a_{n+1}} + \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} \tag{$*$}\]

est entier. En le multipliant par $a_1$, on voit que $a_1 a_n / a_{n+1}$ est entier, donc $a_{n+1} \mid a_1 a_n$. Par suite $a_n \mid a_1^{n-k} a_k$, donc tous les diviseurs premiers de $a_n$ sont parmi ceux de $a_1 a_k$. Ces premiers sont en nombre fini ; il suffit donc de montrer que l'exposant de chacun d'eux dans $a_n$ est constant à partir d'un certain rang.

Soit $p$ un premier divisant $a_1 a_k$. On note $v_p(q)$ l'exposant de $p$ dans la décomposition d'un rationnel non nul $q$ (valuation $p$-adique). Un indice $n \geq k$ est dit grand si $v_p(a_n) \geq v_p(a_1)$.

Cas 1 : il existe un indice grand $n$. Si $v_p(a_{n+1}) < v_p(a_1)$, alors $v_p(a_n/a_{n+1})$ et $v_p(a_n/a_1)$ sont positifs ou nuls, tandis que $v_p(a_{n+1}/a_1) < 0$ ; donc $(*)$ n'est pas entier, contradiction. L'indice $n + 1$ est donc grand aussi. D'autre part, si $v_p(a_{n+1}) > v_p(a_n)$, alors $v_p(a_n/a_{n+1}) < 0$ tandis que $v_p\big((a_{n+1} - a_n)/a_1\big) \geq 0$, et $(*)$ n'est pas entier non plus. Ainsi $v_p(a_1) \leq v_p(a_{n+1}) \leq v_p(a_n)$.

On applique ces arguments successivement aux indices $n + 1, n + 2, \ldots$ : tous les indices supérieurs à $n$ sont grands, et la suite $v_p(a_n), v_p(a_{n+1}), v_p(a_{n+2}), \ldots$ est décroissante (au sens large), donc stationnaire.

Cas 2 : aucun indice n'est grand. On a $v_p(a_1) > v_p(a_n)$ pour tout $n \geq k$. Si l'on avait $v_p(a_{n+1}) < v_p(a_n)$ pour un certain $n \geq k$, alors

\[v_p(a_{n+1}/a_1) < v_p(a_n/a_1) < 0 < v_p(a_n/a_{n+1}),\]

et $(*)$ ne serait pas entier. Donc la suite $v_p(a_k), v_p(a_{k+1}), v_p(a_{k+2}), \ldots$ est croissante (au sens large) et majorée par $v_p(a_1)$ ; elle est donc stationnaire. $\blacksquare$

Remarques¶

Remarque. Pour tout entier impair $m > 0$, le $m$-uplet $(2, 2^2, \ldots, 2^{m-1}, 2^m)$ suivi d'une infinité de $1$ donne une suite stationnaire vérifiant la condition de l'énoncé : le rang de stabilisation peut donc être arbitrairement grand.

Il existe des exemples plus élaborés. La solution de la partie (b) du problème 10532 de l'American Mathematical Monthly (vol. 105, n° 8, octobre 1998, p. 775–777) montre que, pour tout entier $m \geq 5$, il existe un $m$-uplet $(a_1, \ldots, a_m)$ d'entiers positifs distincts avec $\gcd(a_1, a_2) = \gcd(a_2, a_3) = \cdots = \gcd(a_{m-1}, a_m) = \gcd(a_m, a_1) = 1$ et $\frac{a_1}{a_2} + \cdots + \frac{a_{m-1}}{a_m} + \frac{a_m}{a_1}$ entier. En posant $a_{m+k} = a_1$ pour $k \geq 1$, on obtient une suite stationnaire vérifiant la condition. Exemple des auteurs : $b_1 = 2$, $b_{k+1} = 1 + b_1 \cdots b_k = 1 + b_k(b_k - 1)$, $B_m = b_1 \cdots b_{m-4} = b_{m-3} - 1$, et

\[a_1 = 1,\quad a_2 = (8B_m + 1)B_m + 8,\quad a_3 = 8B_m + 1,\quad a_k = b_{m-k} \ (4 \leq k \leq m - 1),\]

\[a_m = \frac{a_2}{2} \cdot a_3 \cdot \frac{B_m}{2} = \left(\frac{1}{2}(8B_m + 1)B_m + 4\right) \cdot (8B_m + 1) \cdot \frac{B_m}{2}.\]

On vérifie que $a_1 < a_{m-1} < a_{m-2} < \cdots < a_3 < a_2 < a_m$. Connaître cet exemple n'aide en rien à résoudre le problème.