Решение сравнений по модулю

Этот калькулятор находит решения линейных сравнений, или сравнений первой степени по модулю m

Эта страница существует благодаря следующим персонам

Timur

Timur

Создан: 2021-11-26 20:49:40, Последнее изменение: 2021-11-26 21:37:26

PLANETCALC, Решение сравнений по модулю

Решение сравнений по модулю

Сравнение первой степени
 

Решений нет

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Сравнение по модулю

Сравнение двух целых чисел по модулю натурального числа m — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на m один и тот же остаток. Арифметические операции с остатками чисел по одному и тому же модулю образуют модулярную арифметику.

Сравнимость чисел a и b по модулю сравнения m записывается как
a \equiv b {\pmod {m}}

Выражение
a \cdot x \equiv b {\pmod {m}}
называется сравнением первой степени или линейным сравнением по модулю m.

Для проверки существования решений сравнения сначала вычисляется НОД(a, m). Если b не кратно полученному НОД, то у сравнения нет решений.
Если кратно, то количество решений по модулю m равно полученному НОД.

Существует несколько алгоритмов нахождения всех решений сравнения, но в данном калькуляторе применяется алгоритм решения линейных диофантовых уравнений с двумя переменными. В самом деле, сравнение эквивалентно следующему линейному диофантовому уравнению:
a \cdot x  + m \cdot y = b {\pmod {m}}
поэтому я использовал уже реализованный калькулятор решения линейных диофантовых уравнений для получения общей формулы решения, после чего выбрал все частные решения в диапазоне от 0 до m.

Ссылка скопирована в буфер обмена
PLANETCALC, Решение сравнений по модулю

Комментарии