Shortlist 2022, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Croatia
Concepts : Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 62 (page 64 du PDF)
Énoncé¶
Let \(a > 1\) be a positive integer, and let \(d > 1\) be a positive integer coprime to \(a\). Let \(x_1 = 1\) and, for \(k \geq 1\), define
Find the greatest positive integer \(n\) for which there exists an index \(k\) such that \(x_k\) is divisible by \(a^n\).
Indices : les idées clés
- Majoration de la suite : on a toujours \(x_k < ad\), ce qui donne immédiatement la borne \(a^n < ad\).
- Congruences, théorèmes de Fermat et d'Euler (solution 1) : modulo \(d\), une étape montante ne change pas le reste et une étape descendante le multiplie par \(a^{-1}\).
- Inverser la récurrence (solution 2) : l'application \(x \mapsto x_{k+1}\) est une permutation d'un ensemble fini, donc la suite est périodique et repasse par \(1\) ; en remontant le temps depuis \(1\), on trouve \(a, a^2, \ldots, a^n\).
- Écriture en base \(a\) (solution 3) : la périodicité donne une égalité de développements en base \(a\) qui force \(n\) divisions consécutives.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (trois solutions).
Réponse : \(n\) est l'unique entier tel que \(d < a^n < ad\).
(Cet entier existe et est unique : les puissances de \(a\) sont séparées d'un facteur \(a\), et \(a^n \neq d\) car \(\gcd(a, d) = 1\) et \(d > 1\).)
Solution 1¶
Par une récurrence immédiate, chaque \(x_k\) est premier avec \(d\).
Majoration. Il ne peut pas y avoir plus de \(a - 1\) étapes montantes consécutives (parmi \(a\) termes consécutifs \(x, x+d, \ldots, x + (a-1)d\), l'un est divisible par \(a\), car \(d\) est inversible modulo \(a\)). Par récurrence, on obtient : \(x_k < da\) si \(x_k = x_{k-1} + d\), et \(x_k < d\) si \(x_k = x_{k-1}/a\) ou \(k = 1\). En particulier \(x_k < ad\) pour tout \(k\) ; si \(a^n\) divise un \(x_k\), alors \(a^n \leq x_k < ad\). Cela donne la borne supérieure : \(a^{n+1} > ad\) ne divise aucun terme.
Existence. La suite est bornée, à valeurs entières, et chaque terme détermine le suivant : elle est donc (à partir d'un certain rang) périodique, et les étapes montantes comme descendantes se produisent une infinité de fois. Notons \(a^{-k}\) l'inverse de \(a^k\) modulo \(d\). Une étape montante ne change pas le reste modulo \(d\) et une étape descendante le multiplie par \(a^{-1}\) ; la suite contient donc des termes congrus à \(1, a^{-1}, a^{-2}, \ldots\) modulo \(d\). Comme \(a\) est d'ordre fini modulo \(d\), le reste \(a^n\) est l'un d'eux.
Soit \(x_{k_0}\) le premier terme tel que \(x_{k_0} \equiv a^n \pmod d\). On a soit \(k_0 = 1\), soit \(x_{k_0} = x_{k_0 - 1}/a\) (un terme obtenu par une étape montante a le même reste que le précédent, qui serait apparu plus tôt). Dans les deux cas \(x_{k_0} < d < a^n < da\), et donc
Aucun élément de cet ensemble n'est divisible par \(a\) (car \(a \mid a^n\) et \(a \nmid jd\) pour \(1 \leq j \leq a-1\)) : la suite ajoute donc \(d\) à chaque étape et atteint la valeur \(a^n\) dans les \(a - 1\) étapes suivantes. \(\blacksquare\)
Note : le livret officiel écrit « \(x_{k_0} \equiv a^{-n} \pmod d\) » ; c'est le reste \(a^n\) qui est nécessaire pour l'appartenance à l'ensemble ci-dessus, et c'est ce que nous avons écrit.
Solution 2¶
Comme dans la première solution, \(x_k\) est premier avec \(d\) et \(x_k < ad\) pour tout \(k\). Posons
On a donc \(x_1 = 1\) et \(x_{k+1} = f(x_k)\).
La récurrence est inversible. Supposons \(f(x) = y\) avec \(x, y \in S\). Si \(y > d\), alors \(y - d \in S\) mais \(a y \notin S\) ; sinon, si \(y < d\), alors \(a y \in S\) mais \(y - d \notin S\). Ainsi \(f\) est une permutation de \(S\), d'inverse
Il s'ensuit que la suite est périodique (permutation d'un ensemble fini), et repasse donc une infinité de fois par la valeur initiale \(1\). Soit \(k_1 > 1\) tel que \(x_{k_1} = 1\). Comme \(a^j < d\) pour \(j < n\),
\(\blacksquare\)
Solution 3¶
Comme dans la première solution, \(x_k\) est premier avec \(d\) et \(x_k < ad\) pour tout \(k\). Il s'agit de prouver qu'il existe \(n\) indices descendants consécutifs (un indice \(k\) est descendant si \(x_k = x_{k-1}/a\)).
Posons \(m_0 = 0\), notons \(m_k\) le \(k\)-ième plus petit indice descendant, et définissons \(y_k = x_{m_k}\) (la sous-suite des termes d'indice descendant, avec \(y_0 = x_1 = 1\) par convention). Pour chaque \(k \geq 0\), on peut écrire
avec \(z_k \in \{0, 1, \ldots, a-1\}\), où \(z_k = 0\) si et seulement si \(y_k\) et \(y_{k+1}\) sont consécutifs dans la suite d'origine. Par récurrence,
Comme \((y_k)\) est bornée, elle est (à partir d'un certain rang) périodique. Considérons \(y_u = y_{u+v}\) avec \(v \geq 1\). On a
En réarrangeant :
Le membre de droite est un entier, donc \(d \mid a^v - 1\) ; en particulier \(a^v - 1 \geq d > a^{n-1}\) (car \(a^{n-1} \cdot a = a^n < ad\)), d'où \(v \geq n\). Notons \(A = z_0 + z_1 a + \cdots + z_{v-1} a^{v-1}\), de sorte que \(0 \leq A < a^v\), et le membre de droite s'écrit \(A + a^v B\) avec \(B\) entier. Comme \(0 < \frac{a^v - 1}{d} < a^v\), on a forcément \(B = 0\), donc \(A = \frac{a^v - 1}{d}\).
Comme \(d > a^n / a = a^{n-1}\), on a \(A = \frac{a^v - 1}{d} < a^{v-n+1}\). Dans l'écriture en base \(a\) de \(A\), les chiffres de \(a^{v-n+1}, \ldots, a^{v-1}\) sont donc nuls : \(z_{v-n+1} = \cdots = z_{v-1} = 0\). Ainsi les indices descendants \(m_{v-n+1}, m_{v-n+2}, \ldots, m_v\) sont consécutifs : il y a \(n\) indices descendants consécutifs dans la suite d'origine, et le terme \(x_{m_{v-n+1} - 1}\) qui précède ces \(n\) divisions est divisible par \(a^n\). \(\blacksquare\)
Note : le livret officiel écrit « le membre de gauche est strictement inférieur à \(a^{v-n}\) » et en déduit \(z_{v-n} = \cdots = z_{v-1} = 0\) ; avec \(d > a^{n-1}\), la majoration correcte est \(a^{v-n+1}\), ce qui donne \(n - 1\) chiffres nuls, soit bien \(n\) indices descendants consécutifs. Nous avons aussi détaillé pourquoi les coefficients éventuellement négatifs \(z_{j+v} - z_j\) ne gênent pas.