Доказать, что 4^4^4^4-3 - составное число

[Ktina]

Доказать, что

$$4^{4^{4^4}}-3$$

- составное число.

С этой несложной для человека задачей не удалось справиться даже Альфочке:
http://www.wolframalpha.com/input/?i=is ... E4-3+prime

[atlakatl]

Степени четверки на 8 на закачиваются, только по очереди на 4 и на 6. С признаками делимости школьного уровня не получается.
Всё-таки залез в Wolfram. Меньший делитель ${4^4}^4-3$ равен 72623.
Что-то ничего нагуглить не могу.

[gris]

Ну разве что трактовать выражение не как тетрацию, а снизу вверх. Тогда оно делится на $11$.

[atlakatl]

gris
Идея не удовлетворяет условию:

Ktina в сообщении #1286376 писал(а):

не удалось справиться даже Альфочке

[gris]

Альфа, очевидно, трактует выражение как тетрацию. Или вовсе никак. Поэтому и написала unknown. Если ей подсунуть вместо четвёрки двойку, то она справится, а если тройку, то нет. А может быть ей решать неохота. PARI не посчитает? Но я думаю, что ТС нашёл какое-то хитрое решение. Это же близко к Числу Мерсенна, вообще-то. Нельзя ли эту идею применить?

[atlakatl]

gris в сообщении #1286427 писал(а):

Это же Число Мерсенна, вообще-то

Для Мерсенна же надо отнимать единицу, а не тройку.

[gris]

Я там поправил. А что если записать выражение так: $K-4+1$?

[wrest]

gris в сообщении #1286433 писал(а):

Я там поправил. А что если записать выражение так:

Вы сейчас про тетрацию $4^{4^{4^{4}}}}-3=4^{(4^{(4^4)})}-3$ или про "обычную" степень $4^{4^{4^{4}}}}-3=(((4^4)^4)^4)=2^{128}-3$ ?

[grizzly]

На 23 делится. Остатки по модулю в Вольфраме посмотрел. Может и на что-то меньшее делится, я не проверял (почему-то первым пришло в голову проверить 23 :)

[eugensk]

grizzly в сообщении #1286438 писал(а):

На 23 делится. Остатки по модулю в Вольфраме посмотрел.

Вы имете ввиду $2^{(2^{513})} \equiv 3 \mod 23$ ? Я не могу сообразить, как это можно проверить.

[grizzly]

eugensk в сообщении #1286441 писал(а):

Вы имете ввиду $2^{(2^{513})} \equiv 3 \mod 23$ ? Я не могу сообразить, как это можно проверить.

Я проверял в два действия: (а) $2^{513}\equiv 8 \mod 22$ и (б) $2^8\equiv 3 \mod 23$.

Сейчас обнаружил, что можно просто спросить Вольфрам

4^4^4^4 mod 23
Result 3

[atlakatl]

wrest в сообщении #1286434 писал(а):

про "обычную" степень $4^{4^{4^{4}}}}-3=(((4^4)^4)^4)=2^{128}-3$ ?

Обычная степень это ${{4^4}^4}^4={4^4}^{256}=4^{4294967296}=2^{8589934592}$ - По меньшей мере $858993459 \cdot 3 = 2576980377+1$ знаков.

[grizzly]

atlakatl в сообщении #1286445 писал(а):

${4^4}^{256}=4^{4294967296}$

Что-то очень скромно получилось. Возведение в степень некоммутативно

[eugensk]

grizzly в сообщении #1286444 писал(а):

Я проверял в два действия: (а) $2^{513}\equiv 8 \mod 22$ и (б) $2^8\equiv 3 \mod 23$.

Разве $(A^B) \mod C = A^{(B \mod C)} \mod C$ ? Я думал что можно только $(A \mod C)^B$.

Или 22 вместо 23 это не опечатка?

[grizzly]

eugensk в сообщении #1286450 писал(а):

Или 22 вместо 23 это не опечатка?

Конечно нет.