Натуральное число $%n$% разрешается заменить на любое число вида $%n
\times \dfrac{(p-1)^k}{p}$%, где $%p$% - это простой произвольный делитель $%n$%, а $%k$% - произвольное натуральное число. Докажите, что в результате таких операция когда-нибудь обязательно получится 1?

задан 30 Авг '19 4:42

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

Представим число $%n$% в виде $%n=p_1^{k_1}\ldots p_r^{k_r}$%, где $%p_i$% обозначает $%i$%-е простое число, и показатели степеней неотрицательны. Ввиду того, что в каноническом разложении числа $%p-1$% присутствуют только простые числа меньшие $%p$%, преобразование числа из условия устроено так: одно из чисел $%k_i$% (то, для которого $%p_i=p$%) уменьшается на единицу, предыдущие числа из набора показателей как-то меняются (как именно, не существенно), а последующие -- не меняются. Требуется доказать, что преобразований такого вида друг за другом можно осуществить лишь конечное число.

Доказываем это индукцией по $%r$%. При $%r=1$% мы имеем дело со степенями $%p_1=2$%. Показатели могут только уменьшаться. Поэтому любая цепочка преобразований обрывается (имеет конечную длину).

Пусть теперь $%r > 1$%, и для всех значений $%< r$% утверждение доказано. В ходе преобразований, число $%k_r$% либо не меняется, либо уменьшается. Рассмотрим те участки, для которых значение $%k_r$% постоянно. Все они имеют конечную длину по предположению индукции, так как при неизменном $%k_r$% речь идёт о преобразованиях числа вида $%p_1^{k_1}\ldots p_{r-1}^{k_{r-1}}$%. Самих участков постоянства величины $%k_r$% также конечное число: их не больше $%k_r+1$%, так как значения последнего показателей могут меняться только от $%k_r$% до нуля. Получается конечное число конечных отрезков. Значит, длина последовательности преобразований конечна.

ссылка

отвечен 30 Авг '19 12:31

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

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

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

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

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

отмечен:

×1,463

задан
30 Авг '19 4:42

показан
152 раза

обновлен
30 Авг '19 12:31

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

по почте:

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

по RSS:

Ответы

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

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