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) ofamodulon, which is denoted bya^{–1}, satisfiesa·a^{–1}1 (modn).For example, if

a= 29, thena^{–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:One complication is that not all choices for

awill have an inverse modn. One way to determine ifahas an inverse modnis to simply multiplyaby each of 0, 1, 2, . . . ,n– 1, and then look to see if any of the products is congruent to 1 (modn). For example, here's what we get fora= 29 andn= 78: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 andn= 78: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

ahave a multiplicative inverse modulon. Using the preceding applet to experiment would be tedious. To make matters easier, the applet below will take an integernas input, and will produce two lists of numbers: those values ofabetween 0 andn– 1 that have inverses, and those values ofabetween 0 andn– 1 that donothave inverses. For example, here's what we get forn= 10:Test out different values of

n, and try to determine which values ofawill appear for a given value ofn.

## Research Question 1

If

n> 0, what values ofa(between 0 andn– 1) will have an inverse modn?

Note:You may find it easier to think of this question in the following equivalent form: for which values ofadoes the congruence equationax1 (modn) have solutions?As you can see, the problem of finding an inverse for

amodulonis really a special case of the general problem considered in the Prelab discussion, namely, to solve the linear congruence equationaxb(modn).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

Copyright © 2001 by W. H. Freeman and Company