Thursday, July 14, 2011

Focus on modular arithmetic

One of the coolest mathematical areas to me is modular arithmetic and it shows up a LOT in my research, as it is a simplification tool, and a lot of my ideas simplify previously difficult and abstract areas of mathematics. It is critical in that simplification.

Most explanations of modular arithmetic that I've seen focus on what they call clock arithmetic, which is where with the clock things just cycle around. So you can't have 100 o'clock.

100 = 4 mod 12

So you have 4 o'clock, as that's the information you need, so succinctly modular arithmetic is about throwing away information you do not need. And with it you can do some really cool things.

Simple rule: with "mod" what is to the right of the equal sign is less than what is to the right of "mod" which is called the modulus. What is on the left of the equal sign may be greater.

When you consider something with "mod" you are said to be "modulo" a particular value, like with clocks you are modulo 12, or modulo 24, if you're not using am and pm.

Most mathematical texts don't use the regular equals sign with "mod" but instead use "≡" which is just adding one more line and if that doesn't show on your browser, it's just adding one more line beneath the normal equals. I did that for a while but soon got tired of it and just use the normal equals without I think losing anything.

As it is a fundamental branch of mathematics you can do an unlimited number of things with "mod" but usually its focus is with Diophantine equations, which are just situations where the answers are all integers, like -1, 0, 1, 2 or 3. So things like e or pi do not show up. And fractions like 1/2 or 1/3 do not usually show up, though they can be useful in a particular way.

Here's an example of something clever you can do with "mod", as, if you're just bored, you might wonder, if you square an integer and add 2, can it be divisible by 5? With modular arithmetic that is:

Does x2 + 2 = 0 mod 5 exist?

You can do a lot of typical algebra with modular arithmetic so that is the same as:

x2 = -2 mod 5, and you can add 5, to get rid of the negative, because what remains is less than 5, so you get: x2 = 3 mod 5

Important nomenclature issue: With 3 mod 5, 3 is called the residue, as it's what's left over, and often 0 is not considered a residue, but sometimes it may be, depending on the author. In my research 0 is not a residue. So, in my writing, the residue is what is to the left of "mod" as long as it is not zero.

Now we can look at all the positive residues modulo 5: 1, 2, 3, 4

And we can square them all: 1, 4, 9, 16

So we have 1 mod 5, 4 mod 5, 4 mod 5, and 1 mod 5

And you can see that only 1 and 4 are the residues when you square residues modulo 5, and they are called quadratic residues.

And our question is answered as 3 is not in that list! So no, it's not possible to add 2 to a square and have an integer divisible by 5.

Or stated another way, we've proven that the Diophantine equation x2 + 2 = 0 mod 5 has no solutions.

By focusing only on the necessary information and throwing everything else away, modular arithmetic allows you to answer questions that otherwise might seem impossible to answer, as you can answer questions over infinity.

You might think that the quadratic residue would always look like a square, but go up just a bit to modulo 7, and notice that 32 = 2 mod 7. So, no, the quadratic residue is not necessarily what is sometimes called a perfect square, which is redundant as you can just call it a square.

Now let's ask the math another question, if you multiply a number by 2 can it equal 3 modulo 5?

That is, does 2x = 3 mod 5 exist?

The answer is, yes. That's because of something called the modular inverse, which is a cool thing that lets you move that 2 from the left hand side to the right hand side:

x = (2-1)3 mod 5

It may seem complicated but it's just a number that you multiply times 2 to get 1 mod 5, and that number is: 3.

3(2) = 1 mod 5, so 3 is the modular inverse of 2 modulo 5.

So now we have: x = (2-1)3 mod 5 = (3)3 mod 5 = 4 mod 5.

The modular inverse will always exist as long as it is not a factor or does not contain factors of the modulus. So we could not do the same thing with 2x = 3 mod 10, which does not exist.

Here also is where you can use fractions instead, as you could have said:

x = 3/2 mod 5 = 3(3) mod 5 = 4

However, very important, with modular arithmetic something that looks like a fraction is never really a fraction, but is instead an actual whole number where you may use the form of a fraction simply as an intermediate step.

Sometimes you need to move from "mod" to what is called an explicit equation, and that's easy!

For example x = 4 mod 5 is equivalent to x = 4 + 5k, where k is some non-zero integer, where usually you have no idea what its actual value is. That is the information that is being thrown away, so there are an infinity of k's usually that will work. And that goes again to the power of "mod" as it always to some extent involves infinity.

And that is just a quick overview of some of the basics with modular arithmetic, where you can learn a lot more as it is a huge subject from many sources including the Wikipedia article on modular arithmetic.

James Harris

No comments: