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.

static IEnumerable Sequence(Integer x, Integer m)
{
  Integer c = Integer.Zero;
  while(true)
  {
    yield return c;
    c = (c + x) % m;
  }
}

Given positive x and m clearly the value of c must always be greater than or equal to zero and less than m. Since the next number is determined only from the previous number and the parameters, this must go into a cycle that is no longer than m. How long is the cycle?

Integer i1 = Integer.One;
Integer i5 = i1 + i1 + i1 + i1 + i1;
Integer i16 = i5 + i5 + i5 + i1;
foreach(Integer i in Sequence(i5, i16).Take(17))
    Console.WriteLine(i);

Produces the sequence 0, 0101, 01010, 01111, 0100, 01001, 01110, 011, 01000, 01101, 010, 0111, 01100, 01, 0110, 01011, 0 in binary, or 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 1, 6, 11, 0 in decimal. The cycle is as long as possible. By contrast, choosing x as four would give the cycle 0, 4, 8, 12, 0 — a cycle of length four.

It should be pretty clear why the second cycle is shorter; there’s no way for it to ever get to any number not evenly divisible by four. And in fact there is a general principle here: iff x and m have no divisors in common other than one then the cycle is of length m. Another way of saying that is that GCD(x, m) is one; yet another way of saying that is that x and m are coprime, or relatively prime. (Because they have no common factors that are any prime number.)

Now, we have a word for “repeatedly sum up a value x, y times, starting from zero” and that’s multiplication. Essentially what we’ve done here is defined a new kind of multiplication, but this time it is multiplication that takes three numbers: x, y and m. One might even call it “multiplication modulo m”. And moreover we know that if 0 <= y < m and GCD(x, m) = 1 then x * y is different for each y.

This means that given coprime x and m there is a unique number 0 <= y < m such that x * y = 1. That is an interesting number because it is the number that “undoes” multiplication by x. That is, if x and y are multiplicative inverses of each other then

 (x * z * y) % m == z % m

for any z because the x and y multiply to one. What is that number y given some coprime x and m? We want:

(y * x) % m = 1

Go back to the definition of remainder. The remainder relates the quotient q and the remainder, in this case one, as:

y * x = q * m + 1

So we need to be able to find values y and q such that:

y * x - q * m = 1
y * x - q * m = GCD(x, m)

But we wrote a method to do that last time! This is Bezout’s Identity again. We have everything we need already written; we just need to wrap some methods around it:

public static Integer AbsoluteValue(this Integer a)
{
    return a < Integer.Zero ? -a : a;
}
public static Integer Modulus(this Integer x, Integer modulus)
{
    Integer result = x % modulus;
    return result < Integer.Zero ? result + modulus : result;
}
public static bool IsCoprime(this Integer a, Integer b)
{ 
    return GreatestCommonDivisor(a, b).AbsoluteValue() == Integer.One;
}
public static Integer MultiplicativeInverse(this Integer x, Integer modulus)
{
    if (x <= Integer.Zero)
        throw new ArgumentException("x");
    else if (modulus <= Integer.Zero)
        throw new ArgumentException("modulus");
    else if (!IsCoprime(x, modulus))
        throw new ArgumentException("modulus");
    else
        return ExtendedEuclideanDivision(x, modulus).Item1.Modulus(modulus);
}

So now we can plug in i5 and i16 and get out that the multiplicative inverse of 5 modulo 16 is 13. And sure enough, (5 * 13) % 16 is 1.

This now means that we have defined division modulo m as well! This kind of division has no remainder because the fundamental question division seeks to answer is “how many times would I have to add the divisor to zero in order to get the dividend?”; when x and m are coprime, that question always has an answer.

Next time on FAIC: a practical application of this algorithm. No, not public key crypto!