0
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Great, got it.. $\endgroup$ – oopsi Mar 5 '13 at 16:46
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.