# How can a = x (mod m) have multiple meanings in modular arithmetic?

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.

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

• 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 – dhatch387 Jan 2 '11 at 20:35
• @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. – Arturo Magidin Jan 2 '11 at 20:41
• ok thanks very much for the tips! – 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.)

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