Why can we modular reduce arguments of sums and products in modular arithmetic?

Question

Suppose,I have a number 1256. I want (1256 % 11)! That is 2 . But, here, if i try in this way, ( (125 % 11 ) * 10 + 6 ) % 11 = 2. That is exactly the same answer 2 as above.

I am confused , how This two process gives the similar answer ??? Even if , I try this method for any number n,m to find (n mod m) . How this works ?? Can anybody explain ?

Answer 1

Two modular arithmetic rules you are missing:

1. The product of remainders, is congruent to the remainder of the unmodded product.
2. The sum of remainders, is congruent the remainder of their unmodded sum.

that means you can turn both into:$$1000\bmod 11+200\bmod 11+50\bmod 11+6\bmod 11 = (10+2+6+6)\bmod 11=10+2+12 \bmod 11 =10+2+1\bmod 11 =11+2\bmod 11= 2\bmod 11$$

Answer 2

The Congruence Sum & Product Rules imply that replacing $\rm\color{#c00}{arguments}$ of sums and products by $\rm\color{#0a0}{congruent}$ arguments yields a congruent sum or product. Applying this inductively (cf. Note below) shows the same holds true for arbitrary "polynomial" expressions composed of sums and products, yielding a multivariate form of the linked (univariate) Polynomial Congruence Rule. In particular this implies that for any such arithmetical expression we obtain a congruent expression if we replace (some or all) arguments of its sums and products by their $\rm\color{#0a0}{(congruent)}$ remainders.

Yours is the special case below for the polynomial $\,10a+b,\,$ for modulus $\, n = 11.\,$ For completeness, below we give a direct proof of this special case of the above sketched proof.

$\left.\begin{align}{\bf Theorem}\ \ \bmod n\!:\,\ \color{#c00}{a'}\equiv \color{#0a0}a\\ b'\equiv b\end{align}\right\}\, $ $\Rightarrow$ $\,\ \begin{align} &10\,\color{#c00}{a'}+b'\ \ \ \ [\:\!x' = x\bmod 11 = x\% 11\,\ \rm in\ OP]\\ \equiv\ &10\,\color{#0a0}a\,+\,b\end{align}$

$\begin{align}{\bf Proof}\qquad a'&\equiv a\qquad\quad\ \, \text{by hypothesis}\\ 10a'&\equiv 10a\qquad\ \ \text{by the Congruence Product Rule}\\ b'&\equiv b\qquad\quad\ \ \text{by hypothesis}\\ \Rightarrow\ 10a'+b'&\equiv 10a+b\ \ \ \text{by the Congruence Sum Rule} \end{align}$

Remark $ $ To get the exact form of your result apply a final $\bmod 11\,$ to the above to convert it from a congruence relation to a mod operation (remainder), using the following $$ a\equiv b\!\!\!\pmod{n}\iff (a\bmod n) = (b\bmod n) $$

Generally this is the easiest way to prove identities about mod operations, i.e. use more flexible congruences to first prove the analogous congruence relation, then apply a final mod operation to get (canonical / normal) remainders (or residues).

See this answer for another worked example: $\,(g^b \bmod m)^a \bmod m = (g^a \bmod m)^b \bmod m$

Note we induct on the "height" of the expression = the total number of sum & product operations. The base case of height $= 0\,$ has no operations so the expression is an integer, so any replacement by a congruent integer yields a congruent result. Else the expression is a sum or product. Its arguments have smaller height (since they exclude this operation), so by induction any replacements yield a congruent argument, so this sum or product remains congruent by the congruence sum or product rule.