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

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

задан 22 Янв '18 11:53

изменен 22 Янв '18 11:53

10|600 символов нужно символов осталось
2

Здесь достаточно угадать, на какое простое число должна делиться "башня" из четвёрок. Подходит p=23. Чтобы вычислить остаток от деления на 23, достаточно найти остаток показателя от деления на 22. Он чётен, и задача сводится к нахождению остатка по модулю 11. А этот вопрос сводится к нахождению значения 4^4 mod 10. Здесь ясно, что 4 в чётной степени оканчивается на 6. Из того, что 4^4=6 (mod 10), по малой теореме Ферма следует, что 4^(4^4)=4^6=2^{12}=2^2=4 (mod 11). Разность числа и его остатка чётна, поэтому делится на 22, откуда 4^(4^4)=4 (mod 22). Тогда снова в силу малой теоремы Ферма получается, что число из условия сравнимо с 4^4=256=3 (mod 23).

Кстати, для числа 4^(4^4)-3 задача оказывается сложнее. Оно тоже составное, но его наименьший простой делитель равен 72623, и тут уже без компьютера не обойтись.

ссылка

отвечен 22 Янв '18 12:22

@falcao, большое спасибо!

(22 Янв '18 12:30) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,213
×219
×41
×26
×4

задан
22 Янв '18 11:53

показан
308 раз

обновлен
22 Янв '18 12:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru