Бесконечно ли множество таких $%n \in \mathbb{N}$% что $%{2^n}$% оканчивается на $%n$%?

задан 24 Авг '14 19:30

изменен 25 Авг '14 17:00

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Да, бесконечно.

Минимальным примером является число $%a_1=36$%, что проверяется непосредственно. Далее по индукции строим числа $%a_2$%, $%a_3$%, ... , доказывая, что все они обладают требуемым свойством.

Число $%a_2$% определяем как $%2^{a_1}{\rm mod\ }10^3$%, далее $%a_3$% как $%2^{a_2}{\rm mod\ }10^4$%, то есть $%a_{k+1}=2^{a_k}{\rm mod\ }10^{k+2}$% для всех $%k\ge1$%. Требуется доказать, что $%2^{a_k}-a_k$% делится на $%10^{k+1}$%. Из этого будет следовать, что число $%2^{a_k}$% в десятичной записи оканчивается на $%a_k$% (ввиду $%a_k < 10^{k+1}$%, что вытекает из построения).

Достаточно отдельно установить делимость на $%2^{k+1}$% и на $%5^{k+1}$%. Первый факт следует из того, что $%a_k$% делится на $%2^{k+1}$%, что верно при $%k=1$%, и далее проверяется по индукции. Переход от $%k$% к $%k+1$% выглядит так: если уже известно, что $%a^k$% кратно $%2^{k+1}$%, то $%a_k\ge k+2$%, и тогда $%a_{k+1}$% в соответствии с индуктивным определением кратно $%2^{k+2}$%.

Зная, что $%a_k$% делится на $%2^{k+1}$% при всех $%k$%, мы выводим отсюда, что и разность $%2^{a_k}-a_k$% делится на $%2^{k+1}$%, так как показатель степени двойки превышает $%k+1$%.

Теперь, рассуждая по индукции, проверяем то же самое для степени пятёрки. При $%k=1$% всё верно. Предположим, что $%2^{a_k}-a_k$% делится на $%5^{k+1}$%, доказывая, что $%2^{a_{k+1}}-a_{k+1}$% делится на $%5^{k+2}$%. По определению, числа $%a_{k+1}$% и $%2^{a_k}$% сравнимы по модулю $%5^{k+2}$%, то есть доказываемое утверждение равносильно делимости числа $%2^{a_{k+1}}-2^{a_{k}}$% на $%5^{k+2}$%. А это, в свою очередь, равносильно делимости $%2^{{a_{k+1}}-{a_{k}}}-1$% на $%5^{k+2}$%. Применяя теорему Эйлера, сводим этот факт к проверке того, что $%a_{k+1}-a_k$% делится на $%\varphi(5^{k+2})=4\cdot5^{k+1}$%. Ясно, что на 4 делятся все рассматриваемые числа последовательности, а с учётом определения числа $%a_{k+1}$%, сравнимого с $%2^{a_k}$% по модулю $%5^{k+1}$%, всё далее следует из индукционного предположения.

Осталось заметить, что $%a_1\le a_2\le a_3\le\cdots$% по построению. Некоторые из совпадений в принципе возможны, но различных чисел в данной последовательности имеется бесконечно много. В противном случае последовательность бы стабилизировалась на некотором члене $%a_m$%, и оказалось бы, что $%2^{a_m}-a_m$% делится на сколь угодно высокую степень числа $%10$%, что невозможно.

ссылка

отвечен 25 Авг '14 1:35

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×120
×51

задан
24 Авг '14 19:30

показан
416 раз

обновлен
25 Авг '14 1:35

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

по почте:

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

по RSS:

Ответы

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

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