Prerequisites: Congruences, GCD and LCM
Definition (invertibility)
Consider a set
with a binary operation having a neutral element denoted (an element satisfying ). Then an element is called invertible with respect to ' ' if there is an element labeled such that .
Theorem
An element
is invertible with respect to multiplication iff .
Proof
Finding the inverse with respect to
is the same as solving the following equation in : . Rewriting this as a congruence, we want to show that the congruence has solutions. Then, Rewriting, we get
. As we know that , by Bézout’s identity this equation in variables and has integer solutions. Therefore the original congruence, and the original equation in has solutions.
Question
Is the multiplicative inverse unique?