Dec 312015
 

I’ve already presented and proved the rule for modular addition, so for a sense of completeness, but mostly to satisfy my OCD, now I’ll cover the rule for modular subtraction. When doing subtraction in modular arithmetic, the rule is:

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

If we subtract integer b from integer a and calculate the difference modulo c, we get the same answer as if we had subtracted b modulo c from a modulo c and then calculated that difference modulo c. Like the modular addition rule, this rule can also be expanded to include multiple integers.

Proof

In order to prove that the two sides of the equations are equal to one another, we again redefine a and b using the quotient remainder theorem:

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}

Starting with the left hand side of the equation, 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}

Eliminating multiples of c since we are doing \bmod{c} leaves us with:

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

The right hand side only requires a simple substitution and we’re done:

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

 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)