Решение для х в "xy + z ≡ 0 (mod k)"

Question

Мне нужно решить для х в отношении конгруэнтности

xy + z ≡ 0 (mod k)

где y, z и k известны. (k не может быть простым.)

Есть ли лучший алгоритм, чем просто тестирование всех значений от 0 до k-1?

Я попытался использовать теорию чисел, и получил это:

xy ≡ -z (mod k)
x ≡ -z · (обратное (y)% k) (mod k)

но я получаю неправильные результаты в некоторых случаях. Например, если k = 728, x = 272, y = 344 и z = 344, то сохраняется исходное соотношение (потому что 272 · 344 + 344 = 129 · 728), а последнее - нет. Что я делаю не так?

Answer 1

Ваше решение не удается, потому что The multiplicative inverse of “y modulo k” exists if and only if y and k are relatively prime (i.e., if gcd(y, k) = 1). В примере, который вы выбрали y и k не были взаимно простыми
Вот еще один способ решения проблемы

xy + z ≡ 0 (мод к)
xy ≡ -z (мод к)
xy ≡ -z + k (мод к)
Пусть k - z = b
xy ≡ b (mod k)

Теперь вам просто нужно решить линейное уравнение конгруэнтности.
Решение для вашего примера будет выглядеть как

x * 344 + 344 ≡ 0 (мод. 728)
x * 344 ≡ -344 (мод. 728)
x * 344 ≡ -344 + 728 (мод. K)
х * 344 х 384 (мод 728)

Решение этого сначала путем уменьшения до x * 43 ≡ 48 (мод 91), а затем с использованием расширенного евклидового алгоритма даст общую форму решения как

90 + 91 * т
Решения для x менее 728: 90, 181, 272, 363, 454, 545, 636, 727.

Таким образом, вы можете найти все возможные решения для х.