Mathematics Appendix - Everyday Cryptography - page 505

DEFINITION OF MULTIPLICATIVE INVERSE
The multiplicative inverse of a chosen number is the number that we multiply the
chosen number by to get 1. In other words:

3 × 'the multiplicative inverse of 3' = 1 .

So what is the multiplicative inverse of 3 in our normal number system? The
answer is one third, since:

1
3 = 1 .
In a similar way, the multiplicative inverse of 127 is

3 ×

1

127 . The multiplicative inverse
of a number is indicated by writing the number to the power − 1. Thus, for

example:

1
3 .
An important issue is that not every number has a multiplicative inverse.
For example, in our normal number system, the number 0 does not have a
multiplicative inverse, since there is no number that, whenmultiplied by 0, results
in the answer 1.

3 − 1 =

DIVISION USING MULTIPLICATIVE INVERSES
Division by a number can thus be described as the process of multiplying a
number by its multiplicative inverse. For example, dividing by 10 is just the same
as multiplying by

1

10 , the multiplicative inverse of 10. In other words, division by
10 is the same as multiplying by 10 − 1 . Similarly, division by 127 is the same as
multiplying by 127 − 1

1

127 .
This might sound like we are just playing with words, but we are not.
Considering division as multiplication by multiplicative inverses is very helpful
when we return to the problem of how to divide in modular arithmetic.

=

MODULAR INVERSES
We now consider the multiplicative inverse of one number modulo another,
sometimes referred to as a modular inverse . We will see that, in contrast to our
normal number system:

• many numbers other than 0do not have amultiplicative inversemodulo another
number;
• there exist numbers other than 1 that are their own multiplicative inverse
modulo another number.
We begin with an example. Let us try to find the multiplicative inverse of
2 modulo 7. In other words, we need to find a number that, when multiplied
by 2, results in 1 mod 7. Recall that when working mod 7, the only numbers are
0, 1, 2, 3, 4, 5 and 6, so 2 cannot be the answer.