Section 5.2: Multiplicative Inverses

5.2 Multiplicative Inverses

Finding rational solutions to linear equations is easy because every nonzero rational number has a multiplicative inverse. Finding integer solutions to linear equations is a bit more complicated because the only integers which have integer multiplicative inverses are ±1.

A pleasant surprise is that when working modulo n, one frequently finds that many elements have multiplicative inverses. In this context, the multiplicative inverse (or just "inverse" for short) of a modulo n, which is denoted by a^–1, satisfies
a · a^–1 1 (mod n).
For example, if a = 29, then a^–1 35 (mod 78). We'll get to how to compute the inverse later in the chapter. For now, we can verify the claim with the following computation:
Your browser does not support java.
One complication is that not all choices for a will have an inverse mod n. One way to determine if a has an inverse mod n is to simply multiply a by each of 0, 1, 2, . . . , n – 1, and then look to see if any of the products is congruent to 1 (mod n). For example, here's what we get for a = 29 and n = 78:
Your browser does not support java.
As we can see, the output list contains a 1, which indicates that 29 has an inverse mod 78. Moreover, since the 1 appears in the 36th entry, this tells us that
29 · 35 1 (mod 78),
as above. On the other hand, here's what we get for a = 32 and n = 78:
Your browser does not support java.
There's no 1 in the list, so 32 does not have an inverse mod 78.

In the first research question, we address the question of which integers a have a multiplicative inverse modulo n. Using the preceding applet to experiment would be tedious. To make matters easier, the applet below will take an integer n as input, and will produce two lists of numbers: those values of a between 0 and n – 1 that have inverses, and those values of a between 0 and n – 1 that do not have inverses. For example, here's what we get for n = 10:
Your browser does not support java.
Test out different values of n, and try to determine which values of a will appear for a given value of n.

Research Question 1

If n > 0, what values of a (between 0 and n – 1) will have an inverse mod n ?

Note: You may find it easier to think of this question in the following equivalent form: for which values of a does the congruence equation ax 1 (mod n) have solutions?

As you can see, the problem of finding an inverse for a modulo n is really a special case of the general problem considered in the Prelab discussion, namely, to solve the linear congruence equation
ax b (mod n).
We take up this problem in the next section.

Section 5.1 | Section 5.2 | Section 5.3 | Section 5.4 | Section 5.5 | Section 5.6
Chapter 5 | DNT Table of Contents