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. You are asking about the "mod" (remainder) operation. Recall that this 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 This one, about inverse operations, is also worth reading: 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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.