Abstract Algebra presented in a non-intimidating way (esp. for developers) part 2

Hi!

If you haven't read the last one, I encourage you to do so, since I'll be using a lot of the terminology from the last post in this one, and I will be building on those topics.

This post is largely background info for the next post, which will be on cryptography, but, for you to understand the next post, it is essential that you understand this one quite thoroughly.

Lets begin with some history. Pure mathematicians when group theory was invented didn't really care what the physicists thought of them and how well they fared at parties, so, they developed all this theory about groups and none of them really cared about how it would apply to "real life".

Then of course, there were these pure mathematician misfits, who were also physicists, and they realized that group theory could actually be pretty useful, and there was this stream of physicists and chemists trying to get in on the abstract algebra action.

Up until then, most of the groups that were being studied were infinite (like $Z$ on addition), or something very specific that the physicists and chemists did not care about, and then mathematicians
Before we get into the group theory today, I want to introduce you to something I call "clock arithmetic".

Clock arithmetic is just like regular arithmetic, but, its carried out on a clock. I'll explain that with an example.

Let's try to find out what 12+6 would be, on a clock with the twelve numbers on it (not the weird Italian ones with 24 numbers on them, they don't deserve to be called clocks). Okay, so, thinking about this, we can see that this would not be 18, because 18 isn't on the twelve hour clock, and, what happens is, if we start at 12 and then rotate an additional 6 hours, we end up on the 6 mark.

Let's do another example. Let's try to find 6+9. Again, this is a similar case, where we set the hand to 6, it rotates around to 12 after 6 hours, and then, we still have 3 hours left to rotate a total of 9 hours, so, we end up at 3. 


Okay, that's not too bad.

As exercises, try finding out:

• 1+19 = ?
• 2+26 = ?

If we're doing $1+19$ on a twelve hour clock, we usually write it as:

$1+19 \equiv 8 (\mod{12})$

I can hear you saying, "What? Why does that equal sign have another line? This is heresy!"

That extra line is telling us that $1+19$ isn't necessarily equal to $8$, but, it is under this funny clock arithmetic with this twelve hour clock we've developed.

If you did those two exercises, you might have noticed something. The observation should have been that if you add 1 and 19 using the "regular" arithmetic, and then take the remainder by 12, you still get the same answer! 

Now, with a little bit of thought and some intuition, you can see why that's true (I encourage you to try this; hint, try starting at an arbitrary hour, like 1, and then seeing what happens in reference to this point). 

I won't bore you with the formal proof (it doesn't use any clever arguments), but, I would really like it if you would try to get some intuition about why the above is true.

Okay, now, not all clocks are 12 hours long, right? How about some clocks that are, eh, three hours long? It's still the same idea!

Say, we're doing $12+20$. We first find out its $32$, and then take $\mod 3$ (remainder by 3), to get $2$. 

Read the last sentence again. See how I used $mod$ to mean remainder? Okay, good. 

Because clock arithmetic are pretty much remainders, and mathematicians like using large words, this clock arithmetic is called modular arithmetic. 

You might have also noticed that we can take the remainder of the two numbers were adding up separately, and then add up those two remainders to get our answer. Let's try proving that in general (note: what matters isn't really the proof, but, how the reasoning goes in the proof, follow it closely). Stated "mathematically", this comes out to be:

If $a \equiv b (\mod {n})$ and $c \equiv d(\mod{n})$, then, $a + c \equiv b + d (\mod{n})$

Let's try to think of this in terms of remainders. Since $a$ has a remainder $b$ when divided by $n$, we get that $a$ can be written as $kn + b$, for an some integer $k$.

Then,

$a-b = (kn+b)-b = kn$

Therefore (since $a-b$ has to be divisible by $n$),

$a-b \equiv 0 (\mod{n})$

Similarly, we can argue that

$c-d \equiv 0 (\mod{n})$

Now, think about it this way, if we add two numbers that are divisible by a certain number $n$, you will always get a number that is divisible by $n$. A quick proof:

$p = k_1n, q=k_2n$
$p+q = n(k_1+k_2)$

So, we can add the two congruences we got, so that we have:

$(a-b) + (c-d) \equiv (a+c)-(b+d) \equiv 0 (\mod n)$

Again, we have to use a bit of thinking here. If you have a number $m$, and $m-k$ is divisible by $n$, then, that means that $m$ has a remainder $k$ when divided by $n$ (from the definition of a remainder).

So, we can use that to say:

$a+c \equiv b+d \mod(n)$

Nice!

You probably did not understand ALL of the proof, and if that was the case, please read it again. The approach that we're using, using algebra and divisibility at the same time is very important, and will probably show up again.

Alright, so, how has any of this got anything to do with abstract algebra and groups and stuff?

Well, let me introduce you to this concept of a cyclic group.

A cyclic group is a group in which all of the elements of the group can be generated by one element of the group on which the operation of the group is applied over and over.

What the heck does that mean?

This is best illustrated with an example.

Let's say we have a group, with the operation $+$. You know, like normal addition.
We start out with the element $1$, and add $1$ do it, and get $2$.

Then, we add $1$ to $2$ again. To get $3$. And so, so forth, until we've generated all the integers (we can also apply the inverse operation, which would be to subtract), so, we can say the the set of integers ($Z$) is cyclic under the operation of addition.

Then, there are cyclic subgroups.
Cyclic subgroups are groups whose elements are a subset of those of a cyclic group. Cyclic subgroups are (usually) finite.

Here's where you need to pay attention.

A cyclic group can be something like:

${1,2,3,4,5,6,7,8,9,10,11,12}$ on the addition operation.

Hey ... that's like a clock! So, cyclic groups can model modular arithmetic!


So, all the stuff we established in the last post is automatically applicable to this one :)
We can now prove some stuff about modular arithmetic using groups!

We can even prove that multiplication (i.e. repetitive addition) forms a cyclic group ($G$) under modular arithmetic with a $\mod p$ where $p$ is prime. This is so because:

• Closure: any two elements that we take in this set and multiply them together cannot give a result which $0$ and therefore not in the set.
• Associative: Its multiplication; not much work here.
• We have an identity, and its 1
• All of them have an inverse so that they have a remainder of 1 $\mod {p}$

This allows us to say:

$m^{p-1} \equiv 1 (\mod {p})$, for all $m \epsilon G$

Why? Because if you think about, the multiplication sort of "wraps around" the set, because all of the results of the multiplication are a part of the set of the group $G$ (if you are confused about this, drop a comment below and I'll definitely help, this confused me for a really long time).

So, let me pose a problem:

Find the $7^{37} \mod {13}$. Don't reach for that calculator. And, no, you can't use Python.

That looks really hard!

But, we can simplify that a bit. From what we know from above, we can say ($13$ is a prime):

$7^{12} \equiv 1 (\mod {13})$


Okay, that helps us, because we can write $7^37$ as:

$7^{37} \equiv (7^{36})\cdot(7) \equiv (7^{12})^3\cdot(7) \equiv 1\cdot7 \equiv 7 \mod{13}$

Nice!

On top of that, all cyclic groups are abelian/commutative (try proving this; its a good exercise), which opens up an entire new set of possibilites.

But, why does any of this matter? But does this "modular arithmetic" idea matter aside from solving problems like the one above, which you would have probably plugged into a computer?

Let me tell you, cyclic groups are not-so-abstract-algebra. They have a TON of applications.

Well, if you've ever written a website (or, even used one), or logged into SSH, or logged into a computer, it definitely does matter.

There's this "little subject" called cryptography, which deals with storing information in different forms, and it uses modular arithmetic intensively.

And, if you are a physics type person, Lie groups and such are quite similar to cyclic/symmetric groups.

If you liked the $7^37$ problem, and would like to continue in this direction, I highly recommend you check out this free set of problems (not by me). They are much more advanced than these, but, if you get some background on number theory, they should be fun.

I promise the next one will be much cooler in terms of CS related stuff, but, I had to provide some background on cyclic groups, otherwise the next one wouldn't have made any sense.

Also, I've started a project called NimbleNotes here, and I really am trying to get it off the ground, so pledges and tweets are highly appreciated :) This blog entry was written with NimbleNotes, with a MathJax plugin I wrote.