## Primitive roots of unity

So we have now seen that there are always $n$ different complex $n$th roots of unity, that is, complex numbers whose $n$th power is equal to $1$, equally spaced around the circumference of the unit circle.

Consider the first $n$th root around the circle from the positive $x$-axis (i.e. the darkest blue dot in the picture above). Let’s call this number $\omega_n$. For example, in a previous post we saw that $\omega_6 = 1/2 + i \sqrt{3}/2$. Then the other dots around the circle—the other $n$th roots of 1—are obtained by taking powers of $\omega_n$. The next dot is $\omega_n^2$, the next is $\omega_n^3$, … and finally $\omega_n^n = 1$.

In my original post that kicked off this series, I drew circles with dots on only some of the spokes, like this:

I explained one way to think about this: in the circle with $n$ spokes, there is a dot on spoke $k$ (where the spoke on the positive $x$-axis is numbered 0) if and only if $k$ and $n$ are relatively prime, that is, $k$ and $n$ have no common divisors other than $1$ ($\gcd(k,n) = 1$). Now that we know how to think of the dots as complex numbers, we can also ask: what is special about these dots as complex numbers? Is there a way to rephrase this definition in terms of $n$th roots of 1?

Of course, the answer is yes! These dots are called the primitive $n$th roots of unity. In the above picture with $n=12$, using our new notation, the highlighted dots are $\omega_{12}$, $\omega_{12}^5$, $\omega_{12}^7$, and $\omega_{12}^{11}$. In general, we will have $\omega_n^k$ where $\gcd(k,n) = 1$. But there is a different, equivalent way to characterize them: an $n$th root of unity is primitive if it is not also an $m$th root of unity for some smaller $m$. For example, consider $\omega_{12}^2$, corresponding to the second spoke on the circle above. This is a 12th root of 1, but it is not a primitive 12th root of 1, because it is also a $6$th root of 1. (In fact, it is our old friend $\omega_6 = 1/2 + i \sqrt{3}/2$.) In other words, if we start with $\omega_{12}^2$ and take successive powers of it, we find a power (the sixth power) that yields 1 before we get to the 12th power. Something similar is true for $\omega_{12}^3$: it is a 12th root of 1, sure, but raising it to the 12th power is overkill—just raising it to the 4th power will get us to 1. $\omega_{12}^5$, on the other hand, is a primitive 12th root—we actually have to multiply it by itself 12 times before reaching $1$.

I will leave to you the fun of figuring out why these definitions are the same!

## Complex multiplication: proof

In my previous post, I claimed that when multiplying two complex numbers, their lengths multiply and their angles add, like this:

In particular, this means that there are always $n$ different complex numbers whose $n$th power is equal to $1$: they are equally spaced around the circumference of the unit circle. For example, here are the twelve $12$th roots of $1$:

Did you figure out why? Here’s one way to understand it. If a complex number $z$ is at distance $r$ away from the origin, and makes an angle $\theta$ with the positive $x$-axis, then $z^n$ will be at distance $r^n$ from the origin (since lengths multiply), and will make an angle $n\theta$ with the positive $x$-axis (since angles add). First of all, for all the complex numbers on the unit circle, $r = r^n = 1$. So if we start with a complex number on the unit circle, all its powers will always stay on the unit circle. Now, if we have $n$ equally spaced points around the unit circle, the angles they make with the positive $x$-axis are $1/n$ of a full turn, $2/n$ of a full turn, $3/n$, and so on. So if we take their $n$th powers, the results have angles of $n \cdot (1/n) = 1$ full turn, $n \cdot (2/n) = 2$ full turns, and so on… but any whole number of turns will land exactly back on the positive $x$-axis.

So, let’s prove that this is how complex multiplication works! Let’s write $\langle r, \theta \rangle$ to represent the complex number at radius $r$ and angle $\theta$.

From the picture, we can see that $\langle r, \theta \rangle$ is at one corner of a right triangle with hypotenuse of length $r$ and one angle $\theta$. Remembering some basic trigonometry, we can say that the horizontal leg of the triangle (the blue edge) has length $r \cos \theta$, and the vertical leg (the red edge) has length $r \sin \theta$. Therefore,

$\langle r, \theta \rangle = r \cos \theta + i r \sin \theta = r (\cos \theta + i \sin \theta)$

So now let’s see what happens when we multiply.

$\begin{array}{rcl} \langle r_1, \theta_1 \rangle \cdot \langle r_2, \theta_2 \rangle &=& r_1 (\cos \theta_1 + i \sin \theta_1) \cdot r_2 (\cos \theta_2 + i \sin \theta_2) \\ &=& r_1 r_2 (\cos \theta_1 \cos \theta_2 - \sin \theta_1 \sin \theta_2 + i \sin \theta_1 \cos \theta_2 + i \cos \theta_1 \sin \theta_2) \\ &=& r_1 r_2 (\cos (\theta_1 + \theta_2) + i \sin (\theta_1 + \theta_2)) \\ &=& \langle r_1 r_2 , \theta_1 + \theta_2 \rangle \end{array}$

Mostly this is just substituting and then distributing out the multiplication; but in the second-to-last step we have to remember some trig identities, specifically the angle sum identities. So I guess this proof seems a bit magical if you don’t already believe those; but here’s a nice proof of the angle sum identities.

## Complex multiplication and roots of unity

If played around with the question from my previous post, you probably found something like the following:

$\begin{array}{lcl}(1/2 + i \sqrt{3}/2)^2 &=& 1/4 + i \sqrt{3}/2 - 3/4 \\[0.5em] &=& -1/2 + i \sqrt{3}/2 \\[1em] (1/2 + i \sqrt{3}/2)^3 &=& (-1/2 + i \sqrt{3}/2)(1/2 + i \sqrt{3}/2) \\[0.5em] &=& -1/4 - i \sqrt{3}/4 + i \sqrt{3}/4 - 3/4 \\[0.5em] &=& -1 \\[1em] (1/2 + i \sqrt{3}/2)^4 &=& (-1)(1/2 + i \sqrt{3}/2) \\[0.5em] &=& -1/2 - i \sqrt{3}/2 \\[1em] (1/2 + i \sqrt{3}/2)^5 &=& (-1/2 - i \sqrt{3}/2)(1/2 + i \sqrt{3}/2) \\[0.5em] &=& -1/4 - i \sqrt{3}/2 + 3/4 \\[0.5em] &=& 1/2 - i \sqrt{3}/2 \\[1em] (1/2 + i \sqrt{3}/2)^6 &=& (1/2 - i \sqrt{3}/2)(1/2 + i \sqrt{3}/2) \\[0.5em] &=& 1/4 + 3/4 \\[0.5em] &=& 1\end{array}$

That is, as the powers of $1/2 + i \sqrt{3}/2$ we get $-1$, $1$, and $\pm 1/2 \pm i \sqrt{3}/2$ with all possible sign combinations. Of course, since $(1/2 + i \sqrt{3}/2)^6 = 1$, if we continue taking higher powers after that we will just get the same values repeated.

Remember that $1/2 + i \sqrt{3}/2$ is the complex number corresponding to the end of the first spoke on a $6$-circle. If we plot its powers, we find that they are exactly the other spokes of the $6$-circle! Every time we multiply by $1/2 + i \sqrt{3}/2$, we seem to rotate around the circle $1/6$ of the way. What’s going on?

As it turns out, there’s nothing magical about these particular values—this is just how complex multiplication works! Plot any complex number and connect it to the origin with a straight line. This line has a certain length and makes a certain angle with the positive $x$-axis (this length and angle are respectively called the magnitude and argument of the complex number, but I won’t use these terms in the rest of the post).

When we multiply two complex numbers, these lengths and angles combine in a particularly nice way: the lengths multiply, and the angles add.

That is, the length of the purple line above is the product of the lengths of the blue and red lines, and the angle that the purple line makes with the positive $x$-axis is the sum of the blue and red angles. We’ll prove this in another blog post, but for now, let’s assume it’s true and see what the implications are for our spokes.

When a complex number is located on the unit circle, then its distance from the origin is 1, so multiplying it by another complex number does not change the length at all (since the lengths multiply, and multiplying by 1 is the identity). All it does is add the angle, that is, it rotates.

In particular, consider $1/2 + i \sqrt{3}/2$, which is located on the unit circle at an angle of $\tau / 6$, that is, one-sixth of the way around the circle ($\tau = 2\pi$ is the fundamental circle constant, the ratio of a circle’s circumference to its radius). Squaring it thus produces another complex number at a distance of 1 from the origin, and an angle of $\tau/6 + \tau/6 = \tau/3$, one-third (two-sixths) of the way around the circle. Every time we multiply by another factor of $1/2 + i \sqrt{3}/2$, we rotate another sixth of the way around. This is why the powers of $1/2 + i \sqrt{3}/2$ are evenly spaced around the unit circle.

Now, notice that when we take the sixth power of $1/2 + i \sqrt{3}/2$, we rotate all the way around to the $x$-axis, and we get $1 + 0i = 1$. So $1/2 + i \sqrt{3}/2$ is a sixth root of $1$. In fact, all the powers of $1/2 + i \sqrt{3}/2$ are sixth roots of $1$:

You should take a minute to make sure you understand why this is true. For example, what happens if you start with the complex number one-third of the way around the circle (that is, $(1/2 + i \sqrt{3}/2)^2$), and multiply it by itself six times? After squaring it, we are two-thirds of the way around… after cubing it, we are three-thirds around, that is, at $1$… and so on.

You are surely familiar with the fact that $1$ has two square roots, namely, $1$ and $-1$. You might even be familiar with the fact that $1$ has four fourth roots, namely, $1^4 = i^4 = (-1)^4 = (-i)^4$. But in general, now that we understand how complex multiplication works via rotation, we can see that $1$ always has exactly $n$ different $n$th roots, which are evenly spaced around the unit circle, at the ends of the dotted spokes in our pictures!

Posted in geometry, pictures | Tagged , , , , , | 2 Comments

## Complexifying our dots

It’s time to up our game a bit. Previously we have considered some cool pictures with dots and bespoked circles, looking for patterns, without really considering what sort of mathematical objects these circles might represent. In fact, they turn out to have a close connection to complex numbers.

Recall that a complex numbers are built from real numbers together with the “imaginary unit” $i$ (which is just as real as real numbers!) which has the property that $i^2 = -1$. A complex number is of the form $a + bi$ for real numbers $a$ and $b$, and we can think of complex numbers as living in a two-dimensional plane, where we usually think of real numbers as the horizontal axis, and imaginary numbers as the vertical axis.

So the dots on the circles we have been considering can be thought of as complex numbers:

If we suppose the circles to be centered at the origin and have radius 1 (which turns out to work nicely), then the above blue dots happen to correspond to the complex numbers $1/2 \pm i \sqrt{3}/2$ (as you can confirm with either some basic geometry—those dotted triangles are equilateral triangles with sides of length 1—or by remembering the sine and cosine of some special angles).

Next time, we’ll recall how multiplication of complex numbers works, and discover what is special about the dots considered as complex numbers. For now, I’ll leave you with something to play with, if you haven’t seen this before: what happens when you square $1/2 + i \sqrt{3}/2$? When you cube it? Take the fourth power? And so on?

Posted in geometry, pictures | Tagged , | 3 Comments

## Totient sums

I took a bit of a break to travel to Japan for a conference, but I’m back now to continue the series I started with Post Without Words #10, a follow-up post, and Post Without Words #11. Recall that we have dots on circles with spokes, like this:

Circle $n$ has a dot on spoke $k$ if and only if $\gcd(k,n) = 1$ (the spokes are numbered from zero).

In PWW #11, I showed some pictures like this:

We have here the circles with $1$, $2$, $3$, $4$, $6$, and $12$ spokes—one for each divisor of $12$. The colors highlight the fact that if we take all these circles and superimpose them on each other, we get exactly one dot at the end of each spoke.

Does this always happen? In fact, it does. First, as I explained in a previous post, a spoke in a particular location has a dot the first time that spoke appears, but then never again. So we can never get overlapping dots. But how do we know that if we take the circles for all the divisors of some number, we end up with all possible dots? Well, given a circle with $n$ spokes, its spokes also show up in circles corresponding to divisors of $n$, and in no other circles. For example, the circle with $6$ spokes above includes every other spoke from the circle with $12$; the circle with $4$ spokes includes every third spoke, and so on. Any circle $m < n$ where $m$ is not a divisor of $n$ will have completely different spokes. So among all of the $n$ spokes, each one must have first appeared as a spoke of some divisor of $n$, where it would have a dot. So if we collect the circles for all divisors of $n$, we necessarily include one dot for each spoke.

The number of dots on circle $n$ can be notated by the Euler totient function $\varphi(n)$ (also known as the Euler phi function), which counts how many numbers less than $n$ are relatively prime to $n$. Using this notation, we can restate the above observation as

$\displaystyle \sum_{d|n} \varphi(d) = n,$

that is, if we add up the number of dots on circle $d$ for each $d$ which is a divisor of $n$, we get a total of exactly $n$ dots.

Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 1 Comment

## Factorization diagram cards are here!

It’s been a long process, but factorization diagram cards are finally available for purchase!

If you just want to purchase a set right this minute, then click the above link! If you want to learn more, keep reading.

## History

As explained in this original blog post from 2012 and this follow-up post, the basic idea behind factorization diagrams is to visualize the prime factorization of a positive integer $n$ by taking $n$ dots and recursively grouping them according to the prime factors. For example, $30 = 2 \times 3 \times 5$ can be visualized by making two groups of three groups of five dots, as seen in one of the cards above. You can find a lot more information about factorization diagrams here, including links to related things people have made, posters for sale, and so on.

Very early on I heard from teachers who had printed the diagrams, cut them out into cards, and used them successfully in their classrooms. After hearing that, I decided that there really ought to exist a high-quality deck of factorization diagram cards for purchase. It’s taken four years for that idea to come to fruition, but they are finally here!

## The deck

So, what’s in a deck, you ask? Each deck contains 54 large (3.5 inch) square cards. The front of each card has a factorization diagram, and the back has the corresponding number and factorization written out. Numbers with multiple distinct prime factors have multiple cards with different diagrams, one for each distinct permutation of the prime factors. (For example, $12 = 2 \times 2 \times 3 = 2 \times 3 \times 2 = 3 \times 2 \times 2$ has three different cards, as illustrated below.)

You can buy your very own deck through The Game Crafter for $13.99 (see below for an explanation of the price). The images used to make the cards are freely available here (in case you’d rather just print them yourself, or do something else with them), and the source code is on github. Everything is released under a Creative Commons Attribution 3.0 license, which basically means you can do whatever you want with the source code, images, design, etc., as long as you credit me as the source (preferably by linking to https://mathlesstraveled.com/factorization). If you end up using these cards in a classroom and come up with any fun activities/games/puzzles using the cards, please let me know! I would like to collect a big list of suggested activities for different ages and eventually be able to publish the list along with the cards. ## Pricing and print-on-demand As mentioned above, I have published the deck through The Game Crafter, who have done a great job. The process was easy and professional, and I am pleased with the final product—and I hope you will be too. You might think$13.99 is steep for a deck of cards, but (a) the print-on-demand model means there are no economies of scale to be had, and (b) these are definitely high-quality cards (3.5" square, high-quality card stock, with a linen texture and UV coating that reduces glare). I think a deck should last you a while, even if young kids are handling it.

Speaking of economies of scale though, if you are—or know—an educational/game publisher who would be interested in publishing this deck at a lower price point, please contact me! Until something like that happens though, I don’t have the resources—temporal or financial—to be able to coordinate a larger print run. The print-on-demand model means that I can get these cards out without a huge commitment.

Posted in arithmetic, counting, pattern, pictures, primes, teaching | Tagged , , | 2 Comments

## Post without words #11

Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 5 Comments