Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | |
---|---|---|
olgasikir |
|
|
Вернуться к началу | ||
Zhenek |
|
|
Вроде это так делается. Попробую первый пример:
Для первого числа: 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. |
||
Вернуться к началу | ||
За это сообщение пользователю Zhenek "Спасибо" сказали: olgasikir |
||
[ Сообщений: 2 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Найти остаток от деления числа в степени в степени
в форуме Теория чисел |
7 |
1586 |
03 мар 2020, 16:51 |
|
Остаток от деления числа в степени
в форуме Теория чисел |
5 |
2255 |
31 май 2016, 22:25 |
|
Найти остаток от деления числа в степени
в форуме Теория чисел |
32 |
23034 |
15 дек 2014, 20:15 |
|
Найти остаток от деления 10 в 10 степени на 67
в форуме Теория чисел |
7 |
1186 |
11 ноя 2017, 12:00 |
|
Узнать остаток от деления степени на число
в форуме Алгебра |
10 |
808 |
30 дек 2018, 20:42 |
|
Остаток от деления простого числа | 7 |
820 |
19 окт 2019, 00:30 |
|
Найти остаток от деления, если числа не взаимно простые
в форуме Теория чисел |
2 |
873 |
28 май 2016, 19:12 |
|
Остаток числа в степени по модулю
в форуме Теория чисел |
2 |
593 |
10 дек 2019, 23:33 |
|
Найти остаток от числа в степени без mod
в форуме Теория чисел |
5 |
1010 |
24 ноя 2016, 16:03 |
|
Нахождение остатка от деления числа в степени
в форуме Теория чисел |
7 |
2012 |
21 апр 2015, 12:30 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |