So, for those of you who follow the blog, you may realize that I am actually at the low end of the totem pole in terms of Acadamia, but I am a research assistant, well, all year round. Woo hoo, I have a job that is cushy, irrelevant and pays well better than minimum wage. And I have actually been asked to use facebook while on the job.
Anyways, the other day a fellow research student who is working on projects unrelated to me, let's call him Prince Caspian, had a weird problem invovling the calculation division of large factorials MOD n.
For those of you not in mathematics, factorials are explained
here. Long and short of it is they can become very big numbers quickly. (10! is 3,628,800). Of course you also need to know what mod is, so look
here. It's a remainder operator, so 7 mod 3 is 1. 18 mod 2 is 0. 17 mod 5 is 2.
Anyways, he had a big number / another big number mod some other big number.
Needless to say this is hard to program since as I said 10! is in the millions. It's easy to get big. Now the nice thing about the mod operator is that for addition and multiplication are operation preserving.
Thus (a * b) mod n = a mod n * b mod n... and (a + b) mod n = a mod n + b mod n. Hurray, abstract algebra! Everyone rejoice.
Why am I telling you this? Because if I have a big number * another big number mod some third big number, then I can take the "a big number" mod it by some third big number and get a smaller number and then multiply it by the smaller number produced by taking "another big number" mod "some third big number" and I get an equivalent result.
Huh?OK, take (5 * 7) mod 3. 5 * 7 is 35... 3 * 11 = 33, so 35 mod 3 = (33 + 2) mod 3 = 2 mod 3. 5 mod 3 is clearly 2. (1*3 + 2 = 5) and 7 mod 3 is 1 (2*3 + 1= 7). This is a very useful property because if we have bigger numbers, we can mod them first and get smaller numbers, which our computers can then handle. Thus if I want to calculate n! *(2n)! mod n, I only need to calculate n! mod n and (2n)! mod n rather than the whole huge number.
OK, I sorta kinda get your fun lunacy... Wooo hoo math is fun, but you were talking division, what then?
Well, mod n has a neat property in that if n is prime or that if for any x mod n the greatest common divisor of x and n is 1, then x mod n will have an inverse.
You lost meWell, yes... This is abstract algebra. Everyone hates it. But think of division as the reverse of multiplication 1/7 * x is the reverse of multiplying x by 7. In modular multiplication, if the gcd of x and n are 1, then there exists some number b between 1 and n such that b * x = 1.
ok, I don't understand but so how is this useful?
Well if we are calculating "a big number" / "some other big number" mod n, if we could convert it to multiplication we could write it as "a big number" mod n * "some other big number" mod n... both of which would be nicer smaller numbers to work with.
OK, but how do we do that?Well if the GCD of "some other big number" and n is 1 then some other big number has an inverse in the ring of integers n. so 1/"some other big number" mod n can be written as "some inverse of another big number mod n."
Huh?Let's try and do this with small numbers. Say I have 2 / 3 mod 5... 3*7 = 21 mod 5 is 1, therefore 1/3 = 7 mod 5. thus 2/3 mod 5 = 2* 7 mod 5 = 2 mod 5 * 2 mod 5 = 4.
Ok, I have no idea what you did there, but I'm assuming you are actually sane today so that the above works, what is the point of this story anyways?Well, the point is that my method allows for the calculation of the big number / another big number mod n for really big certain numbers. And my other point is that I came up with this last week, and worked on it with Prince Caspian in my spare time, even though I am an edumakation researcher. The neat thing is that the prof he's working with on this told him TODAY to use the method that I a lowly undergraduate came up with.
So you wrote this incredibly long winded post which defies comprehension merely to gloat about how you came up with the same thing a prof did for a mathematics problem?Yes... and was told by Prince Caspian "I think we know where you're going."
Smartypants...His Grace.