The Modern Geek by Mikhail Y. Popov - why math majors should learn programming

November 8^th 2009 : permalink : 15 notes : Comments

why math majors should learn programming

I was working on some Modern Algebra homework and came across a problem that required a lot of calculations that I just didn’t want to do by hand. So I did what anyone with programming knowledge would do: create a program that would do it for me.

The problem was this:

List the order of each element of the group U₂₀.

The order of an element of the group is defined as the least number of times that element must be multiplied by itself to get back to the identity element.

With groups, you only have operation * and that could be

a simple multiplication (a * b = ab)
a simple addition (a * b = a + b)
or something a little more complex (a * b = a + b - ab)

The identity element is the element e such that a * e = a = e * a.

So if you’re dealing with a simple multiplication, the identity element is 1. But if you’re dealing with a simple addition, your identity element is 0.

Now, what exactly is U₂₀? It is the set of units of Z₂₀.

An element a is a unit if there exists an element u such that au = 1. That is: a is invertible.

Wikipedia: “In computing, the modulo operation % finds the remainder of division of one number by another.” Here are some examples:

5 % 3 = 2
6 % 3 = 3
7 % 5 = 2

Z₂₀ is the set of integers mod 20. You take every single integer and divide it by 20 and if the remainders of two numbers are equal, the two numbers are congruent to each other. What Z₂₀ then becomes is a set of 20 unique elements: the integers from 0 to 19 because then the numbers repeat: 20 % 20 = 0, 21 % 20 = 1.

U₂₀ is easily obtained, actually, by the use of a corollary and a theorem. It is the set of all elements in Z₂₀ that are relatively prime to 20. Relatively prime means their greatest common factor is 1. 20 and 1, 3, and 7 are relatively prime, for example, while 20 and 2, 4, 5 are not since their g.c.f.s are not 1.

The complete set U₂₀ is 1, 3, 7, 9, 11, 13, 17, 19.

When working with a group of units, the operation * is always just multiplication (that is a theorem, by the way).

The problem was this:

List the order of each element of the group U₂₀.

So I need to find the smallest power of each of those eight elements such that when raised to that power and then divided by 20, I get back the integer 1 (the identity element).

This means you start with the power of 1 and if that doesn’t work, you go on to 2, and if that doesn’t work, you keep going until it does. There will come a point when you’re doing 134 % 20 and then you’re just like “Okay, this is bullshit.”

You have more patience than me because I lasted until I found the order 3, which is 4.

Here’s the reasoning: 3¹ = 3, 3² = 9, 3³ = 27 = 7 (remember the modulo thing?), and 3⁴ = 81 = 1. And we’re done with 3. Time for 7. I say: NO. Going through the same procedure each time is the work of a machine, not man. If only there was a way…

Oh, I know! Conveniently, I have Microsoft Visual Studio 2008 installed on my laptop. This is something almost every college student who’s into programming can do for free if they just go to Microsoft’s DreamSpark website. With that fired up, I created a new project: a Visual C# Console Application. I don’t need anything fancy here, just something that will display to me some letters and numbers.

So here’s the code:

int[] units = { 3, 7, 9, 11, 13, 17, 19 };
foreach (int u in units) {
int k = 1;
while ((Math.Pow(u, k)) % 20 != 1) { k++; }
Console.WriteLine(“The order of {0} is {1}. \n”, u, k);
}
Console.Read();

And here’s my step-by-step explanation of the code:

int[] units = { 3, 7, 9, 11, 13, 17, 19 };

Sets up an array of integers that I plan to work with.

foreach (int u in units) {

Begins a loop of statements that will be executed for each one of the elements in the array.

int k = 1;
while ((Math.Pow(u, k)) % 20 != 1) { k++; }

Creates a power and starts it off at 1 and then takes the current integer and raised it to the power and then mods it by 20 and if the result is not 1, then we just increment the power to the next value and test it until we do get 1.

Console.WriteLine(“The order of {0} is {1}. \n”, u, k);

At which point we just spit out our result to the user and then move on to the next integer in the array.

I really want to see what this process would look like in F#. I tried to do it but my F# is f’n terrible and I completely forgot everything I learned a year ago.

There are a lot of higher-math concepts embedded into this post that most people aren’t familiar with me and I hope I made them clear enough to follow along with. Obviously I’ve been dealing with this stuff a while and may take my knowledge for granted, so if there’s something you didn’t really understand please leave a comment below and I’ll respond with a clarification.