# “multiplicative inverse in the modulo of the larger number” what does that mean?

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$

• I would never say "in the modulo of"; rather I would just use "modulo" as a preposition: "the multiplicative inverse modulo the larger number". All mathematicians understand that. The former locution is not standard. ${}\qquad{}$ – Michael Hardy Aug 14 '15 at 23:02
• Speculation on the author's motivation: English prepositions are a closed class - new ones aren't invented often. If you're a native English speaker, you learn them all pretty early. Adding a new one to your vocabulary isn't like learning a new noun, adjective, or verb. It's weird. It takes some mental effort to find the right way to parse a sentence with an unfamiliar preposition. Avoiding prepositional "modulo" may just be a way of going easy on the target audience. – user141452 Aug 15 '15 at 1:16

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$.

• it was a perfect answer, thanks a lot, but I am wondering about why they call it multiplicative inverse, it is a little confusing because the multiplicative inverse of number is the number which you multiply it by that number and gives 1 for example if we multiply 9 * 1/9 this will give one so 1/9 is the multiplicative inverse of 9 – Mohamad Aug 15 '15 at 1:30
• @MohammadHaidar It is the same thing, except you have modulo $9$ afterward; as I stated above, the multiplicative inverse of $4$ (working modulo $9$) is the number $n$ such that $4 \cdot n$ equals $1$ (modulo $9$). – angryavian Aug 15 '15 at 1:33

How familiar are you with modular arithmetic? What the author means is that if $\gcd(n,m)=1$ and $m<n$, then we can find a number $k\in\{1,2,...,n-1\}$ such that $mk\equiv 1(\mod n)$.

One way to find the multiplicative inverse is to use the Extended Euclidean Algorithm, but for something small like $4$ and $9$, it is pretty fast to just multiply $4$ by everything in the set $\{1,2,...,8\}$, and see what comes out to be congruent to $1$ modulo $9$. It is a fact from group theory that only one of these numbers should be the inverse.

• Just a comment (+1): I find (when just going by hand, for small numbers) that it's easier for me personally to look at multiples of the modulus. It only takes up to $9 \cdot 3 = 27$ to find that $9 \cdot 3 + 1 = 28$ is a multiple of $4$. – pjs36 Aug 14 '15 at 23:13

Concretely, what he means is this: if $a<b$ are positive integers, and are coprime (that is, their gcd is 1), then there is some integer $c$ such that $ac$ leaves a remainder of 1 when divided by $b$ - that is, $ac-1$ is a multiple of $b$.

A more abstract way of putting this: consider the set $\{0, 1, . . . , b-1\}$. There is a binary operation $\otimes$ on this set, "inspired" by multiplication on the integers, which is defined as follows: $x\otimes y$ is the remainder left when $xy$ is divided by $b$. So, for instance, if $b=7$ then $4\otimes 3=5$. We can similarly extend addition in this way: $a\oplus b$ is the remainder left when $a+b$ is divided by $b$. The set $\{0, 1, . . . , b-1\}$ equipped with these operations is called the integers modulo $b$.

In the normal universe, a multiplicative inverse of a number $x$ is a number $y$ such that $xy=1$. In the integers, there are no (interesting) numbers with multiplicative inverses; in the integers modulo $b$, however, we get lots of multiplicative inverses! For example, if $b=7$, then 2 is the multiplicative inverse of 4 in the integers modulo 7.

(NOTE: In general, any operation on the integers which respects remainders has an analogue on the set $\{0, 1, . . . , b-1\}$, but we're usually most interested in plus and times.)

Notation-wise, what I've written above is non-standard. We write "$a\equiv c$ $(mod$ $b)$" to mean that $a$ leaves a remainder of $c$ when divided by $b$ (or that $a$ and $c$ leave the same remainder); so we usually write "$x+y\equiv z$ $(mod\,\, b)$" rather than "$x\oplus y=z$ in mod $b$".

Let $n$ be a positive integer and consider the positive integers, $x$, that are less than $n$ and for which $\gcd(x,n)=1$. Then $x$ is invertible modulo $n$. Also, if $\gcd(x,n) > 1$, then $x$ is not invertible modulo $n$.

For example $\gcd(3,14)=1$ and $3 \cdot 5 \equiv 15 \equiv 1 \pmod{14}$. However $\gcd(6,14)=2$ and there is no integer $y$ such that $6y \equiv 1 \pmod{14}$

A multiplicative inverse of a number $a\in R$ for a ring $R$ is a number $a^{-1}$ such that $aa^{-1}=1$.

What he means by saying "modulo the bigger number" which we can denote $b$ is a multiplicative inverse of $a$ (the smaller number) in the ring $\mathbb{Z_b}$ which is the ring of the integers under the identification $\forall c,d \in \mathbb{Z} \ \ \bar{c}=\bar{d}\in\mathbb{Z}_b \ \iff c\equiv d(\mbox{mod} b)$.

Note this is intereseting because in general $\mathbb{Z}_b$ is a ring where we do not know if we have multiplicative inverses.

$\mathbb{Z}_b$ is a field (commutative ring with inverses) $\iff \ b$ is a prime number.