Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по математике

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 761 RSS
←   Апрель 2016   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru
Открыта: 14-07-2005

Автор
Калашников О.А.

Статистика

761 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по математике


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Лангваген Сергей Евгеньевич
Статус: Профессор
Рейтинг: 490
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 456
∙ повысить рейтинг » 		Елена Васильевна
Статус: 10-й класс
Рейтинг: 353
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика

Номер выпуска:1917
Дата выхода:27.04.2016, 15:21
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:20 / 29
Вопросов / ответов:1 / 2

Консультация # 189239: Здравствуйте! Прошу помощи в следующем вопросе: найти остаток от деления 11^(11^35) mod (62)...

Консультация # 189239:

Здравствуйте! Прошу помощи в следующем вопросе:

найти остаток от деления 11^(11^35) mod (62)

Дата отправки: 22.04.2016, 15:02
Вопрос задал: bill1091989 (Посетитель)
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Гордиенко Андрей Владимирович (Модератор):

Здравствуйте, bill1091989!

Я бы решал задачу так.

По формуле Эйлера

φ(62)=φ(2*31)=(21-20)(311-310)=1*30=30.

Тогда по теореме Эйлера
1130≡1 (mod 62).


Аналогично
φ(30)=φ(2*3*5)=(2-1)(3-1)(5-1)=8,

118≡1 (mod 30).


С учётом свойств сравнений получим
(118)4=1132≡14=1 (mod 30),

1135=1132+3≡113 (mod 30),

113=1331=44*30+11,

1135≡11 (mod 30),

1111^35≡1111 (mod 62),

1111=285311670611=62*4601801138+55.


Значит, остаток от деления числа 1111^35 на 62 равен 55.

С уважением.

Консультировал: Гордиенко Андрей Владимирович (Модератор)
Дата отправки: 23.04.2016, 13:57
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Консультирует Roman Chaplinsky / Химик CH (Модератор):

Здравствуйте, bill1091989!
В том, что функция an mod d - периодическая (впрочем, это не гарантирует, что период начнётся с первого значения функции - как в случае, когда с определённого значения n все остатки равны нулю) можно убедиться из того, что
an+1 mod d = ((an mod d)·a) mod d
то есть остаток следующего члена показательной последовательности зависит только от остатка предыдущего от деления на тот же делитель. А число возможных остатков не может превышать делитель.

Составив по этому принципу таблицу значений 11n mod 62 (пока они не начнут повторяться), находим, что
1130 mod 62 = 1 = 110 mod 62
1131 mod 62 = 11 = 111 mod 62
то есть период равен 30 (и имеет место при n=1 и даже n=0)
11n mod 62 = 11n mod 30 mod 62

Здесь также можно отметить, что остаток an mod d не может принимать значения, делящиеся на прос тые делители числа d, не являющиеся делителями числа a (что отражено в упомянутой в предыдущем ответе формуле Эйлера). Функция 11n mod 62 действительно принимает все 30 возможных значений, удовлетворяющих этому условию (как мы далее убедимся, это не всегда так).

Итак,


Теперь нужно найти 1135 mod 30
Легко убедиться, что 11n mod 30 принимает всего 2 значения (что на сей раз в 4 раза меньше, чем то, что даёт нам формула Эйлера):
112k-1 mod 30 = 111 mod 30 = 11
112k mod 30 = 112 mod 30 = 1
или
11n mod 30 = 11n mod 2 mod 30

Таким образом находим ответ (воспользовавшись ранее составленной таблицей остатков 11n mod 62)

Консультировал: Roman Chaplinsky / Химик CH (Модератор)
Дата отправки: 23.04.2016, 23:38
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное