Tag Archives: number

Examples

The Beauty of Euler’s phi function

Leave a comment

The recent conversation I had about number theory has brought it back into my awareness. In particular, the concept of beauty in numbers. I’m definitely not any kind of graphical designer or fashion expert but I do appreciate what I think of as beautiful, and there are certain areas of mathematics that are just beautiful.

But who am I to say what is beautiful? What really is beautiful? Rather than trying to talk about these things in terms of the abstract concept of beauty, I wanted to try to nail down some of the things I like about it.

In our early years we learn about shapes. Sometime later we learn about things like “regular polygons”. These are polygons where all sides have the same length. We also learn about stars, but the stars we learn to draw most often is the 5 point star that we can draw without lifting the pencil.

A natural question becomes are there other stars we can draw without lifting a pen? A 4 point star? a six point star? a seven point star?

Before we go into the ? function, lets make sure we’re on the same ground. We need to talk about common divisors.

Suppose we have two numbers, lets call them m and n. A common factor of m and n is a number that divides into both of them. For example a common divisor of 4 and 6 is 2 since 4 = 2 * 2 and 6 = 2 * 3. Two numbers are called relatively prime if their only common factor is 1. Remember that 1 is a factor of every number.

Euler’s ? function (called the totient function) of a number n is defined as the count of numbers less than n that are relatively prime to n.

n12345678910111213
?(n)112242646410412

To understand what’s going on in that table above, lets look at a number like 10 and ask what are the numbers relatively prime to 10?

n123456789
Factor 101*102*51*102*52*52*51*102*51_9
Factor n1*11*21*32*21*52*31*72*41*10
GCF121252121

So from this example we see that the numbers relatively prime to 10 are 1, 3, 7, and 9, so ?(10) = 4.

A nice property of Euler’s phi function is that for any n > 3, if ?(n) is 3 or greater, then we can draw a star with that many (n) points without lifting the pencil.

To do this, we first need to talk about modular arithmetic. If we have two numbers, a and b and want to add them modulo some number, written
(a + b) mod n
We take the remainder of (a + b) when this number is divided by n.

For example, if we wanted to calculate (3 + 5) mod 7 we would first compute (3 + 5) to get 8 and then realize that 8 = 7 * 1 + 1. This gives a remainder of 1, so (3 + 5) mod 7 would be congruent to 1.

If we are considering drawing an n pointed star, we can start with a number that is not 1 and is relatively prime to n and continually add that number to itself. What will happen is that because this number is relatively prime to n, it will visit every other number before returning to the number 0.

What is more is that there may be more than one n pointed star that we can draw. The number of stars is (?(n) – 2) / 2. So for 10, it will be (4 – 2) / 2 = 1. This can be seen below.

I wanted to allow users to begin to see more of this beauty, so I wrote a script showcasing it.

Examples

Pascal’s Triangle

Leave a comment

I had a recent conversation with a friend who asked me “what makes number theory interesting?”. I loved the question, mainly because it gave me an opportunity to talk about math in a positive manner. More importantly though, it was an opportunity to talk about one of my favorite courses in mathematics (along with discrete mathematics and set theory). As much as the current day seems to focus on joining Number Theory with Cryptography, when I answered this question I wanted to make sure I didn’t go that route. Numbers are beautiful in their own right, and one of the things about Number Theory that was so interesting was simply the ability to look at all the different questions and patterns and properties of numbers discovered.

To answer this question, I started listing numbers to see if she noticed a pattern, but I did it with a “picture”.

.
..
…
….
…..
……

and I asked two questions

  • How many dots will go on the next line
    and
  • After each line how many dots have been drawn in total?

Lets answer these questions:

Dots# on this line# in total
.11
..23
…36
….410
…..515

There were a lot of directions I could have taken this conversation next, but I decided to stay in the realm of triangles and discuss Pascal’s triangle. This is a triangle that begins with a 1 on the first row and each number on the rows beneath is the sum of the two cells above it, assuming that cells not present have a value of zero.

So the first five rows of this triangle are

1
11
121
1331
14641

This is an interesting and beautiful triangle because of just the number of patterns you can see in it.

  • Obviously there are ones on the outside cells of the triangle.
  • One layer in, we get what are called the Natural or Counting numbers (1, 2, 3, 4, 5, …) .
  • One layer in, we can start to see the list of numbers that I was showing my friend (1, 3, 6, 10, 15, …).

There are several other properties of this triangle and I wanted to allow users to begin to see them, so I wrote a script highlighting some of these patterns.

Examples

The RSA Algorithm

2 Comments

I can remember back when I was in school, still deciding whether I wanted to study pure or applied mathematics. One of the common questions I would receive from those in applied mathematical realms would sound like “What’s the point of doing mathematics with no real world applications?”. Generally my response to these questions was about the intrinsic beauty of mathematics, no different from an artist painting not for some desire to be a millionaire, but because of an burning desire to paint. Whether their paintings would one day be on the walls of a Smithsonian museum or sit on their mother’s refrigerator is generally outside of the thought process of the artist. So too, would I argue about the thought process of a pure mathematician.

When I was an undergrad and learned about the RSA algorithm (named for Ron Rivest, Adi Shamir, and Leonard Adleman who discovered the algorithm) it helped me explain this concept a lot better. The algorithm is based on prime numbers and the problem of finding the divisors of a given number. Many mathematicians throughout the ages have written papers on the beauty of prime numbers (see Euclid, Eratosthenes, Fermat, Goldbach, etc). For a large period in time one of the beautiful things about prime numbers was that they were so interesting in themselves. There were questions about how to check if a number is prime, question of patterns in primes, famous conjectures like the Goldbach conjecture and the twin prime conjecture, quick ways of finding prime numbers or numbers that are almost always prime, etc. In short, this was an active area of research that much of the applied world was not using. This all changed in 1977 when Rivest, Shamir and Adleman published the RSA algorithm.

The algorithm is in the area called public key cryptography. These algorithms differ from many of the previous cryptography algorithms, namely symmetric key cryptography. Whereas symmetric key cryptography depends uses the same device (key) to encode as to decode, public key cryptography creates two keys – one for encoding that is generally shared with others, and another for decoding which is kept private. These two keys in generally relate to a mathematical problem that is very difficult to solve.

In my example script for the RSA Algorithm, I show two people who want to communicate, Alice and Bob. Bob wants people to be able to send him messages securely so he decides to use the RSA algorithm. To do this, he first needs to think of two prime numbers, p1 and p2.
From these, he computes the following:
n = p1 * p2

Next, he computes Euler’s function on this n which can be calculated as
(n) = (p1 – 1) * (p2 – 1)

Then Bob looks for a number e that is relatively prime to . This is what he will use as the encryption key.

One he has e, he can calculate d, which is the multiplicative inverse of e in (n).
This means that e * d = 1 (mod (n)).

The public key that will be used for encryption will be the pair (e, n). This is what he posts publicly via his web page for others to communicate with him securely. Bob also has a private key pair (d, n) that he will use to decrypt messages.

Alice sees Bob’s public key and would like to communicate with him. So she uses it to encode a message. The formula she uses to encrypt her message is c = me mod n, where c is the encrypted message. Once Alice encrypts her message, she sends it to Bob.

Bob receives this encoded message and uses the private key (d, n) to decode the message from Alice. The formula to decrypt is m = cd mod n.

For a more illustrative idea of how this algorithm works as well as examples, be sure to visit Script for the RSA Algorithm.

Examples

The PageRank Algorithm

1 Comment

I think one of the best recent examples of the importance of mathematics is the rise of the search engine Google. I remember the world of search engines before Google and it was dominated by names like AltaVista, Yahoo, WebCrawler, Excite, and the likes. The standard way these search engines ranked the order that pages would be listed on a search query was basically to count the number of times that query appeared on pages in their database. The pages with the most listings were considered the most important, the second most listings were second most important and so on and so forth.

This sounds like a feasible way of doing things but let me show you an example of how this can be tricked. Suppose I wrote my first web page and it looked like the following:

That’s a basic web page that may not garner much attention, and it wouldn’t rank highly in most search engines as no work appears more than once. Suppose that, this being a math web page, I wanted it to rank higher on the query “math”. Then I could just edit the source code of the page to be as follows:

This second page says not much more than the first, but the fact that the word math appears 9 additional times would increase the ranking of this page among math pages. This is a very simple example, but it shows how these search engine rankings did not have a useful metric for determining the important sites on the web.

Enter Google.

The way Google solved this problem of determining the importance of a web page is basically by counting the number of links into a web page – the theory being that the more important a web page is, the more people will be talking about it and thus linking to it. Also, the more important the people talking about (linking to) a web site, the more important that site is. This can be expressed mathematically by the following formula:

In the above formula, the variable d is called the damping factor, which helps to capture some of the random nature of the internet by saying that every site should have at least some minimal worth because of the idea that a random surfer could still get to these sites.

I have written a script to implement the algorithm here.

Other Blogs that have covered this topic
Blue Onion

Blog

How Could You Possibly Love/Hate Math?

4 Comments

Growing up, I never really liked math. I saw it as one of those necessary evils of school. People always told me that if I wanted to do well and get into college, I needed to do well in math. So I took the courses required of a high school student, but I remember feeling utter confusion from being in those classes. My key problem was my inquisitive nature. I really didn’t like being “told” that certain things were true in math (I felt this way in most classes). I hated just memorizing stuff, or memorizing it incorrectly, and getting poor grades because I couldn’t regurgitate information precise enough. If this stuff was in fact “true”, I wanted to understand why. It seemed like so much was told to us without any explanation, that its hard to expect anybody to just buy into it. But that’s what teachers expected. And I was sent to the principal’s office a number of times for what they called “disturbing class”, but I’d just call it asking questions.

At the same time, I was taking a debate class. This class was quite the opposite of my math classes, or really any other class I’d ever had. We were introduced to philosophers like Immanuel Kant, John Stuart Mill, Thomas Hobbes, John Rawls, etc. The list goes on and on. We discussed theories, and spoke of how these concepts could be used to support or reject various propositions. Although these philosophies were quite complex, what I loved was the inquiries we were allowed to make into understanding the various positions. Several classmates and I would sit and point out apparent paradoxes in the theories. We’d ask about them and sometimes find that others (more famous than us) had pointed out the same paradoxes and other things that seemed like paradoxes could be resolved with a deeper understanding of the philosophy.

Hate is a strong word, but I remember feeling that mathematicians were inferior to computer programmers because “all math could be programmed”. This was based on the number of formulas I had learned through high school and I remember having a similar feeling through my early years of college. But things changed when I took a course called Set Theory. Last year, I wrote a piece that somewhat describes this change:

They Do Exist!

Let me tell you a story about when I was a kid
See, I was confused and here's what I did.
I said "irrational number, what’s that supposed to mean?
Infinite decimal, no pattern? Nah, can't be what it seems."
So I dismissed them and called the teacher wrong.
Said they can't exist, so let’s move along.
The sad thing is that nobody seemed to mind.
Or maybe they thought showing me was a waste of time.

Then one teacher said "I can prove they exist to you.
Let me tell you about my friend, the square root of two."
I figured it'd be the same ol' same ol', so I said,
"Trying to show me infinity is like making gold from lead"
So he replies, "Suppose you're right, what would that imply?"
And immediately I thought of calling all my teachers lies.
"What if it can be written in lowest terms, say p over q.
Then if we square both sides we get a fraction for two."

He did a little math and showed that p must be even.
Then he asked, "if q is even, will you start believing?"
I stood, amazed by what he was about to do.
But I responded, "but we don't know anything about q"
He says, "but we do know that p squared is a factor of 4.
And that is equal to 2 q squared, like we said before."
Then he divided by two and suddenly we knew something about q.
He had just shown that q must be even too.

Knowing now that the fraction couldn't be in lowest terms
a rational expression for this number cannot be confirmed.
So I shook his hand and called him a good man.
Because for once I yould finally understand
a concept that I had denied all my life,
a concept that had caused me such strife.
And as I walked away from the teacher's midst,
Excited, I called him an alchemist and exhaled "THEY DO EXIST!"

Aside from its lack of poetic content, I think that many mathematicians can relate to this poem, particularly the ones who go into the field for its theoretic principles. For many of us, Set Theory is somewhat of a “back to the basics” course where we learn what math is really about. The focus is no longer on how well you can memorize a formula. Instead, its more of a philosophy course on mathematics – like an introduction to the theory of mathematics, hence the name Set Theory.

The poem above focuses on a particular frustration of mine, irrational numbers. Early on, we’re asked to believe that these numbers exist, but we’re not given any answers as to why they should exist. The same could be said for a number of similar concepts though – basically, whenever a new concept is introduced, there is a reasonable question of how do we know this is true. This is not just a matter of practicality, but a necessity of mathematics. I mean I could say “lets now consider the set of all numbers for which X + 1 = X + 2”, but if this is true for any X, then it means that 1 equals 2, which we know is not true. So the set I’d be referring to is the empty set. We can still talk about it, but that’s the set I’d be talking about.

So why is this concept of answering the why’s of mathematics ignored, sometimes until a student’s college years? This gives students a false impression of what math really is, which leads to people making statements like “I hate math”, not really knowing what math is about.