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!

Advertisements

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?

      • 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. Pingback: Dew Drop – November 13, 2013 (#1666) | Morning Dew

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

  4. Pingback: Teddy Textile | Gameschie

  5. “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…

  6. Pingback: How to generate different random time in the given interval for each row? | DL-UAT

  7. Pingback: A practical use of multiplicative inverses | Fabulous adventures in coding

  8. Pingback: How to generate “random-looking” keys « Jim's Random Notes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s