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?
0
$\begingroup$
$\endgroup$
-
1$\begingroup$ I took the liberty of converting to more standard mathematical notation. $\endgroup$ – Brian M. Scott Mar 5 '13 at 16:42
-
2$\begingroup$ 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\}$. $\endgroup$ – anon Mar 5 '13 at 16:49
2
$\begingroup$
$\endgroup$
HINT: Try to express $a$ as $(b \times k) + c$ and then proceed
0
$\begingroup$
$\endgroup$
$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.
0
$\begingroup$
$\endgroup$
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.
