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$