Наименьшее количество делителей числа p^4+4^p

[Ktina]

Какое наименьшее количество попарно различных натуральных делителей может иметь число, представимое в виде

$$p^4+4^p$$

, где $p$ - простое?
(Всероссийская олимпиада школьников, Пермский край, по мотивам)

[Shadow]

Простое быть не может, но может быть произведением двух простых. Значит, четыре "попарно различных" натуральных делителей. Или я чего-то не понял?

-- 12.08.2016, 11:20 --

Да, и квадрат простого быть не может. Тоесть, 25 быть не может

[Ktina]

Shadow
Верно!

Квадрат простого быть не может, по модулю 3, так как $4^p$ всегда даёт остаток 1 при делении на 3, а $p^4$ - тоже, при $p>3$.

[sa233091]

а почему не может быть простое?

[cmpamer]

sa233091 в сообщении #1145790 писал(а):

а почему не может быть простое?

Оно не может быть простым даже если p нечётное, не кратное пяти. Для ответа на вопрос "почему?", надо исходное равенство "промодулировать" по модулю 5. Тривиальная задача.
Надеюсь, не для старшеклассников такие задачи выставляют на олимпиадах?

[maxal]

cmpamer в сообщении #1145846 писал(а):

Оно не может быть простым даже если p нечётное, не кратное пяти. Для ответа на вопрос "почему?", надо исходное равенство "промодулировать" по модулю 5. Тривиальная задача.

Или так:

$$p^4 + 4^p = p^4 + 2\cdot p^2\cdot 2^p + (2^p)^2 - 2p^2\cdot 2^p = (p^2 + 2^p)^2 - (p2^{(p+1)/2})^2 = (p^2 + 2^p + p2^{(p+1)/2})\cdot (p^2 + 2^p - p2^{(p+1)/2}).$$

[cmpamer]

maxal в сообщении #1147360 писал(а):

Или так:

$$p^4 + 4^p = p^4 + 2\cdot p^2\cdot 2^p + (2^p)^2 - 2p^2\cdot 2^p = (p^2 + 2^p)^2 - (p2^{(p+1)/2})^2 = (p^2 + 2^p + p2^{(p+1)/2})\cdot (p^2 + 2^p - p2^{(p+1)/2}).$$

Можно и так, если и дальше усиливать условия задачи (включить случай кратности пяти). Но если ещё дальше усиливать - заменить четвёрку всяким большим 3 простым без единицы - то так шустро уже не получится. Возможно, последняя "редакция" превратила бы эту задачку в реально олимпиадную...

[sa233091]

cmpamer в сообщении #1148253 писал(а):

maxal в сообщении #1147360 писал(а):

Или так:

$$p^4 + 4^p = p^4 + 2\cdot p^2\cdot 2^p + (2^p)^2 - 2p^2\cdot 2^p = (p^2 + 2^p)^2 - (p2^{(p+1)/2})^2 = (p^2 + 2^p + p2^{(p+1)/2})\cdot (p^2 + 2^p - p2^{(p+1)/2}).$$

Можно и так, если и дальше усиливать условия задачи (включить случай кратности пяти). Но если ещё дальше усиливать - заменить четвёрку всяким большим 3 простым без единицы - то так шустро уже не получится. Возможно, последняя "редакция" превратила бы эту задачку в реально олимпиадную...

Почему? Все так-же есть малая теорема Ферма и все легко <<модулируется>>.