6
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ 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{}$ $\endgroup$ – Michael Hardy Aug 14 '15 at 23:02
  • $\begingroup$ 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. $\endgroup$ – user141452 Aug 15 '15 at 1:16
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mohamad Aug 15 '15 at 1:30
  • 2
    $\begingroup$ @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$). $\endgroup$ – angryavian Aug 15 '15 at 1:33
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – pjs36 Aug 14 '15 at 23:13
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.