Tag Archives: factor

The Beauty of Euler’s phi function

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.