Международная олимпиада 2022, Осло, Норвегия, 2022 год

Найдите все тройки $(a,b,p)$ целых положительных чисел, такие что число $p$ простое и $a^p=b!+p.$

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

$a^p-p \equiv a,0 \pmod {p} = b! \equiv a,0 \pmod {p}$ по МТФ

пусть $a^p-p \equiv a \pmod {p} = b! \equiv a \pmod {p}$ тогда $b<p$

если $a>b$ то $a^p-p>b!$ поэтому $b>a$ тогда $b!\equiv 0 \pmod {a}=a^p\equiv 0 \pmod {a} -p\equiv p\pmod {a}$ но $p>a$ значит $p \ne\equiv 0 \pmod {a}$

пусть $a^p\equiv 0 \pmod {p} \Rightarrow b!\equiv 0 \pmod {p}$

разбирая $p=2,p=3 $ выходят такие ответы $(a,b,p)=(2,2,2),(3,4,3)$

пусть $p>3$ тогда $b>p>3$

Докажем что $a=p$ тогда $a=px$ где $x\geq 3$ $p(p^{p-1}x^p-1)=b!$ но тогда $(p^{p-1}x^p-1)\equiv 0 \pmod {2,3,4,5....p-1,p+1....,p+k}$ но если т.к. $x\geq 3$ то $(p^{p-1}x^p-1)\equiv 0 \pmod {2,3,4,5....p-1,p+1....,p+k}$ не делится на $x$ а должно т.к. $b>x$ потому что если $a>b $ то $px>2p>b>p$ где $x\geq 3$ но тогда $p^px^p-p>b!$т.к.$\Rightarrow \dfrac {2xp}{3}>b$,$\dfrac {(2xp)^p}{(3)^p}>b^p$,$x^pp^p-p>\dfrac {(2xp)^p}{(3)^p}>b^p$ так что $b>a$ $\Rightarrow a=p$ теперь надо доказать что при $p>3$ решений нету

помогите добить задачу я только до этого смог дойти

(3 дня решал только до этого дошел)

добивка $p>5$$p^p-p\equiv 0 \pmod{2^{p-1}}$ или меньше больше не может но заметим что при $b>5$ у него $b!=2^kx$,$k\geq 2^p$$\Rightarrow b\leq4$

Разбором можно найти решения $(2,2,2)$, $(3,4,3)$. Для $p=2, 3$ разбором находим что других решений для $b<2p$ нет. Для любого $p$ и $b \geq 2p$, $a^p$ делится на $p$ и не делится на $p^2$ - решений нет.

Покажем что для $p \geq 5$ решений нет. Для $b=1$ решений нет.

Разберем $1<b<p$, тогда существует наименьшее нечетное простое $q$ что $q | b!+p$. Выполняется $q>b$ и $q \neq p$. Тогда верно неравенство: $b!+p \geq q^p$

Для $q>p$:

$$b! \geq q^p-p > q^p-q > (q-1)^p \geq b^p > b!$$

Для $q<p$ используется $q^p>p^q$:

$$b!+p \geq q^p > p^q \rightarrow b! >p^q-p>(p-1)^q \geq b^q > b!$$

Разберем тогда $p \leq b <2p$, естественно $p|a$.

$$a^p=b!+p \leq (2p-1)!+p = p \times (2p-1)(1) \times ... \times (p+1)(p-1)+p < (p^2-1)^{p-1} \times p+p < p^{2p-2} \times p + p < p^{2p}$$

Тогда $\frac{a}{p}<p \leq b$.

$\frac{a}{p}$ делит $b!$, $a^p$, и $p$, получаем $a=p$.

Допустим что $b \geq p+1 \geq 6$:

$$2 \times \dfrac{(p+1)}{2} \times (p+1)=(p+1)^2 | b! = p^p-p$$

$$p+1 | \dfrac{p^p-p}{p+1} \Leftrightarrow \dfrac{p^p+1}{p+1}-1=(p^{p-1}-p^{p-2}+...-p+1)-1 \equiv 0 \pmod {p+1}$$

Но при этом:

$$p^{p-1}-p^{p-2}+...-p^{1} \equiv (+1)-(-1)+(+1)-...-(-1) \equiv p-1 \pmod {p+1}$$

Значит остается $b=p$: $p!+p=p^p$

Что индукцией можно показать что $p^p$ больше чем $p!+p$ для $p \geq 5$.

С решение этой задачи помогали:

Амангелді Бейбарыс, Алмасбекұлы Абдуллаһ, Қанатұлы Нұрасыл, Рамазанов Адильби, Есенгелді Аман, Алиасқар Султанәлі, Рахымұлы Ахмет, Аманқұл Ерасыл.

Решение:

$b=1 \rightarrow p+1=a^p \rightarrow a=(p+1)^{\frac{1}{p}}<e<3 \rightarrow a=1,2$. Очевидно $a=1$ не подходит. Если $a=2$ тогда $2^p = 1 (mod p)$ и из МТФ $2^{gcd(p,p-1)} = 2 = 1 (mod p)$ что невозможно, значит $b \geq 2$ .

Пусть $a>b$ и если $2 \leq b < p$ тогда:

$b!+p=a^p < b^p+p$ что невозможно $\rightarrow p | b! \rightarrow p | a$ .

Заметим $V_p(a^p-p)=1=V_p(b!) \rightarrow p \leq b <2p$.

Пусть $a=pk$ тогда:

$(kp)^p=b!+p \leq (2p-1)!+p < (2p-1)! \cdot p = \prod_{i=0}^{p-1} (p+i)(p-i) < (p^2)^p \rightarrow k < p$. Также очевидно что $k < b$. Возьмем произвольный простой делитель $k$ как $q$, тогда $q | b!+p \rightarrow q | p \rightarrow q=1$ значит $k=1$ и $a=p$.

$p^p-p=b!$

$V_2(LHS)=V_2(p^{p-1}-1)=V_2(p+1)+2V_2(p-1)-1.$

$V_2(RHS)=V_2(b!) \geq V_2(p+1!)$ $\Longrightarrow$

$2V_2(p-1) > V_2(p!)$

Если $p \geq 5$ тогда очевидно что $V_2(p!) \geq 2V_2(p-1)$. Значит $p=2,3$ и можно легко найти все решение:

$(a,p,b)=(2,2,2);(3,3,4)$.

P.S: Случай $b \geq a$ был не разобран так как если это так то следует что $a=p$.