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!

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.

Pingback: Dew Drop – November 13, 2013 (#1666) | Morning Dew

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!

Aw – I was wrong with my first guess that WOLOG meant “Without Looking On Google”

Pingback: Teddy Textile | Gameschie

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

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

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