Для каких элементов существует обратный элемент(метод Хилла)?

Question

[naruto_hokagi]

Здравствуйте, изучаю шифрование методом Хилла, алгоритм простой и весьма понятный. Но возник вопрос: для каких элементов существует обратный элемент? В инете прочитал, что он существует для A которые взаимно простые с m, но почему это так?
буду благодарен за помощь)

Answer 1

[Sumor]

Вам необходимо изучить/прочитать основы алгебры конечных множеств и линейной алгебры.
Вкратце примерно так:
Если мощность множества символов равна простому числу, то обратный элемент есть у всех элементов кроме нуля.
Если мощность множества символов равна степени простого числа (например, 2^5), то можно определить операцию умножения таким образом, чтобы также у каждого ненулевого элемента был обратный элемент.
Для всех остальных случаев действительно обратный элемент есть только только у элементов, которые взаимно простые с мощностью множества.
Достаточно просто показать, что если элемент a имеет общие множители с m (мощность множества), то:
a = k*НОД(a,m)
m = l*НОД(a,m), l < m
тогда
a*l = k*l*НОД(a,m) = k*m*НОД(a,m) = 0 (mod m)
Элемент 0 не имеет обратного, значит и a не имеет обратного.