1

I need to prove that $$(ab)\bmod m = \bigl((a \bmod m)(b \bmod m)\bigr)\bmod m,$$ but I don't know why the last "$\mathop{\bmod} m$" is there.

dfeuer
  • 9,069
Emilio B.
  • 79
  • 5
  • 3
    It might be needed. For example, $a = b = 4$ and $m = 5$. – Tunococ Sep 26 '13 at 23:25
  • I don't know if this is a course you're taking, but to avoid confusion with the usual use of $\mod m$; one might write $r_m(ab)=r_m(r_m(a)\cdot r_m(b))$, that is, the remainder when $ab$ is divided by $m$ equals the remainder of the product of the remainder of each factor separately. This just means that when multiplying out the remainders $r_m(a)$ and $r_m(b)$ one might need to carry out one more division so this number is indeed a remainder $\mod m$. – Pedro Sep 26 '13 at 23:39
  • @PedroTamaroff, I suspect this usage is more CSish than mathy, reflecting the use of $\bmod$ as a sort of remainder operator in several programming languages. My own take is that the "usual" notation $a\equiv b\pmod n$ is the oddball, and it makes a lot more sense to write something (non-standard?) like $a\equiv_n b$, as my current teacher does. – dfeuer Sep 26 '13 at 23:47
  • @dfeuer Well, if context is understood, one simply writes $a=b$. =) – Pedro Sep 26 '13 at 23:53
  • @PedroTamaroff, I firmly believe that using $a=b$ to mean anything other than $a=b$ is playing with fire, one of the most effective ways to introduce errors into a proof. – dfeuer Sep 26 '13 at 23:58

2 Answers2

1

One may say the last $\bmod m$ is there to insure that your $(a \bmod m)(b \bmod m)$ is in $\mathbb Z_m$ ($\mathbb Z_m$ being the set of non-negative integers less than $m$, $\Bbb Z_m = \{0, 1, 2, ..., m-1\}$.)

Alternatively, here's another way of saying exactly what you're trying to prove:

If $a\equiv i \pmod m$ and $b\equiv j \pmod m$, then $ab\equiv ij \pmod m$.

dfeuer
  • 9,069
Patterns_43
  • 94
  • There's a piece missing here, which is the relationship between $\Bbb Z_m$ and congruence modulo $m$, or prett much equivalently $\Bbb Z/m\Bbb Z$, which is the division theorem. – dfeuer Sep 26 '13 at 23:52
1

What "$\bmod\,m$" means here is "take the remainder when you divide by $m$". The reason the last one is there on the right hand side (RHS) is because $(a \bmod m)(b \bmod m)$ could still be larger than $m$. For example suppose $a=7,b=8,m=5$ then $(a \bmod m)(b \bmod m)=(2)(3)=6$ which is larger than $5$. On the LHS we would have $ab \bmod m=7*8 \bmod 5=56 \bmod 5=1$. So you can see that we need that last $\bmod\,m$ on the RHS to make the two sides equal.

By the way, people usually use "$\bmod\,m$" to mean something slightly different. They write it after an equation, like this:$$(m+3)^2\equiv 9 \pmod m$$ When people use "$\bmod\,m$" like this, it isn't applying to the right hand side of the equation. Instead it's applying to the whole equation. What it means is that the remainder we get when we divide the RHS by $m$ is the same as the remainder we get when we divide the LHS by $m$. People use a weird equals sign with three lines to remind themselves that this isn't true equality, but only equality $\bmod\,m$ (although sometimes people get sloppy and use $=$).

EDIT: Mathematicians normally use "$\bmod\,m$" applied to the whole equation. Programmers normally use it as an operator, like you're using it (sometimes they use the symbol '$\%$'). Programmers also distinguish between variants that give different results depending on the sign of the operands, one form more useful and intuitive and the other more efficient: see this SO question.

Community
  • 1
Oscar Cunningham
  • 16,299