Найти тему
Математика не для всех

Как найти остаток от деления ? Универсальный способ

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

Приветствую Вас, уважаемые Читатели! Сегодня хочу немного погрузиться в теорию делимости, а именно в вычисление остатков от деления. Эта задача является и практически важной, ведь такие операции применяются буквально повсюду: от криптографии до телекоммуникационных систем. Поехали!

Итак, начнем с определения:

-2
Так же такие числа называются сравнимыми по модулю m.

Для равноостаточных чисел работает такая теорема:

  • Если при делении на m числа a1,a2,a3... an соответственно равноостаточны числам b1,b2.b3...bn, то равноостаточными будут суммы a1+a2+a3+...+an и b1+b2+b3+...bn, а также произведения a1a2a3...an и b1b2b3...bn.
  • Как следствие, если числа a и b равноостаточны, то такими же являются и числа a^n и b^n при любо натуральном n.

Формулировка весь запутанная, поэтому разберем два пример. Итак:

-3

Теперь пример посложнее с многоступенчатым решением:

-4

В итоге мы получаем хоть и меньшее, но всё равно трудно вычисляемое вручную число, поэтому продолжаем дальше:

-5

На третьем шаге уже нет смысла вычислять все остатки, как прежде. Можно было и вычислить вручную. Получаем, что первоначальное число и число 56 равноостаточны при делении на 37. Ответ получен! Спасибо за внимание!

Читайте также: