Processing math: 7%

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


Найдите все пары простых чисел (p,q) для которых число 1+pqqpp+q также простое число. ( Albania )
посмотреть в олимпиаде

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

  5
4 года 2 месяца назад #

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

Допустим, что 1+pqqpp+q=r, тогда

pqqp=(r1)(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.

  1
3 года 8 месяца назад #

В конце можно так: 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} противоречие

пред. Правка 5   7
2 года 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   3
2 года 1 месяца назад #

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