Полученный результат |
![Остаток числа]() |
Рассмотрим одну из задач часто встречающейся в арифметике и теории чисел, которую можно выразить несколькими примерами.
Какой остаток будет у следующих чисел
![числа в степени](https://img.abakbot.ru/cgi-bin/mathtex.cgi?2^{31}\\\\-57^{321}\\\\101^{999921441})
если их попытаться разделить на число 31?
И если первый пример можно решить на калькуляторе, так сказать " в лоб, не думая", то как Вы будете решать третий пример, это для некоторых очень не тривиальная задача.
Что же такое остаток? Остаток в данном случае - это такое число(по абсолютному значению меньше модуля!), отняв которое из исходного числа, полученный результат будет делится нацело на модуль ( в нашем примере модуль это число 31)
То есть, если обозначим остаток буквой Х получим (в первом примере ) что число
делится нацело (без остатка) на модуль
Или в другой, записи более привычной
где M - модуль
Как же решать подобные задачи?
Для этого нам надо знать несколько свойств из теории чисел, которые покажем на втором примере ![-57^{321}](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-57^{321})
1. ![-57^{321}mod31=-1^{321}57^{321}mod31](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-57^{321}mod31=-1^{321}57^{321}mod31)
Даже объяснять неохота, выносим -1 за "скобки" ( отдельным множителем) и можем сразу посчитать. Если степень числа (321) четная то результат равен 1, если нечетная то -1.
2.![(-1)57^{321}mod31=(-1)mod31{57^{321}}](https://img.abakbot.ru/cgi-bin/mathtex.cgi?(-1)57^{321}mod31=(-1)mod31*57^{321}mod31)
Если число можно представить в виде двух и более сомножителей то, остаток от этого числа будет равен произведению остатков от сомножителей по этому же модулю.
3.![-1*57^{321}mod31=-1*(57-31-31)^{321}](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-1*57^{321}mod31=-1*(57-31-31)^{321}mod31=-1*(-5)^{321}mod31)
Прибавив или отняв от любого сомножителя целое количество модуля - остаток не изменится.
4. ![-1*(-5)^{321}mod31=-1*(-5^3)^{\frac{321}{3}}mod31=-1*(-5^3)^{{107}mod31](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-1*(-5)^{321}mod31=-1*(-5^3)^{\frac{321}{3}}mod31=-1*(-5^3)^{107}mod31)
Тоже ничего сложного, просто преобразовали степень. Обычное свойство степеней.
5. ![-1*(-5^3)^{{107}mod31=-1*(-125)^{107}=-1*(-125+31+31+31+31)^{107}mod31](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-1*(-5^3)^{107}mod31=-1*(-125)^{107}=-1*(-125+31+31+31+31)^{107}mod31)
Здесь мы возвели -5 в куб и воспользовались 3 правилом, прибавив к нему 4 раза модуль
6. ![-1*(-125+124)^{107}mod31=-1*(-1)^{107}mod31=-1*-1mod31=1](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-1*(-125+124)^{107}mod31=-1*(-1)^{107}mod31=-1*-1mod31=1)
Воспользовавшись первым правилом, получили что наш ответ 1
То есть можем утверждать что
есть целое число.
7. Последнее правило гласит, что формально, всегда существует два остатка и они равноценны. В нашем примере это 1 и -30, так как
тоже целое число.
Надеюсь это небольшой пример разбора, дал Вам методику решения подобных задач.
А бот, который создан, поможет Вам легко узнавать правильность решения подобных задач или, если Вы преподаватель, легко и точно генерировать задачи для учеников.
Синтакис для XMPP клиентов
modul число степень модуль
число - отрицательное или положительное, целое число
степень - только положительная целая степень.
модуль - положительное целое число.
каждый элемент может содержать до 19 цифр ( вообще я не знаю на какой длине, могут возникнуть ошибки, но при (до) 19 символах все работает хорошо)
поэтому нет ничего страшного найти остаток вот от такого "монстра"
![5239009213117^{100445342321}mod6576500111123](https://img.abakbot.ru/cgi-bin/mathtex.cgi?-5239009213117^{100445342321}mod6576500111123)
кто хочет может умножать на калькуляторе :)
ответ 3848922529426
Если же Вы вдруг нашли ошибку или у Вас есть пожелания или вопросы, не стесняйтесь обращайтесь Обратная связь с разработчиками бота.
Интересные факты
Утверждается, что если P - число простое то выполняется вот такое равенство
![2^{P}modP=1](https://img.abakbot.ru/cgi-bin/mathtex.cgi?2^{P-1}modP=1)
Это условие необходимое(то есть применимо ко всем простым числам) но не достаточное ( то есть есть составные числа для которых эта формула тоже действительна)
Красивое выражение было найдено пока тестировал бота ( для 2014 года) :)
![666^{777}mod2014=666](https://img.abakbot.ru/cgi-bin/mathtex.cgi?666^{777}mod2014=666)
![666^{777}mod777=666](https://img.abakbot.ru/cgi-bin/mathtex.cgi?666^{777}mod777=666)
На 31 мая 2018 года еще нашлось кое что интересное
Смотрите
![1331^{56}mod171=134](https://img.abakbot.ru/cgi-bin/mathtex.cgi?1331^{56}mod171=134)
![1331^{2*any\ number}mod171=134](https://img.abakbot.ru/cgi-bin/mathtex.cgi?1331^{2*any\ number}mod171=134)
![133000..000001^{2*any\ number}mod171=134](https://img.abakbot.ru/cgi-bin/mathtex.cgi?133000..000001^{2*any\ number}mod171=134)
Удачных расчетов!