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

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

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

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

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

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

если их попытаться разделить на число 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} тоже целое число.

 

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

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

Синтакис для XMPP клиентов

modul число степень модуль

число - отрицательное или положительное, целое число

степень - только положительная целая степень.

модуль - положительное целое число.

каждый элемент может содержать до 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

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

 
 
Поиск по сайту