Решение сравнений по модулю
Этот калькулятор находит решения линейных сравнений, или сравнений первой степени по модулю m
Эта страница существует благодаря следующим персонам
 | Timur
|
Этот материал распространяется на условиях лицензии Creative Commons Attribution/Share-Alike License 3.0 (Unported). Это означает, что вы можете размещать этот контент на своем сайте или создавать на его основе собственный (в том числе и в коммерческих целях), при условии сохранения оригинального лицензионного соглашения. Кроме того, Вы должны отметить автора этой работы, путем размещения HTML ссылки на оригинал работы https://planetcalc.ru/9561/. Пожалуйста оставьте без изменения все ссылки на других авторов данной работы или работы, на основе которой создана данная работа (если таковые имеются в спроводительном тексте).
Решение сравнений по модулю
Решений нет
Сравнение по модулю
Сравнение двух целых чисел по модулю натурального числа m — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на m один и тот же остаток. Арифметические операции с остатками чисел по одному и тому же модулю образуют модулярную арифметику.
Сравнимость чисел a и b по модулю сравнения m записывается как
Выражение
называется сравнением первой степени или линейным сравнением по модулю m.
Для проверки существования решений сравнения сначала вычисляется НОД(a, m). Если b не кратно полученному НОД, то у сравнения нет решений.
Если кратно, то количество решений по модулю m равно полученному НОД.
Существует несколько алгоритмов нахождения всех решений сравнения, но в данном калькуляторе применяется алгоритм решения линейных диофантовых уравнений с двумя переменными. В самом деле, сравнение эквивалентно следующему линейному диофантовому уравнению:
поэтому я использовал уже реализованный калькулятор решения линейных диофантовых уравнений для получения общей формулы решения, после чего выбрал все частные решения в диапазоне от 0 до m.
Комментарии