# Math from scratch, part thirteen: multiplicative inverses

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!

## 14 thoughts on “Math from scratch, part thirteen: multiplicative inverses”

1. How long is the cycle?

When I read this, I didn’t realise it was a rhetorical question and started trying to work out a general answer. After a couple of minutes I gave up. Turns out it was rhetorical.

I got as far as, “It depends. Ah, this must have soemthing to do with the greatest common divisor stuff from last post.” Which is correct, I guess, as far as it goes.

• Well you’ll note that I did not prove the assertion that if x and m are coprime then the sequence (0 * x) % m, (1 * x) % m, (2 * x) % m … does not get back to zero until (m * x) % m and does not repeat any remainders either. I merely stated it. You started trying to find the general pattern; can you produce a proof of my assertion?

• Fun though that would be, I’m actually going out drinking right now.

So, uh, let’s see how that works out.

🙂

• for the first part:
(p*x)%m = 0
p*x = q*m
x = q*m/p
as x and m are coprime m cannot be a factor of x, so either q=x=0, but from definition x>0, or p is some multiple of m, so first time back to 0 would be p = 1*m

• Correct. And now proving the more general result is a more general version of this argument:

To prove: if x and m are positive coprime integers, x, c and d are all integers >= 0 and < m, and (c * x) % m == (d * x) % m, then c == d. WOLOG assume that c >= d.

Let (c * x) % m == (d * x) % m == r. By the definition of %, there exists q1 such that c * x == q1 * m + r, and q2 such that d * x = q2 * m + r.

Subtract the second equation from the first equation: c * x – d * x == q1 * m + r – (q2 * m + r)

Simplify and factor. x * (c – d) == m * (q1 – q2)

The left hand side is evenly divisible by m. No prime factor of m divides x because x and m are coprime. Therefore m must divide (c-d). c is the greater of c and d, and both are smaller than m, so (c – d) is either zero, or a positive number smaller than m. But clearly m does not divide any positive number smaller than itself! The only possible solution is that (c-d) is zero, and therefore c == d.

Therefore, if two multipliers less than m give the same remainder, they must be the same. Therefore, if two multipliers less than m are different then they give different remainders. And therefore the sequence of remainders has m elements before it repeats.

2. Just out of curiosity: When modulus <= Integer.Zero in MultiplicativeInverse, why do you throw an InvalidOperationExecption instead of an ArgumentException?

• Hmm, you’re right, I should be throwing ArgumentException here. I’ll fix it. Thanks!

3. Pingback: Teddy Textile | Gameschie

4. “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"

Shouldn't it be 0 < y < m? because if y = 0 then x*y = 1 cannot be…