24-я Балканская математическая олимпиада среди юниоров. Греция, 2020 год

Найдите все пары простых чисел $(p,q)$ для которых число $1 + \frac{p^q - q^p}{p + q} $ также простое число. ( Albania )

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

Ответ: $(p,q)=(2,5).$

Допустим, что $1 + \dfrac{p^q - q^p}{p + q}=r,$ тогда

$$ p^q-q^p=(r-1)(p+q).$$

Из Малой Теоремы Ферма получаем, что $$-q\equiv p^q-q^p\equiv (r-1)(p+q)\equiv (r-1)q \pmod p\implies qr\equiv 0\pmod p.$$ Очевидно, что $q\neq p,$ откуда $r=p.$

Также из Малой Теоремы Ферма $$p\equiv p^q-q^p\equiv (p-1)(p+q)\equiv(p-1)p\pmod q\implies (p-2)p\equiv 0\pmod q,$$

значит $q\mid p-2.$ Если $p=2,$ то $$2^q=q^2+q+2,$$

но для любого натурального $q\ge 7,$ верно неравенство $2^q>q^2+q+2.$(легко доказать индукцией по $q$) Поэтому $q=2,3,5$ из которых подходит лишь $q=5.$

Если $p>2,$ то $q\mid p-2,$ откуда $$i)\quad q\ge 3$$ $$ii)\quad p>p-2\ge q,$$

но тогда $p^q-q^p<0,$ (поскольку для любых действительных $x>y>e,$ верно неравенство $x^y<y^x$) что конечно невозможно, так как $(p-1)(p+q)>0.$

В конце можно так: $p^q-q^p$ делится на $p-1$, $p^q-q^p \equiv 1-q^p = 0 \pmod {p-1}, q^p \equiv 1 \pmod {p-1},$ если $\alpha$ - показатель числа $q$ по $mod (p-1)$, то либо $\alpha=1$, но тогда $q \geq p$, противоречие, либо $\alpha=p$. Pассмотрим число $\varphi(p-1)$, очевидно, что $\varphi(p-1)<p$, но, по теореме Эйлера, $q^{\varphi(p-1)} \equiv 1 \pmod {p-1}$ противоречие

$p=q$ бесиыслено разбирать тогда разберем вариант где все нечетные тогда заметим одну вещь что если мы обе стороны умножим на $p+q$ тогда $p+q+p^q-q^p=a(p+q) $ заметим что это можно записать так $p(p^{q-1}+1)-q(q^{p-1}-1)$ по малой теореме ферма заметим что $q^{p-1}-1\equiv 0 \pmod {p}$ но тогда $a$ должно делиться на $p$ но тогда $a=p$ что невозможно при нечетных тогда одно из них обязательно $=2$ заметим что тогда $p=2$ при $q\geq 5 $ проверяем где $p=2,q=3 $ нету вариантов и $p=3,q=2$ нету вариантов тогда единственный вариант $p=2,q=q$ разбираем его $2(2^{q-1}+1)-q(q-1)=a(2+q)$ тогда $a$ четный и т.к. $a$ это простое $a=2$ то $q=5$ тогда $2^q-q^2=2+q$ заметим что $q=5$ единственное решение т.к. если $q>7$ то $2^q-q^2=2+q$ это легко замечается если $q=7$ то $2^7-7^2>2+7$ на $70$ если $q=11$ то на $1914$ $q=13$то на$8008$ и так далее будет расти так что единственный ответ $2^5-5^2=5+2$

$2^q>2q^2=q^2+q^2>q^2+q+2$,Это работает когда $q\geq 7$

$1 + \frac{p^q - q^p}{p + q} = k$, где $k$ — простое число.

Умножим на $p + q$:

$p + q + p^q - q^p = k(p + q)$

$p^q - q^p = (k - 1)(p + q)$

Рассмотрим сравнения по модулю:

$p^q - q^p \equiv -q^p \pmod p$

$p^q - q^p \equiv p^q \pmod q$

Для правой части:

$(k - 1)(p + q) = kp + kq - p - q \equiv kq - q \equiv q(k - 1) \pmod p$

$(k - 1)(p + q) = kp + kq - p - q \equiv kp - p \equiv p(k - 1) \pmod q$

По Малой теореме Ферма:

$q^p \equiv q \pmod p$

$p^q \equiv p \pmod q$

Подставляя это, получаем условия делимости:

$q(k - 1) \equiv -q \pmod p \implies qk \equiv 0 \pmod p$

$p(k - 1) \equiv p \pmod q \implies pk \equiv 2 \pmod q$

Отсюда:

$q \mid k - 2$

$p \mid k \implies p = k$ (так как $p$ и $k$ простые)

Значит, $q$ — единственный простой делитель числа $k - 2 = p - 2$. Т.к. $p - 2$ нечётное, $q = 2$ невозможно, поэтому $q \ge 3$ и $p = k$.

Возвращаемся к уравнению:

$(p - 1)(p + q) = p^q - q^p$

Пусть $p > q \ge 3$. По модулю 2:

$p^q - q^p \equiv 1 - 1 \equiv 0 \pmod 2$

Так как $p - 1$ чётное, левая часть $(p - 1)(p + q)$ тоже чётна.

Рассмотрим функцию $f(x) = \frac{\ln x}{x}$ на промежутке $[3; +\infty)$:

$f'(x) = \frac{1 - \ln x}{x^2}$

Для всех $x > e$ выполнено $1 - \ln x < 0$, следовательно $f'(x) < 0$ и функция $f(x)$ убывает.

Так как $p > q \ge 3 > e$, то:

$f(p) < f(q) \implies \frac{\ln p}{p} < \frac{\ln q}{q} \implies q \ln p < p \ln q \implies \ln(p^q) < \ln(q^p) \implies p^q < q^p$

Отсюда $p^q - q^p < 0$.

Однако левая часть $(p - 1)(p + q) > 0$. Получаем противоречие.

Значит, $p > q \ge 3$ невозможно. Из делимости $q \mid p - 2$: так как $p - 2 < q$ и $p$ простое, получаем $p - 2 = 0 \implies p = 2$, откуда $k = 2$.

Подставляем $p = 2$ в исходное уравнение:

$1 + \frac{2^q - q^2}{q + 2} = 2 \implies 2^q = q^2 + q + 2$

При $q = 5$ равенство выполняется ($32 = 25 + 5 + 2$).

Докажем по индукции, что при $q \ge 6$ левая часть строго больше правой:

($q = 6$): $2^6 = 64 > 44$.

Индукционный переход: пусть для $k \ge 6$ выполнено $2^k > k^2 + k + 2$. Тогда для $k + 1$:

$2^{k+1} = 2 \cdot 2^k > 2(k^2 + k + 2) = 2k^2 + 2k + 4$

Сравним с правой частью при $q = k + 1$: $(k+1)^2 + (k+1) + 2 = k^2 + 3k + 4$.

Разность:

$(2k^2 + 2k + 4) - (k^2 + 3k + 4) = k^2 - k = k(k - 1) > 0$ (при $k \ge 6$).

Значит, $2^{k+1} > (k+1)^2 + (k+1) + 2$. Ч.Т.Д.

Единственное решение в простых числах: $(p; q) = (2; 5)$.