Международная олимпиада 2025, Саншайн-Кост (Квинсленд), Австралия, 2025 год

$\mathbb{N}$ – натурал сандар жиыны. Егер барлық натурал $a$ және $b$ сандары үшін $f(a)$ саны $ b^a-f(b)^{f(a)}$ санын бөлсе, онда $f: \mathbb{N} \rightarrow \mathbb{N}$ функциясы өркөкірек деп аталады. Барлық өркөкірек функциялар үшін және барлық $n \in \mathbb{N}$ үшін $f(n) \leqslant c n$ болатындай ең кіші нақты $c$ тұрақты санын табыңыз.

Комментарий/решение

Ответ: $c=4$

$P(a;a):f(a)|a^a\Longrightarrow f(p)|p^p\longrightarrow f(p)=p^k$ для всех простых $p$

Пусть $x$ такое число что $p\nmid f(x)-x\Longrightarrow P(p;x):p|f(x)|x^p-f(x)^{f(p)}\Longrightarrow x-f(x)\equiv 0 \pmod p$ противоречие. Значить $f(p)=1$

$1)a=2k+1:$ Предположим, что простое число $p\equiv 1 \pmod 2$ делитель числа $f(a)$. По Дирихле возьмём простое число $q$ такое, что $q$ — первообразный корень по модулю $p\Longrightarrow P(a,q):p|f(a)|q^a-1\Longrightarrow p-1|a$ но $p-1\equiv 0 \pmod 2$ противоречие. Значить $f(2k+1)=1;

$2)a=2k:$ Пусть $p\equiv 1 \pmod 2$ и делитель числа $f(a)\Longrightarrow p|f(a)|p^a-1$ противоречие. Значить $f(a)=2^c$

$P(a;3):f(a)|3^a-1\Longrightarrow V_2(f(a))\le V_2(3^a-1)=2+V_2(a)\Longrightarrow f(a)=2^c\le 2^{2+V_2(a)}=4a\Longrightarrow f(n)\le 4n\blacksquare$

Следующие факты довольно простые и легко доказываются:

$\bullet$ $f(a) \mid a^a$ и $\forall$ $p \in \mathbb{P}$ существует $\alpha \in \mathbb{N}$ что $f(p)=p^{\alpha}$

$\bullet$ Если $f(p)=1$, то $f(p^k)=1$ для любого $k \in \mathbb{N}$

$\bullet$ Если $p \mid f(p)$, то $p \mid f(p^k)$

1)$\exists$ $p\in \mathbb {P}$: $f(p)=1$.

Если количество простых чисел $q$ что $q \mid f(q)$ бесконечно, тогда подставим $a=q$ достаточно большое простое с таким свойством и $b=p$:

$p^{q}-1 \equiv p-1 \pmod{q}$, или $p=1$ что невозможно.

Значит с какого то момента для всех $p\in \mathbb{P}:$ $f(p^k)=1$

Теперь допустим существует простое $p\geq3$ что $p\mid f(p)$:

$p\mid f(p)\mid q^p-1$, для очень больших простых $q$.

Или $q\mid p-1$, но по Теореме Дирихле мы могли выбрать $p \equiv 2 \pmod{q}$. Значит $f(q^k)=1$ для любого $q \in \mathbb{P}$ кроме 2.

Если число $f(a)$ делится на какое-то простое не равно 2 (пусть это $r$), для какого-то $a$ натурального которое не равно степени двойки; тогда при $b=r$:

$r \mid f(a) \mid r^a-1$, противоречие. Значит $f(a)=2^k$, где $k\in \mathbb {N_0}$ для всех $a \in \mathbb{N}$. (Для $a$ нечетных очевидно $f(a)=1$).

Так как $2^k \mid 3^a-1$, то по $LTE$, $k\leq $ $\nu_2(a)$ $+$ $2$.

Значит $f(a)\leq4a$, для $a≠2^k$.

Для $a=2^k$:

$f(a)=2^{l} \mid 3^{a}-1$. Или $l\leq k+2$.

Значит $f(a) \leq 4a$, $\forall$ $a \in \mathbb{N}$. Причем существует пример при котором $f(a)=4a$ для какого-то $a$.

2) $p \mid f(p)$, $\forall p\in \mathbb{P}$.

Пусть $f(p)=p^t.$ Тогда:

$p\mid f(p) \mid b^p-f(b)^{p^t}$.

$b^p-f(b)^{p^t} \equiv b-f(b) \pmod{p}$. Тогда при достаточно больших $p$, $b-f(b)=0$. Отсюда $f(x)=x$. Или $c=1$.

Значит минимальный такой $c$ равно 4.