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

Основание степень и модуль, разделенные хотя бы одним пробелом

Полученный результат

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

Какой остаток будет у следующих чисел

$числа в степени$

если их попытаться разделить на число 31?

И если первый пример можно решить на калькуляторе, так сказать " в лоб, не думая", то как Вы будете решать третий пример, это для некоторых очень не тривиальная задача.

Что же такое остаток? Остаток в данном случае - это такое число(по абсолютному значению меньше модуля!), отняв которое из исходного числа, полученный результат будет делится нацело на модуль ( в нашем примере модуль это число 31)

То есть, если обозначим остаток буквой Х получим (в первом примере ) что число $2^{31}-Х$ делится нацело (без остатка) на модуль

Или в другой, записи более привычной

$2^{31}modM=X$ где M - модуль

Как же решать подобные задачи?

Для этого нам надо знать несколько свойств из теории чисел, которые покажем на втором примере $-57^{321}$

1. $-57^{321}mod31=-1^{321}57^{321}mod31$

Даже объяснять неохота, выносим -1 за "скобки" ( отдельным множителем) и можем сразу посчитать. Если степень числа (321) четная то результат равен 1, если нечетная то -1.

2. $(-1)57^{321}mod31=(-1)mod31{57^{321}}$

Если число можно представить в виде двух и более сомножителей то, остаток от этого числа будет равен произведению остатков от сомножителей по этому же модулю.

3. $-1*57^{321}mod31=-1*(57-31-31)^{321}$

Прибавив или отняв от любого сомножителя целое количество модуля - остаток не изменится.

4. $-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$

Здесь мы возвели -5 в куб и воспользовались 3 правилом, прибавив к нему 4 раза модуль

6. $-1*(-125+124)^{107}mod31=-1*(-1)^{107}mod31=-1*-1mod31=1$

Воспользовавшись первым правилом, получили что наш ответ 1

То есть можем утверждать что $-57^{321}-1$ есть целое число.

7. Последнее правило гласит, что формально, всегда существует два остатка и они равноценны. В нашем примере это 1 и -30, так как $\frac{-57^{321}-30}{31}$ тоже целое число.

Надеюсь это небольшой пример разбора, дал Вам методику решения подобных задач.

А бот, который создан, поможет Вам легко узнавать правильность решения подобных задач или, если Вы преподаватель, легко и точно генерировать задачи для учеников.

Каждый элемент в запросе может содержать до 19 цифр ( вообще я не знаю на какой длине, могут возникнуть ошибки, но при (до) 19 символах все работает хорошо)

поэтому нет ничего страшного найти остаток вот от такого "монстра"

$5239009213117^{100445342321}mod6576500111123$

кто хочет может умножать на калькуляторе :)

ответ 3848922529426

Если же Вы вдруг нашли ошибку или у Вас есть пожелания или вопросы, не стесняйтесь обращайтесь Обратная связь с разработчиками бота.

Интересные факты

Утверждается, что если P - число простое то выполняется вот такое равенство

$2^{P}modP=1$

Это условие необходимое(то есть применимо ко всем простым числам) но не достаточное ( то есть есть составные числа для которых эта формула тоже действительна)

Красивое выражение было найдено пока тестировал бота ( для 2014 года) :)

$666^{777}mod2014=666$

$666^{777}mod777=666$

На 31 мая 2018 года еще нашлось кое что интересное

Смотрите

$1331^{56}mod171=134$

$1331^{2*any\ number}mod171=134$

$133000..000001^{2*any\ number}mod171=134$

Удачных расчетов!