It seems to me that a = x (mod m) can mean either that a is the remainder of x divided by m or that the remainders of a and x are the same when divided by m (eg. with respect to mod m). For example: 2 = 6 (mod 4) would be the first meaning I discussed, but 6 = 2 (mod 4) would be the second. It seems that I must be confusing some aspect of modular arithmetic here. Thanks for the assistance.
How can a = x (mod m) have multiple meanings in modular arithmetic?
-
0(I'm posting this comment as an answer.) – 2011-01-02
-
0Ah ok. That makes slightly more sense now. Thanks! – 2011-01-02
-
0The first statement, that $a$ is the remainder upon dividin $x$ by $m$, does not have any standard mathematical notation as far as I'm aware. (The closest approximation is to say that it is equivalent to the C/C++ assertion $\mathtt{a == x\;\%\;m\;}$.) – 2011-01-02
-
0@Niel: Some of the "introduction to discrete mathematics" books now use the first notation. I've actually never encountered it other than in such books. – 2011-01-02
-
0@Niel @Andres I'm currently working on a paper on cryptography and in many cases the first notation I discussed are used. My confusion seems to have come from that some of my sources use = instead of ≡ in the second situation. – 2011-01-02
-
0@Andres @dhatch387 : it doesn't surprise me much that some notation should (at long last) arise, but it disappoints me that it should be such an easily confusable one. I would want it at least to be something like an infix $\mu$ operator. – 2011-01-02
-
0I have a second related question that perhaps some of you could answer if you wouldn't mind. Would greatly appreciate it. http://math.stackexchange.com/questions/16164/is-there-a-theorem-based-on-substitution-to-convert-a-congruency-to-an-equality – 2011-01-02
3 Answers
No; $a\equiv b \pmod{m}$ means that $a$ and $b$ are congruent modulo $m$: by definition, the meaning is that $m$ divides $a-b$. As it happens, this is equivalent to saying that $a$ and $b$ have the same remainder when divided by $m$.
However, there is also a related notation, in which "mod" acts as a binary operator: in computer science especially, one often finds expressions like "$a \bmod m$"; in this case, this is interpreted as an operation on $a$ and $m$ that results in the remainder when $a$ is divided by $m$ (usually the one among $0$, $1,\ldots,m-1$, but in some instances instead the ones with smallest absolute value, allowing negative remainder).
But these two are related-but-different. In $a\equiv b\pmod{m}$, what we have is a binary relation between $a$ and $b$, called "congruence modulo $m$", and written $\equiv\pmod{m}$. In $a\bmod m$, what we have is a binary operation (noncommutative) on $a$ and $m$.
-
0This makes sense to me. Would you mind confirming that the statements I made in this paragraph are correct? I've become confused because many sources seem to use = and ≡ interchangeably. http://cl.ly/3qGi – 2011-01-02
-
0@dhatch387: I would not say "$a$ is the same as $x$ with respect to modulo $m$"; standard is to say that $a$ is *equivalent* to $x$ *modulo* $m$ (no "with respect to"). I am not familiar with your use of "a modulo", and writing "numbers from $0-m$" is ungrammatical and incorrect given what you mean (should be "from $0$ to $m-1$"). The next sentence has an imprecise clause ("this equation", which in any case should be "congruence", when there are many congruences previously mentioned). And "$x \pmod{m} = mk + x$" does not abide by either of the notational conventions I mentioned. – 2011-01-02
-
0ok thanks very much for the tips! – 2011-01-02
I think you are mixing notation here; perhaps using some superfluous parentheses may help:
$a=(x\pmod m)$ has the first meaning you said: $a$ is the remainder of dividing $x$ into $m$; while $(a=x)\pmod m$ would have the second meaning: $a$ and $x$ have the same remainder when divided by $m$.
To avoid confusion, it is customary to write the second expression as $a\equiv x\pmod m$. This way, if you see $=$ you know you are using the first meaning, if you see $\equiv$, it is the second.
(Of course, every now and then, books mix the two notations, hopefully in contexts where which one is intended is clear.)
-
1I usually see the first meaning without the parenthesis, using $x\bmod m$ (use `\bmod` instead of `\pmod`: *binary* mod vs. *parenthesis* mod... – 2011-01-02
-
0@Arturo: Thanks for the LaTeX tip; I find that my formatting gets worse with age! (And I think it is too bad such similar notations are used for subtly different notions, which may confuse people unnecessarily when first learning the concepts.) – 2011-01-02
$a = (x~ \mathrm{mod} ~m)$ means $a$ is the remainder when $x$ is divided by $m$.
$a \equiv x~ (\mathrm{mod} ~m)$ means $a$ and $x$ have the same remainder when divided by $m$.