Modular ArithmeticDate: 01/26/2006 at 22:51:53 From: Dennis Subject: Confused with a = b(mod m) Can you explain why if a = b(mod m), then a = b mod m(mod m), b = a mod m(mod m), and a mod m = b mod m? Date: 01/27/2006 at 15:38:06 From: Doctor Vogler Subject: Re: Confused with a = b(mod m) Hi Dennis, Thanks for writing to Dr. Math. I think the confusion is that there are two ways that the word "mod" can be used. Computer programmers tend to think of it as an operation, like addition and subtraction, that takes in two numbers and returns their "mod." For example, in the C programming language you write % for mod, and you would have 17 % 5 == 2. In this case, a mod b means to divide a by b and return the remainder. There are debates about whether the remainder should always be between 0 and b-1, or whether the remainder should have the same sign as a, or various other variations. Such details can be chosen arbitrarily to suit your needs. I tend to lean towards the first variation, that the remainder should always be nonnegative, between 0 and b-1. But that's not how mathematicians mean "mod." A mathematician writes a = b (mod m) (and often uses three horizontal lines instead of two to mean "a is congruent to b" instead of "a equals b"), and he means that a and b have the same remainder mod m, or, equivalently, that the difference a - b is divisible by m. Notice that the difference is that the "mod m" on the right is not meant to operate on a or b, or both a and b, but rather is meant to explain what the equals sign (or congruence sign) means. In particular, it says that the = does not mean "are the same integer" but rather means "are congruent mod m," that is, "have a difference that is divisible by m." So, for example, a mathematician would write 17 = 2 (mod 5), but it would also be true that 17 = -3 (mod 5), 17 = 22 (mod 5), 17 = 17 (mod 5). Now, let's look again at your question. If you meant the computer programmer idea of using mod as an operator, then a = (b mod m) would have to mean that a is the remainder on dividing b by m. In particular, it means that a is between 0 and m-1. You would also notice that b mod m = (b mod m) mod m, but it would not follow that b = (a mod m) or (a mod m) = (b mod m). If, on the other hand, you mean the mathematician's idea of mod, then a = b (mod m) is certainly equivalent to b = a (mod m) but it makes no sense to write more than one mod, as in a = b mod m (mod m) or a mod m = b mod m. For more information on modular arithmetic, see the article Mod, Modulus, Modular Arithmetic http://mathforum.org/library/drmath/view/62930.html or our section on modular arithmetic at Modular Arithmetic http://mathforum.org/library/drmath/sets/select/dm_mod.html If you have any questions about this or need more help, please write back, and I will try to offer further advice. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/