Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
I took the liberty of converting to more standard mathematical notation. –  Brian M. Scott Mar 5 '13 at 16:42
2  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.