Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Остаток от деления числа в степени
СообщениеДобавлено: 31 окт 2016, 13:09 
Не в сети
Начинающий
Зарегистрирован:
31 окт 2016, 13:03
Сообщений: 4
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день. Очень прошу помочь.
Изображение

Пробовала решать по теореме Ейлера и Ферма. Но хочется понять до конца как это делается. Спасибо!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Остаток от деления числа в степени
СообщениеДобавлено: 31 окт 2016, 14:30 
Не в сети
Гений
Зарегистрирован:
30 окт 2015, 15:03
Сообщений: 510
Cпасибо сказано: 11
Спасибо получено:
98 раз в 96 сообщениях
Очков репутации: 15

Добавить очки репутацииУменьшить очки репутации
Вроде это так делается. Попробую первый пример:
Для первого числа: 3 и 100 - взаимнопростые, поэтому сразу можно применять теорему Эйлера: [math]3^{\varphi (100)} = 1 \pmod{ 100 }[/math].

[math]\varphi (100) = 40[/math] (таблицы найдите, онлайн калькулятор или сами посчитайте), т.е. число [math]3^{40} = 1 \pmod {100}[/math]

Для второго числа та же самая история.

Тогда после несложных манипуляций получим вот такое:

[math](3^{40*3 +2} + 7^{40*7+1}) \pmod {100} = ((3^{40})^{3}*3^{2} + (7^{40})^{7}*7) \pmod {100}[/math]

Ну а теперь применяем 2 формулы:

[math](a + b ) \pmod {m} = (a \pmod {m} + b \pmod {m} ) \pmod {m}[/math]
[math](a \cdot b ) \pmod {m} = (a \pmod {m} \cdot b \pmod {m} ) \cdot \pmod {m}[/math]

После их применения получим в результате [math]9 + 7 = 16[/math]

Для больших оснований (2й пример): делите, например, 5555 на 7. Получаете 793+4 в остатке. В итоге число 5555 можно заменить числом 4. Для 2222 - та же операция, правда заменой уже будет число 3. Смысл здесь в том, что в общем наше большое число можно представить в таком виде: [math](a \cdot k + b)^{n}[/math]. И спрашивают у нас остаток от деления этого выражения на [math]k[/math]. Если раскрыть эти скобки, единственное выражение, которое будем иметь ненулевой остаток, это [math]b^{n}[/math], т.к. другие члены разложения будут содержать множитель [math]k[/math].

Последний приём, однако, имеет 1 нюанс, который тоже надо учитывать. Если в результате деления и нахождения остатка получаем основание, которое не является взаимопростым с делителем, в этом случае нужно использовать замену переменной.
Пример: [math]x = 12^{22} \pmod {100} =12*12^{21} \pmod {4*25}[/math]. Здесь применять теорему Эйлера нельзя, т.к. 12 и 100 - не взаимопростые. Предположим, что [math]x = 4 \cdot y[/math], тогда [math]4 \cdot y = 12*12^{21} \pmod {4*25} => y = 3*12^{21} \pmod {25}[/math]. Ну а здесь 12 и 25 - взаимнопростые. [math]\varphi (25) = 20[/math] и тогда получим, что [math]y = 3*12 \pmod {25}[/math], а значит [math]x = 144 \pmod {100} = 44[/math]. Т.е остаток от деления [math]12^{22}[/math] на 100 равен 44.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Zhenek "Спасибо" сказали:
olgasikir
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 2 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Найти остаток от деления числа в степени в степени

в форуме Теория чисел

hejihe4135

7

397

03 мар 2020, 16:51

Остаток от деления числа в степени

в форуме Теория чисел

Oliver

5

1488

31 май 2016, 22:25

Найти остаток от деления числа в степени

в форуме Теория чисел

azh

32

13745

15 дек 2014, 20:15

Найти остаток от деления 10 в 10 степени на 67

в форуме Теория чисел

kapyshkina_darya

7

654

11 ноя 2017, 12:00

Узнать остаток от деления степени на число

в форуме Алгебра

Djwiccdeqd

10

477

30 дек 2018, 20:42

Остаток от деления простого числа

в форуме Интересные задачи участников форума MHP

Xenia1996

7

256

19 окт 2019, 00:30

Найти остаток от деления, если числа не взаимно простые

в форуме Теория чисел

jeliza_rosa

2

617

28 май 2016, 19:12

Остаток числа в степени по модулю

в форуме Теория чисел

nad27

2

217

10 дек 2019, 23:33

Найти остаток от числа в степени без mod

в форуме Теория чисел

Lana67

5

646

24 ноя 2016, 16:03

Нахождение остатка от деления числа в степени

в форуме Теория чисел

Fjord1

7

1389

21 апр 2015, 12:30


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved