Shortlist 2025, N3¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : Lithuania
Concepts : Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE · Invariants et monovariants · Descente infinie et Vieta jumping
Solution officielle : Shortlist officielle 2025 (avec solutions), section N3 (livret PDF)
Problème 4 de l'OIM 2025
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2025, où il était le problème 4 (jour 2).
Énoncé¶
An infinite sequence \(a_1, a_2, \ldots\) consists of positive integers, each of which has at least four positive divisors. For each \(n \geq 1\), \(a_{n+1}\) is the sum of the three largest proper divisors of \(a_n\).
Determine all possible values of \(a_1\).
A proper divisor of a positive integer \(N\) is a divisor of \(N\) other than \(N\).
Indices : les idées clés
- Descente infinie : si un terme est impair, ou non divisible par \(3\), la suite décroît strictement à partir de là, ce qui est impossible.
- Congruences : un calcul modulo \(3\) montre que « non divisible par \(3\) » se transmet d'un terme au suivant.
- Valuations p-adiques : \(\nu_2(a_n)\) est une suite décroissante d'entiers naturels, donc stationnaire.
- Invariants et monovariants : \(a_n\) croît tandis que \(\nu_2(a_n)\) décroît ; la suite devient constante, puis on remonte jusqu'à \(a_1\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2025 (une solution et deux remarques).
Solution¶
Réponse : les valeurs possibles de \(a_1\) sont les entiers de la forme \(a_1 = 12^M \cdot 6N\), où \(M\) et \(N\) sont des entiers naturels avec \(N \geq 1\) et \(\gcd(N, 10) = 1\).
Dans toute la suite, « diviseur » signifie diviseur positif. Notons \(d_i(a)\) le \(i\)-ème plus grand diviseur strict de l'entier \(a\).
Tous les termes sont pairs. Sinon, si \(a_n\) est impair pour un certain \(n\), ses diviseurs sont tous impairs, donc
Comme \(a_{n+1}\) est la somme de trois diviseurs impairs, il est aussi impair. On obtient une suite infinie strictement décroissante d'entiers positifs : contradiction (descente infinie).
Si \(a_n\) n'est pas divisible par \(3\), alors \(a_{n+1}\) non plus. Distinguons deux cas.
-
Si \(4 \mid a_n\), alors \(d_1(a_n) = \frac{a_n}{2}\), \(d_2(a_n) = \frac{a_n}{4}\) et
\[a_{n+1} = \frac{a_n}{2} + \frac{a_n}{4} + d_3(a_n) = 3 \cdot \frac{a_n}{4} + d_3(a_n) \equiv d_3(a_n) \not\equiv 0 \pmod 3.\] -
Si \(4 \nmid a_n\), soit \(p\) le plus petit diviseur premier impair de \(a_n\). Alors \(d_1(a_n) = \frac{a_n}{2}\) est impair, \(d_2(a_n) = \frac{a_n}{p}\) est pair, et \(d_3(a_n) = a_{n+1} - d_1(a_n) - d_2(a_n)\) est impair (car \(a_{n+1}\) est pair). Donc \(\frac{a_n}{d_3(a_n)}\) est le deuxième plus petit diviseur pair de \(a_n\), c'est-à-dire \(2p\), et
\[a_{n+1} = \frac{a_n}{2} + \frac{a_n}{p} + \frac{a_n}{2p} = 3 \cdot \frac{a_n}{2p} + \frac{a_n}{2} \equiv \frac{a_n}{2} \not\equiv 0 \pmod 3.\]
Ainsi, si \(a_n \not\equiv 0 \pmod 3\) pour un certain \(n\), alors \(a_{n+1} \not\equiv 0 \pmod 3\). Dans ce cas,
et l'on obtient encore une suite infinie strictement décroissante d'entiers positifs : contradiction.
Conséquence. Tous les termes sont divisibles par \(6\). Donc, pour tout \(n\),
Il y a trois cas pour chaque \(a_n\) :
- Si \(4 \mid a_n\), alors \(a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{4} = \frac{13}{12}\, a_n\).
- Si \(5 \mid a_n\) mais \(4 \nmid a_n\), alors \(a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{5} = \frac{31}{30}\, a_n\). Mais alors \(a_{n+1}\) est impair, donc ce cas ne se produit jamais.
- Si \(4 \nmid a_n\) et \(5 \nmid a_n\), alors \(a_{n+1} = \frac{a_n}{2} + \frac{a_n}{3} + \frac{a_n}{6} = a_n\).
Dans tous les cas, \(a_{n+1} \geq a_n\) et \(\nu_2(a_{n+1}) \leq \nu_2(a_n)\). Comme \((\nu_2(a_n))\) est une suite décroissante d'entiers naturels (valuation 2-adique), elle est stationnaire. Comme \(\nu_2(a_{n+1}) = \nu_2(a_n)\) seulement dans le cas 3, à partir d'un certain rang seul le cas 3 s'applique. La suite est donc stationnaire : il existe \(L\) tel que \(a_L = a_{L+1} = \cdots\). Cette valeur finale \(a_L\) est divisible par \(6\), mais pas par \(4\) ni par \(5\) : \(a_L = 6K\) avec \(K > 0\) premier avec \(10\).
En prenant \(L\) minimal, on a \(\nu_2(a_1) > \nu_2(a_2) > \cdots > \nu_2(a_L) = 1\). Donc pour \(1 \leq n \leq L - 1\), c'est le cas 1 qui s'applique : \(4 \mid a_n\) et \(a_{n+1} = \frac{13}{12}\, a_n\). Par conséquent
est de la forme \(a_1 = 12^M \cdot 6 \cdot N\), avec \(M = L - 1 \geq 0\), \(N = K/13^{L-1} > 0\) entier premier avec \(10\), comme annoncé.
Réciproquement, pour un tel \(a_1\), on a \(a_k = 12^{M+1-k} \cdot 13^{k-1} \cdot 6N\) pour \(1 \leq k \leq M + 1\), puis
et tous ces termes ont bien au moins quatre diviseurs. \(\blacksquare\)
Remarques¶
Remarque 1 (une fonction décroissante). Une autre façon de montrer que la suite est stationnaire consiste à trouver une fonction \(f\) telle que \(f(a_n)\) décroisse. Par exemple, la fonction complètement multiplicative \(f : \mathbb{Z}_{>0} \to \mathbb{R}_{>0}\) définie sur les nombres premiers par
avec \(\varepsilon > 0\) petit. On vérifie que le rapport \(f(a_{n+1})/f(a_n)\) n'est jamais supérieur à \(1\). L'ensemble des valeurs de \(f\) est bien ordonné, donc \(f(a_n)\) est stationnaire, et \(a_n\) aussi. On remonte ensuite jusqu'aux valeurs possibles de \(a_1\).
Remarque 2 (variante). Une autre version du problème consiste à demander seulement de prouver que la suite est stationnaire, au lieu de trouver toutes les valeurs de \(a_1\).