We are already familiar with the concept of multiplicative inverses for real numbers, which is as follows:
For any real number $x \ne 0$, its multiplicative inverse $y$ is a real number, such that,
$xy = 1 \Rightarrow y = \dfrac{1}{x} = x^{-1}$, that is the product of a number and its inverse is $1$.
The concept of multiplicative inverses, in modular arithmetic is not much different.
When we have an integer $a$, we say that its multiplicative inverse modulo $N$ is an integer $b$ such that:
$ab \equiv 1\ (mod\ N)$
or, alternately we can write:
$b \equiv a^{-1}\ (mod\ N)$
In other words, the product of a number and its inverse is congruent to $1$ mod $N$
Theorem
Unlike real numbers, where a multiplicative inverse exists for every non-zero number, in case of modular arithmetic, an inverse of an integer, $a$, modulo $N$ exists if and only if $a$ is coprime to $N$, that is $gcd(a,\ N) = 1$.
Proof
Extended Euclid's Theorem says that if $g = gcd(a,\ b)$ then, $g$ is the smallest positive integer, that can be expressed as a linear combination of $a$ and $b$, that there exists integers $m$ and $n$ (positive or negative) such that:
$g = ma + nb$
Any positive integer, less than $g$ cannot be expressed using a linear combination of $a$ and $b$.
Now, it is easy to see why inverses exist if and only if the gcd of the two numbers is $1$.
-----------book page break-----------
We will prove this by contradiction.
Let us assume that $g = gcd(a,\ N)$ such that $g \gt 1$, and there exists integer $b$ that satisfies the relation:
$ab \equiv 1\ (mod\ N)$
$ab = pN + 1$ for some integer $p$
$\Rightarrow ab - pN = 1$
$\Rightarrow ab + (-p)N = 1$
Since $b$ and $p$ are integers, this is a linear combination of $a$ and $N$, and this contradicts the Extended Euclid's Theorem, that is we have expressed $1$, which is less than $g$ as a linear combination of $a$ and $N$. Therefore this is not possible.
--------- Reference to question: 1563de85-b60e-4068-990b-8e4d7f5d935a ---------
-----------book page break-----------
Method To Find Inverse
Now, we will see how to find multiplicative inverses using Extended Euclid's Method.
Let us find the inverse of $11$ modulo $18$. Since $11$ and $18$ are coprimes, there exists integer $p$ such that $11p \equiv 1\ (mod\ 18)$
We know from the , how to find the $gcd$ of two integers by repeated division and substitution.
Performing our repeated division and substitutions, we get:
$Step\ 1:$ $18 = 11(1) + 7$ $7 = 18 - 11(1)$
we have written the remainder as $dividend - divisor(quotient)$ for our later use.
(now we take $11$ as the new dividend and $7$ as the new divisor)
$5 \times 11 = 55$ which leaves a remainder of $1$ when divided by $18$.
Therefore, $5$ is the inverse of $11$ modulo $18$.
$\underline{Tip:}$ Note that for smaller numbers it may be much faster if the inverses are computed by multiplying the given number with each of the other numbers that are coprime to the divisor, and checking the remainder. For the above example to find $11^{-1} \pmod{18}$ it is easier to calculate $11 \times \{5,\ 7,\ 13 \}$ and then finding the remainder with $18$. Observe that in our working we eliminated all numbers that share a non-trivial factor with $18$, also, $1, 11$ and $17$. But for larger numbers, like numbers greater than $50$ or so, it will be more efficient to use the Extended Euclid's Method.
-----------book page break-----------
Properties Of Inverses
For any given integers $N$ all integers coprime to $N$ and less than $N$, map to a unique inverse modulo $N$.
In other words, no two integers less than $N$, that have inverses, map to the same inverse.
Which means, given two integers, $a$ and $b$ less than and coprimes to $N$, where $a \ne b$, then:
$a^{-1}\ (mod\ N) \ne b^{-1}\ (mod\ N)$
Only the numbers $1$ and $N - 1$ are inverses of themselves.
This is easy to see. If we multiply $(N- 1)$ by itself we get $(N-1)^2$