2

Written in Abstract Algebra by T. W. Judson, in an example in the theory of rings it supposes (without proof) that: $$(a+b) \bmod n = (a \bmod n) + (b \bmod n) $$ and $$ ab \bmod n = (a \bmod n) · (b \bmod n).$$

I am trying to prove them but I can't.

$((a+b) \bmod n)$ means that there is an integer $k$ such that $0\le a+b-nk<n$, and $(a \bmod n) + (b \bmod n)$ means there are integers $k_1$ and $k_2$ such that $0\le a-nk_1<n$ and $0\le b-nk_2<n \implies 0\le a+b-n(k_1+k_2)<2n$ which has no relation to the $0\le a+b-nk<n$ especially resulting same numbers to say they are equal.

Edit - Here it is an incomplete proof for the first part of my questions, but it does not show how $(a \bmod n + b \bmod n) \bmod n = (a \bmod n + b \bmod n)$ in the last step?

Ernie060
  • 6,073
  • 5
    Something is missing I think. There might need to be a final $\pmod{n}$ or something. Otherwise you have something like $2=4\times3 \pmod{5}=(4\pmod{5}) \times (3 \pmod{5})=12$ –  Oct 20 '15 at 03:09
  • @avid19 - yes you are right, the book is missing it so the answer in http://math.stackexchange.com/questions/582719/prove-a-b-mod-n-a-mod-n-b-mod-n-mod-n is correct. Thank you for your example. :) –  Oct 20 '15 at 03:17

2 Answers2

4

First reduce mod $n$. So write $a \equiv r \mod n$ and $b \equiv s \mod n$ where $r,s \in \mathbb{Z}_{n}$ and $0 \leq r,s \leq n-1$. So then you may write $a = in + r$ and $b = jn + s$ where $i,j \in \mathbb{Z}$. Then it follows that $$ a + b = (in + r) + (jn + s) = (i + j)n + (r + s) \equiv r + s \mod n, $$ and $$ ab = (in + r)(jn + s) = ijn^2 + (is + jr)n + rs \equiv rs \mod n $$ as desired.

Oiler
  • 3,413
0

The above answer said it well. Said in plainer english with a numerical example, the mod function strips away all but the "ones" place.

Look at the equation 15*27=405.

15*27 (mod 10) = 405 (mod 10) = 5

15 (mod 10) * 27 (mod 10) = 5 * 7 = 35. And 35 (mod 10) = 5.

An important observation to make is that the tens place of the multiplicand and multiplier never carry over into the ones spot:

25*27 (mod 10) = 675 (mod 10) = 5.

35*27 (mod 10) = 945 (mod 10) = 5.

An incremental increase in the 10s place merely adds 10*27 to the answer, which doesn't change the one's place. So to find the answer to "A*B (mod 10)" all you need to do is find: "the one's place of A" and "the one's place of B"

Similarly, if you instead used base N instead of base 10 to write out your numbers A and B, you'd find the exact same pattern.

Naturally, however, this pattern is quite non-intuitive when using a mod that is unequal to your base. The key, for me at least, to understanding mods was in realizing that we only use base 10 because of convention.

Modular problems can be much more easily solved if numbers were given in terms of base n. That's why it's trivial for humans to take a massive base 10 number and mod it by 10. (19578372364 mod 10) = 4.

Ari Sweedler
  • 111
  • 3