For which elements is there an inverse element (Hill's method)?

Question

Cryptography

Hello, I am studying Hill encryption, the algorithm is simple and very understandable. But the question arose: for what elements does an inverse element exist? I read on the Internet that it exists for A which are relatively prime to m, but why is this so?
I will be grateful for help)

Answer 1

You need to learn/read the basics of Finite Set Algebra and Linear Algebra.
Briefly, something like this:
If the cardinality of the set of symbols is equal to a prime number, then all elements except zero have an inverse element.
If the power of the character set is equal to the power of a prime number (for example, 2^5), then you can define the multiplication operation in such a way that every non-zero element also has an inverse element.
For all other cases, only elements that are coprime with the cardinality of the set actually have an inverse element.
It is enough to simply show that if an element a has common factors with m (cardinality of the set), then:
a = k*gcd(a,m)
m = l*gcd(a,m), l < m
then
a*l = k*l*gcd(a,m) = k*m*gcd(a,m) = 0 (mod m)
The element 0 has no inverse, so a has no inverse either.