Aller au contenu

Shortlist 2025, N7

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

Concepts : Congruences, théorèmes de Fermat et d'Euler · Ordre d'un élément et racines primitives · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2025 (avec solutions), section N7 (livret PDF)

Problème 3 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 3 (jour 1).

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Let \(\mathbb{Z}_{>0}\) denote the set of positive integers. A function \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) is said to be bonza if

\[f(a) \text{ divides } b^a - f(b)^{f(a)}\]

for all positive integers \(a\) and \(b\).

Determine the smallest constant \(c\) such that \(f(n) \leq cn\) for any bonza function \(f\) and any positive integer \(n\).

Indices : les idées clés
  • Substitution \(b = a\) : \(f(a) \mid a^a\), donc \(f(p)\) est une puissance de \(p\) et tout facteur premier de \(f(n)\) divise \(n\).
  • Petit théorème de Fermat : si \(f(p) \neq 1\), alors \(p \mid n - f(n)\) ; on en déduit \(f(p) = 1\) pour tout premier impair \(p\), puis que \(f(n)\) est une puissance de \(2\).
  • Ordre de 5 modulo \(2^z\) : avec \(b = 5^c\) bien choisi, on obtient \(2^z \mid 5^{2^x} - 1\).
  • Valuation 2-adique et LTE : \(\nu_2\big(5^{2^x} - 1\big) = x + 2\), d'où \(f(n) \leq 4n\).
  • Construction : \(f(4) = 16\), \(f = 2\) sur les autres pairs, \(f = 1\) sur les impairs.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2025 (une solution et trois remarques).

Solution

Réponse : la plus petite constante est \(c = 4\).

Majoration : \(c = 4\) convient. La fonction \(f(n) = n\) est solution et vérifie trivialement \(f(n) \leq 4n\). On suppose désormais qu'il existe un entier \(m\) tel que \(f(m) \neq m\).

En prenant \(b = a\), on obtient \(f(a) \mid a^a\) pour tout \(a\). En particulier, si \(p\) est premier, \(f(p)\) est une puissance de \(p\).

Affirmation. Si \(p\) est premier et \(f(n) \neq n\), alors \(f(p) = 1\) ou \(p \mid n - f(n)\).

Preuve. Prenons \(a = p\) et \(b = n\). Si \(f(p) \neq 1\), comme \(f(p)\) est une puissance de \(p\), on a \(p \mid f(p)\) et donc

\[p \mid n^p - f(n)^{f(p)}.\]

Par le petit théorème de Fermat, \(n^p \equiv n \pmod p\). Comme \(f(p)\) est une puissance de \(p\), on a aussi \(f(n)^{f(p)} \equiv f(n) \pmod p\) (en appliquant Fermat de façon répétée). Donc \(p \mid n - f(n)\). \(\square\)

Si \(q\) est un nombre premier avec \(q > |m - f(m)|\), alors \(q \nmid m - f(m)\) (car \(m - f(m) \neq 0\)), et l'affirmation avec \(p = q\) et \(n = m\) donne \(f(q) = 1\). Autrement dit, \(f(q) = 1\) pour tout premier \(q\) assez grand.

Montrons maintenant que \(f(p) = 1\) pour tout premier impair \(p\). Pour un premier \(q\) assez grand, \(f(q) = 1 \neq q\), donc l'affirmation avec \(n = q\) donne \(f(p) = 1\) ou \(f(q) \equiv q \pmod p\), c'est-à-dire \(q \equiv 1 \pmod p\). Si de plus \(q \not\equiv 1 \pmod p\), on peut conclure \(f(p) = 1\). Or il existe une infinité de nombres premiers \(q\) tels que \(q \not\equiv 1 \pmod p\) : cela découle immédiatement du théorème de Dirichlet sur les nombres premiers en progression arithmétique, ou se démontre directement (voir la remarque 2). En prenant un tel \(q\) avec \(q > |m - f(m)|\) et \(q \not\equiv 1 \pmod p\), on conclut que \(f(p) = 1\).

Pour tout \(n\), on a \(f(n) \mid n^n\), donc tout facteur premier de \(f(n)\) divise \(n\). Mais si \(q\) est un facteur premier impair de \(n\), en prenant \(a = n\), \(b = q\) et en utilisant \(f(q) = 1\), l'énoncé donne

\[f(n) \mid q^n - 1,\]

donc \(q\) ne divise pas \(f(n)\). Ainsi le seul facteur premier possible de \(f(n)\) est \(2\) : pour tout \(n\), \(f(n)\) est une puissance de \(2\). De plus, si \(n\) est impair, \(f(n) = 1\) (car \(f(n) \mid n^n\) est impair).

Soit \(a = 2^x y\) avec \(x \geq 0\) et \(y\) impair, et \(f(a) = 2^z\) avec \(z \geq 0\). Montrons que \(z \leq x + 2\), ce qui donne \(f(a) \leq 2^{x+2} \leq 4a\). Pour tout \(b\) impair, on a \(f(b) = 1\), et l'énoncé donne

\[2^z \mid b^{2^x y} - 1, \quad \text{c'est-à-dire} \quad b^{2^x y} \equiv 1 \pmod{2^z}.\]

Comme \(\varphi(2^z)\) est une puissance de \(2\) et \(y\) est impair, il existe un entier \(c \geq 1\) tel que \(yc \equiv 1 \pmod{\varphi(2^z)}\). Avec \(b = 5^c\), le théorème d'Euler donne

\[1 \equiv b^{2^x y} = \big(5^{yc}\big)^{2^x} \equiv 5^{2^x} \pmod{2^z}.\]

(Autrement dit, l'ordre de \(5\) modulo \(2^z\) divise \(2^x\).) Or, en factorisant de façon répétée des différences de carrés,

\[5^{2^x} - 1 = \big(5^{2^{x-1}} + 1\big)\big(5^{2^{x-2}} + 1\big) \cdots \big(5^2 + 1\big)(5 + 1)(5 - 1).\]

Comme chaque \(5^{2^k} + 1 \equiv 2 \pmod 4\), on a \(\nu_2\big(5^{2^k} + 1\big) = 1\), et donc (valuation 2-adique)

\[\nu_2\big(5^{2^x} - 1\big) = x \cdot 1 + 2 = x + 2.\]

Comme \(2^z \mid 5^{2^x} - 1\), on obtient \(z \leq x + 2\). Ainsi \(f(n) \leq 4n\) pour tout \(n\).

Optimalité : on ne peut pas faire mieux que \(c = 4\). Définissons

\[f(n) = \begin{cases} 1 & \text{si } n \text{ est impair,} \\ 2 & \text{si } n \text{ est pair et } n \neq 4, \\ 16 & \text{si } n = 4. \end{cases}\]

Vérifions la condition directement, selon \(a\).

  • Si \(a\) est impair, \(f(a) = 1\) et la condition \(f(a) \mid b^a - f(b)^{f(a)}\) est immédiate.
  • Si \(a\) est pair et \(a \neq 4\), alors \(f(a) = 2\) et la condition devient \(2 \mid b^a - f(b)^2\). Par construction, \(b\) et \(f(b)\) ont la même parité, donc la condition est vérifiée.
  • Si \(a = 4\), alors \(f(a) = 16\) et la condition devient \(16 \mid b^4 - f(b)^{16}\). Si \(b\) est pair, \(f(b)\) l'est aussi, donc \(b^4\) et \(f(b)^{16}\) sont tous deux divisibles par \(16\). Si \(b\) est impair, \(b^4 - f(b)^{16} = b^4 - 1 = (b-1)(b+1)(b^2+1)\). Les trois facteurs sont pairs, et \(b - 1\), \(b + 1\) diffèrent de \(2\), donc l'un d'eux est divisible par \(4\). Ainsi \(16 \mid b^4 - 1\).

Cette fonction est donc bonza, et comme \(f(4) = 16 = 4 \cdot 4\), la constante \(c = 4\) est optimale. \(\blacksquare\)

Remarques

Remarque 1 (toutes les fonctions bonza). Les solutions de l'équation fonctionnelle sont : \(f(n) = n\) pour tout \(n\) ; \(f(n) = 1\) pour tout \(n\) ; et

\[f(n) = \begin{cases} 1 & \text{si } n \text{ est impair,} \\ 2^{g(n)} & \text{si } n \text{ est pair,} \end{cases}\]

où \(1 \leq g(2) \leq 2\) et \(1 \leq g(n) \leq \nu_2(n) + 2\) pour les autres \(n\) pairs.

Remarque 2 (sans le théorème de Dirichlet). Pour tout premier impair \(p\), il existe une infinité de premiers \(q \not\equiv 1 \pmod p\). Supposons par l'absurde qu'il n'y en ait qu'un nombre fini, et soit \(N\) leur produit. Considérons \(pN - 1\). On a \(\gcd(pN - 1, q) = 1\) pour tout premier \(q \not\equiv 1 \pmod p\), donc tous les facteurs premiers de \(pN - 1\) sont congrus à \(1\) modulo \(p\). Il s'ensuit que \(pN - 1 \equiv 1 \pmod p\), donc \(2 \equiv 0 \pmod p\) : contradiction.

Remarque 3 (par LTE). L'égalité \(\nu_2\big(5^{2^x} - 1\big) = x + 2\) découle aussi du lemme LTE (cas \(p = 2\), exposant pair) :

\[\nu_2\big(5^{2^x} - 1\big) = \nu_2(5 - 1) + \nu_2(5 + 1) + \nu_2(2^x) - 1 = 2 + 1 + x - 1 = x + 2.\]