Jul 162017
 

An arithmetic sequence of numbers, sometimes alternatively called an arithmetic progression, is a sequence of numbers in which the difference between all pairs of consecutive numbers is constant. A very simple arithmetic sequence consists of the natural numbers: 1, 2, 3, 4, … where the difference between any number and the number before it is just one. 3, 7, 11, 15, 19, …. is another arithmetic sequence, but in this case the constant difference between elements is four.

A finite portion of an arithmetic sequence like 2, 3, 4 or 7, 11, 15 is called a finite arithmetic progression. To confuse matters, sometimes a finite arithmetic progression, like an arithmetic sequence, is also called an arithmetic progression. To be safe, when a progression is finite, I always say as much.

An arithmetic series is the sum of a finite arithmetic progression.  An arithmetic series consisting of the first four natural numbers is 1 + 2 + 3 + 4. The sum, 10, is trivial to compute via simple addition, but for a longer series with larger numbers, having a formula to calculate the sum is indispensable.

Continue reading »

Mar 092016
 

This is going to be another one of my “selfish” posts – written primarily for me to refer back to in the future and not because I believe it will benefit anyone other than me. The idea is one that I always took for granted but had a hard time proving to myself once I decided to try.

Theorem: Suppose we have an M bit unsigned binary integer with value A. Consider the first (least significant) N bits with value B. Then:

A \equiv B \bmod{2^N}

Put another way, arithmetic with unsigned binary integers of a fixed length N is always performed modulo 2^N.
Continue reading »

Jan 122016
 

It is no big secret that exponentiation is just multiplication in disguise. It is a short hand way to write an integer times itself multiple times and is especially space saving the larger the exponent becomes. In the same vein, a serious problem with calculating numbers raised to exponents is that they very quickly become extremely large as the exponent increases in value. The following rule provides a great computational advantage when doing modular exponentiation.

The rule for doing exponentiation in modular arithmetic is:

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

This states that if we take an integer a, raise it to an integer power b and calculate the result modulo c we will get the same result as if we had taken a modulo c first, raise it to b, and calculate that product modulo c.

Continue reading »

Jan 022016
 

I must stay focused. I must stay focused. I must stay … I wonder what’s new on Facebook.

I don’t really feel like writing this post mostly because I know that it will be very similar to the other two I have already done: modular addition rule proof and modular subtraction rule proof, but my New Year’s Resolution is to follow things through to completion. Well, that would’ve been my News Years resolution if I had made one. Either way, it’s back to modular arithmetic.

The rule for doing multiplication in modular arithmetic is:

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

This says that if we multiply integer a times integer b and take the product modulo c, we get the same answer as if we had first taken a modulo c and multiplied by b modulo c and taken that product modulo c.

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 »

Aug 132015
 

Bust of Pythagoras

Pythagoras of Samos
[ccbysa3]

a^2 + b^2 = c^2

It may very well be the second most famous equation of all time, outshone only by that braggart Einstein’s mass–energy equivalence equation. But for those of us that aren’t theoretical physicists, the Pythagorean Theorem is likely to play a fundamental role in many of the calculations we do whether we realize it or not.

Everyone knows the equation, but before we get into it’s proof, let’s re-cap what it means. Consider the following right triangle:

A right triangle

This triangle has sides a, b and hypotenuse c. The Pythagorean Theorem simply tells us then that the square of the length of the hypotenuse (c^2) is equal to the square of the length of side a plus the square of the length of side b (a^2 + b^2).  Well, duh. And after we learn it in middle school many of us take it as axiomatic, but it does have “theorem” in it’s name so I feel its worth revisiting it’s proof every once in a while to keep me on my toes.

Continue reading »