next up previous
Next: Which mod m numbers Up: Contents Previous: Modular division via the

Inverting modular-arithmetic functions

We can use what we know about division to find the inverse of some functions. Consider the function

displaymath121

with a domain of tex2html_wrap_inline123 . The rule says to multiply the input by 3 and then add 1. Intuitively, the rule for the inverse should just reverse this process: subtract 1, then divide by 3. In fact, mod 7 we can divide by 3 by just multiplying by 3's multiplicative inverse (which is 5), so this rule makes sense modulo 7 as well. We get the following rule for the inverse.

displaymath125

Can we do the same calculations modulo 15? As mentioned above, many mod 15 standard names, including 3, do not have multiplicative inverses. So consider the function

displaymath127

with domain tex2html_wrap_inline129 . We've simply changed the modulus from 7 to 15. Since 3 does not have a multiplicative inverse modulo 15, it's not so clear you can properly reverse the process. In fact, this function is not invertible. For example, tex2html_wrap_inline133 .



Lisa Eckstein
Mon Oct 21 22:56:24 EDT 1996