Как доказать нижеследующий факт, не вычисляя сами остатки? Может, есть какая теорема теории чисел?

Степени четвёрки с натуральным показателем дарамдаш ровно 18 попарно различных остатков при делении на 37, ровно 10 попарно различных остатков при делении на 38, ровно 6 попарно различных остатков при делении на 39, ровно 4 попарно различных остатка при делении на 40 и ровно 10 попарно различных остатков при делении на 41.

Доказательство нужно вот для чего.

задан 7 Фев 1:28

1

@Казвертеночка: со стороны это смотрится как чисто случайное совпадение, и вызывает даже некоторое удивление, как сам этот факт был обнаружен. Дело в том, что даже более простая по форме задача о нахождении порядка элемента 2 по простому модулю p (то есть наименьшего натурального n=n(p), при котором 2^n-1 делится на p), не имеет какого-то "прозрачного" ответа. Мы знаем, что n делит p-1, но даже случаи, когда n=p-1, выглядят "нерегулярно".

Понятно, что порядок 4 по нечётному модулю от этого зависит, а по чётному -- нужна ещё некая "подгонка" с отдельным учётом остатка 1 и т.п.

(7 Фев 3:37) falcao
1

А чем не нравится перебор?

(7 Фев 9:25) spades

@falcao, то есть, придётся всё-таки перебирать?

(7 Фев 12:30) Казвертеночка

@spades, тем, что он отнимает у перебирающего\й время и силы, а значит, скорость прогресса падает.

(7 Фев 12:31) Казвертеночка
1

Да какое там время? 5 минут на программу и долю секунды на сам перебор. Не думаю, что содержательное доказательство займет меньше времени

(7 Фев 13:59) spades

@spades, если бы Ян Альбертович умел написать подобную программу за 5 минут, он бы не существовал на пенсию по инвалидности :)

(7 Фев 14:02) Казвертеночка
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,091
×87
×62
×40
×29

задан
7 Фев 1:28

показан
135 раз

обновлен
7 Фев 14:02

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

по почте:

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

по RSS:

Ответы

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

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