|
|
|
|
|
|
|
Вернуться
| 1 Садуллоев Чафар, 04 января 2019 г. 12:30:47 | |
|
fh
|
|
|
| 2 Хворых Павел, 04 января 2019 г. 9:06:21 | |
"При чём здесь уравнение b*x = a (mod m)?" - это определение деления.
Деление a/b определяется как вычисление числа x, которое после умножения на b даст a, ровно это и написано в уравнении. Вам надо по модулю, поэтому еще добавляется (mod m).
Важно отметить, что решений может быть несколько или не быть вообще.
|
|
|
| 3 Яндулов Богдан, 03 января 2019 г. 21:08:12 | |
|
При чём здесь уравнение b*x = a (mod m)? Задача состоит в том, чтобы вычислить (A/BC)(mod M), где M - любое число. Также известно, что A делится без остатка на BC. Числа A,B,C большие, порядка 3000!.
|
|
|
| 4 Тер-Саркисов Богдан Олегович, 03 января 2019 г. 21:02:06 | |
|
Частное решение можно получить как с помощью расширенного алгоритма Евклида, так и с помощью нахождения обратного элемента b'^(-1) по модулю m', так как gcd(b', m') = 1. Обратный элемент можно найти с помощью возведения b' в степень fi(m')-1, где fi(m') - функция Эйлера.
|
|
|
| 5 Тер-Саркисов Богдан Олегович, 03 января 2019 г. 20:43:36 | |
|
Пусть есть задача найти решение уравнения b*x = a (mod m), где известны m, a, b (b, m - натуральные, a - целое неотрицательное). Задача сводится к решению линейного диофантового уравнения с двумя неизвестными: b*x + m*y = a, где x, y нужно найти. Пусть g = gcd(b, m). Сделаем подстановку b = b'*g, m=m'*g, то есть b'*g*x + m'*g*y = a. Или же g*(b'*x + m'*y) = a. Отсюда следует, что если a не делится на g, то уравнение решений не имеет. Иначе a' = a/g. Получили диофантово уравнение b'*x + m'*y = a', в котором gcd(b', m') = 1. Далее решаем его, получаем частное решение для x в диапазоне от 0 до m'-1.
|
|
|
| 6 Яндулов Богдан, 03 января 2019 г. 19:55:00 | |
|
Хорошо известен способ для вычисления результата деления по простому модулю: заменяем деление умножением на обратный элемент по нашему простому модулю. Но что делать, если модуль не простой?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
