Associated Topics || Dr. Math Home || Search Dr. Math

### Reverse Modulus Operator

```
Date: 10/09/2001 at 07:13:05
From: Charles
Subject: Reverse modulus operator

In mathematics, for each action we do, there is normally a reverse
action that allows us to get back to the original two numbers. This
can be seen in the relation between addition and subtraction,
multiplication and division, or even logarithmic and exponential
functions.

I am curious to find out if there is an operator that would return 2
when we we do 6 * 0, * being this new operator.
```

```
Date: 10/09/2001 at 11:57:20
From: Doctor Roy
Subject: Re: Reverse modulus operator

Hello,

Thanks for writing to Dr. Math.

I assume that you mean the modulus operator as used in computer
science, i.e.  6 mod 2 = 0.

There cannot possibly be a well-defined inverse operation. This can be
seen easily following this example:

6 mod 2 = 0
6 mod 3 = 0

Let's call the inverse operation invmod

6 invmod 0 = ?    2 or 3 or 1 or 6 or ?

Since there cannot be a single value that satisfies this operation, it
is not well-defined.

It turns out that there are several operations that work in one
direction and have no inverse operation.

I hope this helps.

- Doctor Roy, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 10/09/2001 at 12:15:03
From: Doctor Peterson
Subject: Re: Reverse modulus operator

Hi, Charles.

Interesting question! I don't think the final answer will be what you
want, but the thinking on the way there will be worth having gone
through.

You have probably learned about inverse functions, and know that not
every function has an inverse. The same is true of inverse operations.
The existence of an inverse is not "normal," but a very special
situation. The reason you think of it as normal is that invertible
operations are particularly useful, so we tend to use them and give
them names. Among familiar operations, therefore, invertibility is
common, though not by any means universal.

Also, it's worth noting that not all operations are commutative, as
addition and multiplication are. When an operation is not commutative,
you have to be careful about order, and it turns out that there are
two different kinds of inverse you can talk about. For addition, the
inverse operation, subtraction, is defined by

(x + y) - y = x

(x - y) + y = x

We can call subtraction the "right inverse" of x, since doing it on
the right of an addition undoes that addition. (I'm not positive that
this is a standard term in this context, but I think it's right.) If
we try to make subtraction a "left inverse," we find that it doesn't
quite work:

x - (x + y) = -y

x + (x - y) = -y

That happens because subtraction is not commutative.

is defined by

x mod y = z  if x = ny + z for some integer n, and 0 <= z < y

(I'll ignore questions that arise if x or y are negative.)

Apparently you want a left inverse of the mod operation, which we'll
call "*", that gives the divisor when you know the dividend and
remainder, so that if

x mod y = z         e.g. 6 mod 2 = 0

then

x * z = y           e.g. 6 * 0 = 2

This can be written as

x mod (x * z) = x   e.g. 6 mod (6 * 0) = 0

x * (x mod y) = y   e.g. 6 * (6 mod 2) = 2

The problem is that there is not just one divisor for a given dividend
and remainder:

6 mod 1 = 0

6 mod 2 = 0

6 mod 3 = 0

6 mod 6 = 0

Which of 1, 2, 3, and 6 should be the result of 6*0?

The same sort of problem occurs with the "right inverse," which gives
the dividend given the divisor and remainder:

(z ** y) mod y = z   e.g. (0 ** 2) mod 2 = 0

and

(x mod y) ** y = x   e.g. (6 mod 2) ** 2 = 6

This time, we see that

2 mod 2 = 0

4 mod 2 = 0

6 mod 2 = 0

and so on, so there are many solutions to the equation

x mod 2 = 0

and no one value to choose for 0 ** 2.

Just as with functions, the fact that the "mod" operation takes
multiple inputs to the same output makes an inverse operation
impossible.

However, just as we have an inverse function "square root" that
inverts the square function _when we restrict the domain of the
latter_, we can do the same here. It's not very useful, however. Note
that

x mod y = x  when 0 <= x < y

so if we restrict the function f(x) = x mod y to that domain, the mod
function becomes the identity function f(x) = x. Therefore, the
inverse operation is simple:

x ** y = x when 0 <= x < y

What this does is to find ONE of many possible dividends that give the
desired remainder, namely the remainder itself. Another approach would
be to have a multivalued "function" that gives ALL possible dividends;
this is

x ** y = x + ny, for any integer n

It's a little more complicated to do this for your "*" operation. Here
you would want to find either one, or all, divisors that leave the
given remainder. Given that

x mod y = z

we can express this as

x = ny + z for some integer n

To solve for y, we get

y = (x-z)/n, for any integer n that divides (x-z)

Therefore,

x * z = 1

or

x * z = x - z

or

x * z = smallest factor of x-z greater than 1

are possible partial inverse operations that give ONE possible
divisor; and

x * z = all divisors of x-z

gives all possible answers. But that doesn't really give you what you
wanted, does it? Defining the inverse doesn't help in actually doing
it.

You may be interested in these answers related to the mod function:

What is Modulus?
http://mathforum.org/library/drmath/view/54363.html

Mod Function and Negative Numbers
http://mathforum.org/library/drmath/view/52343.html

Inventing an Operation to Solve x^x = y
http://mathforum.org/library/drmath/view/54586.html

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Functions
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search