Областная олимпиада по математике, 2025 год, 11 класс

Найдите все такие пары $(p,q)$ простых чисел, что $p>q-2$ и $7^{pq}-5^p$ делится на $pq$. ( С. Мейрам )

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

Заметим,что $pq$ кратно $p$, тогда $p|7^{pq}-5^p$ и по Теореме Ферма получим $p|7^q-5$. $pq$ также кратно $q$, откуда снова по Теореме Ферма получим $q|7^p-5^p$. По малой Теореме Ферма выполняется $q|7^{q-1}-5^{q-1}$. Следовательно, $$q|gcd(7^p-5^p,7^{q-1}-5^{q-1})=7^{gcd(p,q-1)}-5^{gcd(p,q-1)}.$$

Понятно,что $gcd(p,q-1)=1$ либо $p$ ; в первом случае применяя первую делимость получим,что $p|44$, откуда $p=2,11$, а во втором случае воспользовавшись неравенством из условий выйдет, что $p=q-1$, что равносильно к паре решений $p=2$ и $q=3$ используя чётность.

$7^{pq}-5^p\equiv 7^p-5^p\equiv 0,$ пусть $g$ - первообразный корень $\text{mod}$ $q$, тогда $g^{p\alpha}\equiv g^{p\beta} \Leftrightarrow q-1|p(\alpha-\beta)$, откуда $(p,q)=(2,3)$ или $q=2$. $49^p-5^p\equiv 44\equiv 0\Leftrightarrow p|44$, а значит $(p, q)= (2,2), (11,2)$.