Last time we showed how you can take any two coprime positive integers x and m and compute a third positive integer y with the property that (x * y) % m == 1, and therefore that (x * z * y) % m == z % m for any positive integer z. That is, there always exists a “multiplicative inverse”, that “undoes” the results of multiplying by x modulo m. That’s pretty neat, but of what use is it?
Continue reading →

Here’s an interesting question: what is the behavior of this infinite sequence? WOLOG let’s make the simplifying assumption that x and m are greater than zero and that x is smaller than m. Continue reading →

Now that we have an integer library, let’s see if we can do some 2300-year-old mathematics. The Euclidean Algorithm as you probably recall dates from at least 300 BC and determines the greatest common divisor (GCD) of two natural numbers. The Extended Euclidean Algorithm solves Bézout’s Identity: given non-negative integers a and b, it finds integers x and y such that:

a * x + b * y == d

where d is the greatest common divisor of a and b. Obviously if we can write an algorithm that finds x and y then we can get d, and x and y have many useful properties themselves that we’ll explore in future episodes.

Continue reading →

Now we come to the controversial one. As I pointed out back in 2011, the % operator is the remainder operator. When extending the division and remainder operators from naturals to integers, I require that the following conditions be true for dividend x, non-zero divisor y, quotient q and remainder r:

• x == y * q + r
• if x and y are non-negative then 0 <= r < y
• (-x) / y == x / (-y) == -(x / y)

Let’s take a look at the consequences of these three facts. Continue reading →