Бывает, он сопряжен с некоторыми неудобствами, но это лучше, чем ничего.
Приветствую Вас, уважаемые Читатели! Сегодня хочу немного погрузиться в теорию делимости, а именно в вычисление остатков от деления. Эта задача является и практически важной, ведь такие операции применяются буквально повсюду: от криптографии до телекоммуникационных систем. Поехали!
Итак, начнем с определения:
Так же такие числа называются сравнимыми по модулю 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.
Формулировка весь запутанная, поэтому разберем два пример. Итак:
Теперь пример посложнее с многоступенчатым решением:
В итоге мы получаем хоть и меньшее, но всё равно трудно вычисляемое вручную число, поэтому продолжаем дальше:
На третьем шаге уже нет смысла вычислять все остатки, как прежде. Можно было и вычислить вручную. Получаем, что первоначальное число и число 56 равноостаточны при делении на 37. Ответ получен! Спасибо за внимание!