while I was reading this artical I have read the following paragraph:
The interesting thing is that if two numbers have a $\gcd$ of $1$, then the smaller of the two numbers has a multiplicative inverse in the modulo of the larger number. It is expressed in the following equation:
and he gives the following example:
Lets work in the set $\mathbb{Z_9}$, then $4\in\mathbb{Z_9}$ and $\gcd(4,9)=1$.
Therefore $4$ has a multiplicative inverse (written $4^{−1}$) in $\bmod9$, which is $7$.
And indeed, $4\cdot7=28\equiv1\pmod9$.
But not all numbers have inverses.
For instance, $3\in\mathbb{Z_9}$ but $3^{−1}$ does not exist!
This is because $\gcd(3,9)=3\neq1$.
but what I do not understand is what does he mean by:
then the smaller of the two numbers has a multiplicative inverse in
the modulo of the larger number.
and how he got the $7$
Best Answer
The two numbers in his example are $4$ and $9$. The statement is that $4$ has a multiplicative inverse in the integers modulo $9$, or in other words, there is an integer $n$ such that $4 \cdot n \equiv 1 \mod 9$. The $7$ can be obtained by some trial and error (you only need to check the integers $1$ through $9$). He then gives an example of an integer that does not have a multiplicative inverse modulo $9$, namely $3$.