0

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 ?

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
Ovi Poddar
  • 3
  • 2
  • What is your exact process? In your example, you took something mod $2$, and that thing was clearly an even number (since it's multiple of $10$, plus $6$), so of course the final answer is congruent to $2$ mod $2$. – Minus One-Twelfth Apr 03 '19 at 07:53
  • 1
    Welcome to Maths SX! What does 1256%11 denote? – Bernard Apr 03 '19 at 07:58
  • % @Bernard is often used in place of Mod(n,y) in Pari –  Apr 03 '19 at 09:41
  • if i want a number mod by another number, say, n mod m , and suppose n consists of 4 digits ,,,, if a take mod of the number consisting left 3 digits and then multiply by 10 , then add to remaining last digit of right side , and finally take mod of the number then i actually get exactly the same (n mod m) ! I want (1256 % 11)! if i try in this way, ( (125 % 11 ) * 10 + 6 ) % 11 = 2. That is exactly the same answer 2 ! how this works ? – Ovi Poddar Apr 03 '19 at 09:54
  • See https://en.wikipedia.org/wiki/Modular_arithmetic#Properties. From these rules you can see that $$ ax+b \equiv c\mod{m} \qquad \Leftrightarrow (a\mod{m}) x + b \equiv c \mod{m}$$ – Matti P. Apr 03 '19 at 10:05
  • If your original number is $ 10x+b$, you are observing that $(10x+b)\% n$ is the name as $((x\% n)\cdot 10 +b)\% n)$. To show this, try and show that in general, $\color{blue}{(ax)\% n = ((x\% n)a)\% n}$ and $(A+B)\% n = ((A\% n)+(B\% n))\%n$. – Minus One-Twelfth Apr 03 '19 at 10:08
  • thankss a lot ,,i have got the answer ! – Ovi Poddar Apr 03 '19 at 10:13
  • @OviPoddar I gave a careful proof of this special case in my answer. The proof generalizes to arbitrary *polynomial* expressions using induction. – Bill Dubuque Apr 03 '19 at 15:38

2 Answers2

1

The Congruence Sum & Product Rules imply that congruences are preserved if we replace $\rm\color{#c00}{arguments}$ of sums and products by $\rm\color{#0a0}{congruent}$ arguments. Applying this inductively shows the same holds true for arbitrary expressions composed of sums & products, i.e. polynomial expressions, yielding 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) arguments of the sums and products by a congruent argument (e.g. its modular reduction).

Yours is the special case below for the polynomial $\,10a+b,\,$ for modulus $\, n = 11,\,$ and $\,x' := x\bmod n = x\%11$.

$\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'\\ \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 also this answer.

Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
-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$$

  • Both 1 and 2 are incorrect - you need to apply a final mod to the product & sum of the remainders. Generally it is better to express these laws in [congruence form,](https://math.stackexchange.com/a/879262/242) then take the remainder only at the final step, using $\,a\equiv b\pmod{n}\iff (a\bmod n) = (b\bmod n)\ \ $ – Bill Dubuque Apr 03 '19 at 14:43
  • fine corrected the statements. –  Apr 03 '19 at 14:54