Jan 292017

Binary NumbersAbraham Lincoln once famously said, “Everybody loves a compliment.”  I suspect that if he had been a mathematician he would have loved complements, too. We’ve already seen what complements are and talked about the two most prolific: the radix complement and the diminished radix complement. Now it’s time to explore how we can leverage complements to do some really interesting integer arithmetic. Using complements we can subtract one positive integer from another or add a negative integer to a positive one by simply performing addition with two positive integers. The algorithm behind this black magic is called the Method of Complements.

Continue reading »

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. Continue reading »

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. Continue reading »