Калькулятор китайской теоремы об остатках

Китайская теорема об остатках, часто обозначаемая CRT, объединяет несколько модульных условий в одно решение. Сравнение x ≡ 2 по модулю 3 означает, что при делении x на 3 получается остаток 2. Калькулятор принимает три таких уравнения и находит наименьшее неотрицательное целое число, одновременно удовлетворяющее им всем. Классическая теорема применяется к попарно взаимно простым модулям: наибольший общий делитель каждой пары равен единице. При этом существует ровно одно решение по модулю произведения всех модулей. Для модулей 3, 5 и 7 произведение равно 105. Если наименьшее решение равно 23, то 23, 128, 233 и все числа, полученные прибавлением или вычитанием 105, удовлетворяют той же системе. Конструктивный алгоритм сначала перемножает все модули и получает M. Затем для каждого уравнения делит M на его модуль, получая частичное произведение. Поскольку модули попарно взаимно просты, у частичного произведения есть мультипликативный обратный элемент по исключённому модулю. Произведение остатка, частичного произведения и обратного элемента образует слагаемое, удовлетворяющее одному сравнению и дающее ноль в остальных. Сумма этих слагаемых, приведённая по модулю M, даёт ответ. CRT применяется далеко за пределами учебной теории чисел. Она обеспечивает эффективную арифметику больших целых чисел и используется в криптографии, теории кодирования, календарных циклах, сменных расписаниях, компьютерной алгебре и восстановлении значений по остаткам. Особенно полезна, когда сложный расчёт можно разделить на небольшие независимые вычисления по нескольким модулям, а затем объединить результаты. Введите целые остатки и модули больше единицы. Остаток может быть отрицательным или превышать модуль: приведение по модулю автоматически его нормализует. Эта версия намеренно требует попарно взаимно простых модулей, следуя стандартной теореме и гарантируя единственный класс вычетов. Системы с невзаимно простыми модулями иногда разрешимы, но требуют дополнительной проверки совместности и не входят в возможности калькулятора. Всегда проверяйте результат делением на каждый модуль и сравнением остатков.