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.

  • $\begingroup$ (I'm posting this comment as an answer.) $\endgroup$ – Andrés E. Caicedo Jan 2 '11 at 20:19
  • $\begingroup$ Ah ok. That makes slightly more sense now. Thanks! $\endgroup$ – dhatch387 Jan 2 '11 at 20:21
  • $\begingroup$ The 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\;}$.) $\endgroup$ – Niel de Beaudrap Jan 2 '11 at 20:26
  • $\begingroup$ @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. $\endgroup$ – Andrés E. Caicedo Jan 2 '11 at 20:37
  • $\begingroup$ @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. $\endgroup$ – dhatch387 Jan 2 '11 at 20:41

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$.

  • $\begingroup$ This 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. cl.ly/3qGi $\endgroup$ – dhatch387 Jan 2 '11 at 20:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Arturo Magidin Jan 2 '11 at 20:41
  • $\begingroup$ ok thanks very much for the tips! $\endgroup$ – dhatch387 Jan 2 '11 at 20:50

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.)

  • 1
    $\begingroup$ I usually see the first meaning without the parenthesis, using $x\bmod m$ (use \bmod instead of \pmod: binary mod vs. parenthesis mod... $\endgroup$ – Arturo Magidin Jan 2 '11 at 20:23
  • $\begingroup$ @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.) $\endgroup$ – Andrés E. Caicedo Jan 2 '11 at 20:29

$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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.