Решение сравнений по модулю
Этот калькулятор находит решения линейных сравнений, или сравнений первой степени по модулю m
Решение сравнений по модулю
Решений нет
Сравнение по модулю
Сравнение двух целых чисел по модулю натурального числа m — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на m один и тот же остаток. Арифметические операции с остатками чисел по одному и тому же модулю образуют модулярную арифметику.
Сравнимость чисел a и b по модулю сравнения m записывается как
Выражение
называется сравнением первой степени или линейным сравнением по модулю m.
Для проверки существования решений сравнения сначала вычисляется НОД(a, m). Если b не кратно полученному НОД, то у сравнения нет решений.
Если кратно, то количество решений по модулю m равно полученному НОД.
Существует несколько алгоритмов нахождения всех решений сравнения, но в данном калькуляторе применяется алгоритм решения линейных диофантовых уравнений с двумя переменными. В самом деле, сравнение эквивалентно следующему линейному диофантовому уравнению:
поэтому я использовал уже реализованный калькулятор решения линейных диофантовых уравнений для получения общей формулы решения, после чего выбрал все частные решения в диапазоне от 0 до m.
Комментарии