# Proof that $(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$

I'm trying to prove this kinda of trivial modular attribute, but keep failing.

$$(a\cdot a)\bmod b=\Big((a\bmod b)\cdot(a\bmod b)\Big)\bmod b$$

Any ideas?

• I took the liberty of converting to more standard mathematical notation. – Brian M. Scott Mar 5 '13 at 16:42
• More generally, $\rm x=an+b$ and $\rm y=cn+d$ yield $$\rm xy=(an+b)(cn+d)=(acn+bc+ad)n+bd$$ Hence $\rm x\equiv b,~y\equiv d\bmod n \implies xy\equiv bd\bmod n$. This holds even if $\rm b,d$ are not chosen among the usual representatives $\rm\{0,1,\cdots,n-1\}$. – anon Mar 5 '13 at 16:49

HINT: Try to express $a$ as $(b \times k) + c$ and then proceed

• Great, got it.. – oopsi Mar 5 '13 at 16:46

$a = (a \mod b) \mod b$ and by compatibility with multiplication (by itself) you get $a*a = (a\mod b)*(a \mod b) \mod b$ and since $a*a=((a*a)\mod b) \mod b$ you get your result.

To prove that $\rm\,\ a^2\bmod b\ =\, (a\bmod b)^2 \bmod b,\:$ since $\rm\,\ x\equiv y\,\ (mod\ b)\, \Rightarrow\, (x\ mod\ b) = (y\ mod\ b),$

it suffices to prove $\rm\ \ \ \ a^2 \equiv\ (a\bmod b)^2\ (mod\ b).\$ But that's a special case of

$\rm\qquad\qquad\quad mod\ b\!:\,\ \begin{eqnarray} a\,\equiv\, \hat a\\ \rm c\,\equiv\, \hat c\end{eqnarray}\ \Rightarrow\ ac\,\equiv\, \hat a\hat c,\ \$ the Congruence Product Rule

Remark $\$ Generally, as above, when proving ring theoretical properties of the mod operation, it is simpler, conceptually and computationally, to work with the associated congruence relation, i.e. work $\,\rm(mod\ b),\,$ in a quotient ring.