Dec 312015
 

Addition in modular arithmetic is much simpler than it would first appear thanks to the following rule:

(a + b) \bmod{c} = (a \bmod{c} + b \bmod{c}) \bmod{c}

This says that if we are adding two integers a and b and then calculating their sum modulo c, the answer is the same as if we added a modulo c to b modulo c and then calculated that sum modulo c. Note that this equation can be extended to include more than just two terms.

Example
To show how this saves time and the use of a calculator, let’s look at a simple example. Suppose we needed to add a list of large numbers, but were only interested in the value of units the digit, aka the ones column, of the solution. Take:

3381 + 65 + 10346 + 573 + 12

That problem is too large to do in my head, but I could work it out on paper fairly easily. I could also hunt up a calculator, but there is a quicker  way still using the rule above.

In a decimal system, the units digit is really modulo 10 in disguise. Counting from 0:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

So when we are looking at the units digit of a decimal number of any length, we are really calculating that number modulo 10. BUT, the addition rule tells us that we don’t even to add up the whole list of numbers as they are to calculate the sum modulo 10. Instead, we first calculate each term modulo 10, and then sum those numbers. So,

3381 \bmod{10} = 1
65 \bmod{10} = 5
10346 \bmod{10} = 6
573 \bmod{10} = 3
12 \bmod{10} = 2

Now, that’s addition I can do in my head!

1 + 5 + 6 + 3 + 2 = 17

But wait! The sum is greater than 9 which is the reason for having to the sum modulo 10, one last time:

17 \bmod{10} = 7

If you’d worked the original addition problem out by hand or by calculator, you would have come to the same answer. The units digit is 7.

Proof

If you’ve read any of my math-related posts, you already know that it is not enough for me to know equations, but I also need to feel like I know how and why they work. In keeping with that neurotic tendency, I offer a proof for the modular addition rule.

Again, our equation is:

(a + b) \bmod{c} = (a \bmod{c} + b \bmod{c}) \bmod{c}

and our goal is to prove that the two sides of the equals sign are indeed equal to each other.

The key to doing this is the quotient remainder theorem, aka the Euclidean division algorithm. It tells us that we can rewrite a and b as:

a = cq_{1} + r_{1} where 0 \leq r_{1} < c this means that a \bmod{c} = r_{1}
b = cq_{2} + r_{2} where 0 \leq r_{2} < c this means that b \bmod{c} = r{2}

Examining the left hand side of the addition equation first, we have:

(a + b) \bmod{c} = (cq_{1} + r_{1} + cq_{2} + r_{2}) \bmod{c}
(a + b) \bmod{c} = (c(q_{1} + q_{2}) + r_{1} + r_{2}) \bmod{c}

Since we are taking \bmod{c}, we can eliminate multiples of c, leaving us with:

(a + b) \bmod{c} = (r_{1} + r_{2}) \bmod{c}

Now we move over to the right hand side of the equation.

(a \bmod{c} + b \bmod{c}) \bmod{c} = (r_{1} + r_{2}) \bmod{c}

Well, that was easy! The two sides of the equation are equal. The proof is done.

There is a similar rule and proof for modular subtraction. If I can keep my momentum, I will post it soon. But if you understood this one, working out the subtraction proof should be no problem at all.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)