Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Modular Arithmetic

Date: 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/ 
Associated Topics:
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/