Practical Cyclotomy

Before we come to the heart of the matter in cyclotomy, we have to deal with some preliminaries. Especially, we want to show that it suffices to restrict ourselves to regular polygons with a prime number of vertices. Having done this, we try to follow Gauss' line of thought concerning the regular 17-gon as the practical part of cyclotomy. The more abstract considerations will follow in the next chapter.

But first of all, we want to step back from the infinite realm of the integers $\mathbb{Z},$ where we roamed up to now, to the more manageable finite.

Modular Arithmetic

For $q$th roots of unity we have the following identity: $\zeta^{q+k} = \zeta^q\zeta^k = \zeta^k$ or more general: \[\zeta^{nq+k} = (\zeta^q)^n\zeta^k = \zeta^k\eqndot \] Hence, one is more interested in the remainder  of the exponents, when dividing them by $q,$ than in the exponents themselves.

That one may perform calculations with these remainders in almost the same way as with the usual integers, has been known for a long time. It's rarely conceivable that this fact could escape the wit of a mathematician like Euler. But again it was Gauss, who in [Gauß 1801] published the systematic approach to modular arithmetic, how it has been called after Gauss' definition and notation of the so called congruence relation  \[a \equiv b \pmod{q}\] if and only if \[a - b = nq\] for $a,b \in \mathbb{Z}, q \in \mathbb{N}, q > 0$ and some $n \in \mathbb{Z}.$

The wording is, that $a$ and $b$ are congruent modulo  $q.$ The equation $a - b = nq$ is equivalent to the fact that $a-b$ can be divided by $q$ without remainder, or after isolating $a$ on the left side $a = nq+b,$ that the remainder of $a$ after division by $q$ is $b.$ Hence, it is legitimate to speak about calculation with reminders.

The relation $a \equiv b \pmod{q}$ is an equivalence relation, in other words it satisfies the following conditions:

• For all $a \in \mathbb{Z}$ holds: $a \equiv a \pmod{q}$  (reflexivity ),
• if $a \equiv b \pmod{q}$ then $b \equiv a \pmod{q}$  (symmetry ),
• if $a \equiv b \pmod{q}$ and $b \equiv c \pmod{q}$ then $a \equiv c \pmod{q}$   (transitivity ).

By an equivalence relation the underlying set is split into disjoint classes of elements, which are equivalent to each other. These classes are called equivalence classes, and the elements inherit many of their properties to these classes.

In the special case of the congruence relation the corresponding equivalence classes are called congruence classes  or residue classes. Unfortunately, there is no general convention for the notation of congruence classes. The equivalence class $\{x \in \mathbb{Z}: x \equiv a \pmod{q}\}$ of all $x$, that are congruent to a given element $a$, is sometimes denoted by $a+q\mathbb{Z},$ sometimes by $\bar{a}_q$ or even by $[a]_q.$ We will use the last given notation^[1], hence: \[[a]_q := \{x \in \mathbb{Z}: x \equiv a \pmod{q}\}\] The positive integer $q$ is called the modulus  of the congruence class $[a]_q.$

Once again it seems to depend on the federal state in Germany, whether the basics of modular arithmetic belong to the curriculum of high schools or secondary schools. However, there is a website (in German) [Duden 2010], presenting the topics one should know when taking the school-leaving examination. In English I found the following pages in Wikibooks and you will find a lot more, if you google for modular arithmetic highschool.

So I refrain from pointing out more basics and suggest to read the said websites, if necessary. That will suffice to understand the following paragraphs. If you want to exercise, you should prove the reflexivity, symmetry and transitivity of the congruence relation using only Gauss' definition. As an extra you could also prove, that the definition of $[a]_q$ does not depend on the choice of the representative  $a,$ in other words: $[a]_q = [b]_q$ if $a \equiv b \pmod{q}.$

The independance from the choice of the representative gives us the possibility to write the congruence classes as it is convenient for the problem under inspection. In most cases the smallest positive representative is used, for example: \[[0]_7, [1]_7, [2]_7, [3]_7, [4]_7, [5]_7, [6]_7\eqncomma\] sometimes the representative with smallest absolute value is more convenient: \[[0]_7, [1]_7, [2]_7, [3]_7, [-3]_7,[-2]_7, [-1]_7\eqndot\]

Often, and that's how we will do it in the following, one neglects  that one deals with congruence classes and uses integers. Instead of writing \[[5]_7 = [-2]_7\] one writes \[5 \equiv -2 \pmod{7} \eqndot\] Addition, subtraction and multiplication are performed as usual but the result is reduced modulo  the modulus, for example \[3 + 4\times6 = 27 \equiv -1 \pmod{7}\eqndot\]

The congruence classes$\pmod{q}$ form a ring , in other words one can add, subtract and multiply congruence classes without limitation. In this aspect the congruence classes are similar to the integers $\mathbb{Z}.$ One writes $\mathbb{Z}/q\mathbb{Z}$ or $\mathbb{Z}_q$ for the said ring of congruence classes and its elements are, strictly speaking, the $[a]_q.$ However, like many others, we will use the more convenient and a little bit sloppy notation $a$ for those elements, with $a \in \mathbb{Z}$.

The similarity of $\mathbb{Z}$ and $\mathbb{Z}/q\mathbb{Z}$ extends to the fact that the division operation causes problems. In $\mathbb{Z}$ the division operation of $4 : 3$ has no solution, but $4 : 2$ has. The ring $\mathbb{Z}$ has to be extended by the proper fractions to come up with the field of rational numbers $\mathbb{Q},$ in order to make all division operations solvable. However, in case of the congruence classes $\mathbb{Z}/q\mathbb{Z}$ there exist by nature classes, in which every division operation has a solution (except, of course, division by $0$, which is a taboo in every part of mathematics).

This is the case, if the modulus $q$ is a prime number. However, we want to give a more general rule of divison  for congruence classes, because in the following we will have to performe such divisions, even if the modulus is not a prime. So, let $q$ be prime or composite and let \[ka \equiv kb \pmod{q}\eqndot \] If every divison operation could be solved in $\mathbb{Z}/q\mathbb{Z},$ we could immediately cancel the $k$ and write $a \equiv b \pmod{q}.$ However, for arbitrary $q$ we can only prove \[a \equiv b \pmod{q/d}\eqncomma \] with $d = \gcd(k,q)$ the greatest common divisor  of $k$ and $q.$ The prove uses the so called Bézout identity , which is proved in every textbook about algebra^[2], in Wikipedia or on the Ja:Mathe!-site at the Mathematical Marginalia. The Bêzout identity states that with $d = \gcd(k,q)$ there always exist $u,v \in \mathbb{Z}$, such that $uk + vq = d$ holds.

Using this notation, it follows: $$ \begin{align*} d(a-b) &= (uk+vq)(a-b) \\ d(a-b) &= (ka-kb)u + q(a-b)v \\ \end{align*} $$ If we now have $ka \equiv kb \pmod{q}$, in other words $ka-kb \equiv 0 \pmod{q},$ it follows from the above equation: $$ \begin{align*} d(a-b) &\equiv (ka-kb)u + q(a-b)v \pmod{q}\\ d(a-b) &\equiv 0 \pmod{q}\\ d(a-b) &= sq, \quad \text{with an appropriate} \quad s \in \mathbb{Z}\\ a-b &= s(q/d) \\ a-b &\equiv 0\pmod{q/d}\\ a &\equiv b \pmod{q/d}\eqncomma\\ \end{align*} $$

It follows immediately, in case of the modulus $q$ being prime and thus having $d = \gcd(k,q) = 1$ for all  $k$ with $1 \leq k \lt q,$ that $k$ can be cancelled in $ka \equiv kb \pmod{q},$ because we have $q/d = q.$ Rearranging Bêzout's identity with $d=1$ one can compute the inverse of $k$. One can find an $u \in \mathbb{Z}$ with: \[uk = 1 - vq = (-v)q + 1 \] or in other words \[uk \equiv 1 \pmod{q}\eqndot\] After reducing $u \pmod{q},$ if necessary, one has for every $k \neq 0$ the inverse $u = 1/k = k^{-1}$ within the ring of congruence classes and every divison can be performed by simply multiplying with the inverse.

On the other hand, if $q$ is not prime, there is a factorization $q = rs$ with $1 \lt r,s \lt q.$ In other words $rs \equiv 0 \pmod{q}.$ If there would be an inverse $r^{-1}$ of $r,$ we had \[1 \equiv r^{-1}r \equiv r^{-1}(r + rs) \equiv 1 + s\ \pmod{q} \eqncomma\] from which followed $s \equiv 0 \pmod{q}$ in contradiction to our precondition $1 \lt r,s \lt q.$

Hence, the ring of congruence classes $\mathbb{Z}/q\mathbb{Z}$ is in fact a field, if and only if the modulus $q$ is prime. In other words, addition, subtraction, multiplication and division can be performed as usual in such a field of congruence classes. That's one of the reasons, why we try to restrict our constructibility considerations to regular polygons with a prime number of vertices in what follows.

Restriction to Polygons with a Prime Number of Vertices

First of all we notice that the constructibility of the regular $n$-gon implies the constructibility of the regular $2n$-gon, $4n$-gon and generally of the regular $(2^k\cdot n)$-gon. To perform the construction, one has simply to successively bisect all the angles $\cos(2\pi/n),$ and that is an elementary construction with ruler and compass, already taught at school.

The other way round, with every constructible $(2^k\cdot n)$-gon the $n$-gon is also constructible – you have simply to connect every $2^k$-th vertex in a round robin manner with help of your straightedge.

Likewise you see, that the constructibility of a regular $(m\cdot n)$-gon implies the constructibility of the $m$-gon and the $n$-gon: connect every $n$th or $m$th vertex with your straightedge.

A little bit more demanding is the proof, that one can construct the $(m\cdot n)$-gon, provided the $m$-gon and the $n$-gon are constructible – and, as a matter of fact, that's true only for coprime  $m$ and $n.$

It follows from the precondition that the coordinates of the roots of unity $\zeta_m$ and $\zeta_n$ are constructible (here we need the index, to distinguish between the $m$th and the $n$th root of unity). Hence, every power of these roots of unity is also constructible, especially the powers $\zeta_m^b$ and $\zeta_n^a,$ where we have chosen $a$ and $b,$ applying the omnipresent Bêzout identity, in such a way that $am + bn = 1$ holds (this is possible, because $m$ and $n$ are supposed to be coprime).

The product of these powers is constructible as well, and we have: $$ \begin{align*} \zeta_m^b\zeta_n^a &= e^{\frac{2\pi\I b}{m}}e^{\frac{2\pi\I a}{n}}\\ &= e^{\frac{2\pi\I bn}{mn}}e^{\frac{2\pi\I am}{mn}} \\ &= e^{\frac{2\pi\I(am+bn)}{mn}}\\ &= e^{\frac{2\pi\I}{mn}} = \zeta_{mn} \end{align*} $$ You may have noticed that $a$ or $b$ could have been negative integers, but because of $x^{-a} = 1/{x^a}$ this has no negative effect on the constructibility of the powers. Moreover, for $n$th roots of unity it holds \[\zeta_n^{-a} = \frac{1}{\zeta_n^a} = \zeta_n^{n-a} \eqncomma\] so that one can avoid the division. We remember that multiplication of complex numbers with absolute value $1$ is nothing else as addition of the polar angles. Hence, the construction of a $mn$-gon reduces to clever addition and subtraction of multiples of the central angles of the $m$-gon and the $n$-gon. You may want to try to construct the central angle of the regular 15-gon (24°) by fiddling around with the central angle of the regular triangle (120°) and of the regular pentagon (72°).

As a consequence, we will no longer bother about polygons with a composite number $n$ of vertices, but restrict ourselves to $p$-gons, where $p$ is any (odd) prime.

The square, however, gets out of line in this context. Technically it belongs to the $(2^k\cdot n)$-gons with $k=1$ and the corresponding prime $2$-gon as basis. Now it needs utmost generosity to regard the $2$-gon as regular polygon, although the construction of the square, like that of any other $2n$-gon is performed by bisecting the central angle of 180° of the $2$-gon. Therefore, the phrase odd had been added at the above paragraph, and we will cast a veil of silence over the square in what follows.

Fermat Primes

The primality is needed, because we now start to establish an order among the roots of unity. That kind of order, Gauss discovered for the 17th roots of unity, and which allows to represent sums of roots of unity as square root expressions. We have already seen that \[\zeta^{p-1}+\zeta^{p-2}+\dots+\zeta^2+\zeta=-1\] holds, and that \[\zeta + \zeta^{p-1} = 2cos(2\pi/p) \eqndot\] Gauss discovered, how to descend from the sum of all roots of unity to the sum of two roots of unity by successively dividing in half the number of summands, while at the same time assuring that every new sum can be expressed as a square root expression of the old sums. To make this work, it's not only required that $p$ is prime, but that $p-1$ is a power of two, otherwise the successive division in half would not be possible. The importance of the primality will be considered later on, to begin with, we will discuss the consequences of $p$ being a power of two.

So, let $p = 2^k+1.$ Those primes are called Fermat primes , after Pierre de Fermat (1607-1665), who became famous because of his marginal notes. $2^k+1$ can only be prime, if $k$ itself is a power of two. To prove this, at first assure yourself that for all $z \in \mathbb{Z}$ we have \[z \equiv -1 \pmod{z+1}\eqndot\] If $k$ were no power of two, it would have at least one odd factor $u,$ and could be written as $k = tu$ with $1 \leq t,u \lt n$ and odd $u.$ It follows \[2^k+1 \equiv (2^t)^u +1 \equiv (-1)^u + 1 \equiv 0 \pmod{2^t+1} \eqndot\] Hence, $2^k+1 = (2^t)^u + 1$ would be divisible by $2^t+1$ and thus be no prime.

For $p = 2^{2^n}+1$ and for $n=0,1,2,3,4$ one has the Fermat primes $3, 5, 17, 257$ and $65537.$ Fermat himself believed that all Fermat numbers of the form $2^{2^n}+1$ were prime, but already for $n=5$ Euler demonstrated that the number \[2^{2^5} = 4294967297 = 641 \cdot 6700417\] is composite. For all $n \le 32$ the Fermat numbers have been tested for primality, but up to now^[4] no additional prime has been found.

Gaussian Periods and Primitive Elements

But why do we insist on $p$ being a prime? This is a consequence of the way, how the sums of roots of unity are formed. We will present this method at first without justification, which will follow later on. The sums of roots of unity, constructed that way, are called Gaussian periods . The first one, or better the $0$th Gaussian period is identical with the well known sum $\zeta^{p-1}+\zeta^{p-2}+\dots+\zeta^2+\zeta=-1,$ however the order of the summands is changed, and we will now explain in what way:

If $p$ is prime , the ring (or rather the field) of congruence classes $\mathbb{Z}/p\mathbb{Z}$ contains elements $\omega,$ so that every element of $\mathbb{Z}/p\mathbb{Z}$ other than $0$ can be uniquely represented as $\omega^k$ with $0 \leq k \lt p-1.$ Such an $\omega$ is called primitive element  or primitive root  ^[5] (We will stick to the terminology primitive element, to avoid a third flavour of roots besides the roots of unity and the roots in our square root expressions).

So, $5$ is a primitive element in $\mathbb{Z}/7\mathbb{Z}$: \[ \begin{array}{rrrrrrr} 5^0,& 5^1,& 5^2,& 5^3,& 5^4,& 5^5&\pmod{7} \\ 1,& 5,& 4,& 6,& 2,& 3&\pmod{7} \end{array} \] but $2$ is no primitive Element in $\mathbb{Z}/7\mathbb{Z}$: \[ \begin{array}{rrrrrrr} 2^0,& 2^1,& 2^2,& 2^3,& 2^4,& 2^5&\pmod{7} \\ 1,& 2,& 4,& 1,& 2,& 4&\pmod{7} \end{array} \] because only the three elements $1,2$ and $4$ are generated by its powers.

Of course, one tries to avoid computing 4th or 5th powers of an integer, but reduces the result$\pmod {7}$ immediately after multiplying with $5$ or $2$.

Because we are interested only in exponents other than $0$ when we deal with the powers of roots of unity, we can represent all the exponents as powers of a primitive element, provided $p$ is prime. And that's the way Gauss ordered the roots of unity in his Gaussian periods, namely taking the exponents in the order of successive powers of a primitive element, for example for the $0$th Gaussian period: \[\zeta^{\omega^0}+\zeta^{\omega^1}+\zeta^{\omega^2}+\dots\] Following Gauss, it became common practice to take $3$ as primitive element, that works for all Fermat primes $\geq 5,$ and so in all cases we deal with.

As an example look at the $0$th Gaussian period for $p = 17$: \[\zeta^{3^0}+\zeta^{3^1}+\zeta^{3^2}+\dots+\zeta^{3^{15}} \eqncomma\] \[\zeta^1 + \zeta^3 +\zeta^9 + \zeta^{10} + \zeta^{13} + \zeta^{5}+\zeta^{15}+\zeta^{11}+\zeta^{16}+\zeta^{14}+\zeta^{8}+\zeta^{7}+\zeta^{4}+\zeta^{12}+\zeta^{2}+\zeta^{6}\] If you multiply the exponent of the last summand $\zeta^6$ once again with $3,$ you get $\zeta^{18}=\zeta^1,$ hence the name period. It's easy to verify that the $0$th Gaussian period indeed contains all roots of unity other than $\zeta^0 = 1,$ thus its value is $-1.$ Furthermore, you see that every summand of the period is generated from its predecessor by raising it to the power$\pmod{p}$ of the primitive element, because we have: \[\zeta^{\omega^{n+1}} = \zeta^{\omega^n\omega} = (\zeta^{\omega^n})^\omega\] (the predecessor of the first summand is taken to be the last summand).

Two Remarkable Properties

Two remarkable properties of primitive elements will be discussed in the following paragraphs, because they will be useful later on:

We have seen that $\mathbb{Z}/p\mathbb{Z}$ is a field, if $p$ is prime. In other words, there are two operations defined in $\mathbb{Z}/p\mathbb{Z},$ addition and multiplication (subtraction and division can be regarded as addition or multiplication with the particular inverse). Viewing the operations separately we can say that $\mathbb{Z}/p\mathbb{Z}$ is a group with regard to addition and $\mathbb{Z}/p\mathbb{Z}\backslash\{0\}$ is a group with regard to multiplication. These groups within a field are called the additive  and multiplicative  group of $\mathbb{Z}/p\mathbb{Z}$ respectively and the notation is $\mathbb{Z}/p\mathbb{Z}^{+}$ and $\mathbb{Z}/p\mathbb{Z}^{\times}$ respectively.

If you don't know or don't remember, what a group is in mathematics, and don't want to consult the Wikipedia either, don't panic: We will hardly rest on more than the fact, that in a group there exists only one  operation, (in contrast to the two  operations in a field), and that this operation and its inverse can be executed without limitations within the group.

Now, a primitive element allows a connection between the multiplicative group $\mathbb{Z}/p\mathbb{Z}^{\times}$ and the additive group $\mathbb{Z}/(p-1)\mathbb{Z}^{+}$.

To save space, our example is about the primitive element $3$ in $\mathbb{Z}/5\mathbb{Z}.$ We show the multiplication table$\pmod{5}$:

You see, that the elements of $\mathbb{Z}/5\mathbb{Z}$ other than $0$ form a group with regard to multiplication. Every element can be written as some power of the primitive element $3$ and the exponents are added$\pmod{4}$, if the elements themselves are multiplied$\pmod{5}$. The exponents can be identified with the additive group $\mathbb{Z}/4\mathbb{Z}^{+}.$

In general one defines a mapping of groups, using the primitive element: \[ \require{AMScd} \begin{CD} \mathbb{Z}/p\mathbb{Z}^{\times} @>f>> \mathbb{Z}/(p-1)\mathbb{Z}^{+}\\ @. @. @.\\ \omega^k @>f>> k \end{CD} \] It's immediately seen that $f$ is well defined, because for every element of $\mathbb{Z}/p\mathbb{Z}^{\times}$ there exists only one image to which it is mapped (remember that the representation by powers of a primitive element has been said to be unique). Furthermore, a little calculation shows that \[f(\omega^k\cdot\omega^j) = f(\omega^{k}) + f(\omega^{j})\] holds. The same is true for the inverse mapping \[ \begin{CD} \mathbb{Z}/(p-1)\mathbb{Z}^{+} @>f^{-1}>> \mathbb{Z}/p\mathbb{Z}^{\times}\\ @. @. @.\\ k @>f^{-1}>> \omega^k \end{CD} \]

Such a mapping, respecting the group operation and having an inverse mapping, is called an isomorphism  of the two groups. In this case one often simply forgets  that the two groups are only isomorphic, but treats them as being the same. The first remarkable property  results from this isomorphism:

Let's assume that we have \[\omega^k \equiv \omega^m \pmod{p}\] in other words \[\frac{\omega^k}{\omega^m} \equiv 1 \pmod{p} \eqndot\] Applying the isomorphism $f$ we get \[f(\frac{\omega^k}{\omega^m}) \equiv 0 \pmod{p-1}\] hence \[f(\omega^k)-f(\omega^m) \equiv 0 \pmod{p-1}\] and by definition of $f$ we have \[k-m \equiv 0 \pmod{p-1}\] and finally \[k \equiv m \pmod{p-1} \eqndot\]

We have shown:

The second remarkable property  refers to the representation of $-1$ as a power of $\omega.$ We have \[1 \equiv \omega^{p-1} \equiv (\omega^{(p-1)/2})^2 \pmod{p}\eqndot\] Hence \[\omega^{(p-1)/2} \equiv \pm 1\pmod{p}\eqndot\] The solution $+1$ is impossible, because this value is already taken by $\omega^{p-1}.$ Thus $-1 \equiv \omega^{(p-1)/2} \pmod{p}$ holds and we have:

Divide and Conquer

After completion of the preliminaries we will for the rest of the chapter concentrate on the 17-gon, so we fix the prime $p=17.$ Beginning with the 0th Gaussian period, which we call $p_{0,0}$ from now on, we want to descent and divide in half the length of the period step by step until we finally arrive at a sum of length $2,$ for example $\zeta + \zeta^{p-1}.$

If you follow the rule that after dividing a period in half the results should again be periods, in other words that every summand shall be computed by exponentiation$\pmod{p}$ of its predecessor, you have hardly a choice how to perform the splitting: We simply sort by the even and odd powers of the primitive element $3$, in other words we split by taking every second summand: \[p_{1,0} = \zeta^1 + \zeta^9+ \zeta^{13} +\zeta^{15}+\zeta^{16}+\zeta^{8}+\zeta^{4}+\zeta^{2}\eqncomma\] \[p_{1,1} = \zeta^3 + \zeta^{10} + \zeta^{5}+\zeta^{11}+\zeta^{14}+\zeta^{7}+\zeta^{12}+\zeta^{6}\eqndot\] At the same time we have introduced the notation that will be generated by the Java program later on. We will call the first index $k$ in $p_{k,n}$ the level of the period or speak of the $k$th period. In contrast to the $0$th period, in these shorter periods every summand is created by exponentiation with $3^2$ (or generally $\omega^2$) from its predecessor, not by exponentiation with $3$ (or $\omega$). Of course all exponentiations are$\pmod{p}$.

Another important property of the thus created Gaussian periods can be immediately verified: With every root of unity $\zeta^k$ its complex conjugate $\bar{\zeta^k} = \zeta^{p-k}$ is also in the same period. Hence, when taking the sum, the imaginary parts of the roots of unities cancel out and the result is a real number. For the 17-gon the verification of this fact may be done by pointing with your pencil. That the numeric value of every  Gaussian period for every Fermat prime $p$, created by this kind of splitting, is a real number, will be shown later on.

Because the two periods of level $1$ have been created by splitting the period of level $0$, it is clear that $p_{1,0}+p_{1,1} = p_{0,0}.$ That is no rocket science, but now comes a flash of genius, and it's well possible that it has been exactly this insight, that Gauss came up with on that morning in his bed. The periods of length $1$ cannot only be added but also multiplied, and the result is stunning indeed:

Because one has to multiply every summand of $p_{1,0}$ with every summand of $p_{1,1}$, we have $8\times8$ products that have to be added, and we give a multiplication table for the exponents without the basis $\zeta$. Of course, everything is calculated$\pmod {17}$ and the exponents have to be added  when the powers of the roots of unity are multiplied.

Of course, you could as well expand the product by hand: $$ \begin{align} p_{1,0} \cdot p_{1,1} &= (\zeta^1 + \zeta^9+ \zeta^{13} +\zeta^{15}+\zeta^{16}+\zeta^{8}+\zeta^{4}+\zeta^{2}) \\ &\quad \quad \cdot (\zeta^3 + \zeta^{10} + \zeta^{5}+\zeta^{11}+\zeta^{14}+\zeta^{7}+\zeta^{12}+\zeta^{6}) \\ &= \zeta^{1+3} + \zeta^{1+10} + \dots + \zeta^{2+12} + \zeta^{2+6} \\ &= \zeta^4 + \zeta^{11} + \dots + \zeta^{14} + \zeta^8 \\ &= \dots \end{align} $$ You will admit that this is cumbersome, but try it anyway and compare your result with the one got by evaluation of the following table, which in fact has been calculated by a spreadsheet program.

With a little effort you can verify that all  exponents appear as products in the above table, and every one does so exacly $4$ times – we say that every exponent has multiplicity of $4.$ So, when all is summed up we get $4p_{0,0}$. Hence, in addition to the equation \[p_{1,0} + p_{1,1} = p_{0,0} = -1\] we have \[p_{1,0}\cdot p_{1,1} = 4 p_{0,0} = -4\]

and thus representations of sum and product of two Gaussian periods, that do not contain any debris in form of isolated roots of unity. Everybody, who once in his or her life has solved a quadratic equation, should be thrilled by that fact – and it's dead certain that young Gauss has been thrilled by the two equations. They are nothing else but one of Vieta's formulae: the coefficients of a normalized quadratic equation can be expressed by sum and product of its zeroes (taking proper signs). Furthermore, if the coefficients are rational numbers, the zeroes are square root expressions containing only rational numbers. $$ \begin{align*} (x-x_0)(x-x_1)&=0\\ x^2 -x_0 x -x_1 x + x_0 x_1 &= 0 \\ x^2 -(x_0+x_1)x + x_0 x_1 &= 0 \end{align*} $$ Of course, the coefficients are the elementary symmetric expressions (the most elementary indeed), which we already introduced in the preceding chapter.

The solution of this quadratic equation is given by the well known midnight formula \[x_{0;1} = \frac{x_0+x_1}{2} \pm \sqrt{(\frac{x_0+x_1}{2})^2 - x_0 x_1}\] or, slightly modified \[x_{0;1} = \frac{(x_0+x_1) \pm \sqrt{(x_0+x_1)^2-4x_0 x_1}}{2}\eqncomma\] what can be easily verified by expanding and using the binomial theorem backwards.

Hence $p_{1,0}$ and $p_{1,1}$ are solutions of the quadratic equation \[ x^2 -(p_{1,0}+p_{1,1})x + p_{1,0}p_{1,1} = 0 \] or, after inserting \[ x^2 + 1x - 4 = 0 \eqncomma \] and by the modified midnight formula \[p_{1,0;1,1} = -\frac{1}{2} \pm \frac{1}{2}\sqrt{17}\eqndot\]

Thus, the first of the square root expressions, needed for the construction with ruler and compass, is finally found. Note, that for the present we keep open the question, which sign has to be chosen for $p_{1,0}$ and which for $p_{1,1}.$

The next steps are obvious. If it is possible to divide in half the periods of level $k$ in such a way, that sum and product of these periods can be computed as a rational expression in the periods of level $k-1,$ it will also be possible to compute the periods of level $k$ as solution of a quadratic equation, whose coefficients are rational expressions in the periods of level $k-1$. Furthermore we have seen (at least for the example of $p = 17$) that the value of a Gaussian period is always a real number, hence the solutions of these quadratic equations satisfy the condition for constructible points. In this way we can descent down to the Gaussian periods of length $2$ and finally represent $\zeta + \zeta^{p-1} = 2\cos(2\pi/p)$ as square root expression.

For the sum of two Gaussian periods, created by splitting, this is trivial, because the sum equals the splitted period by construction. For the product the required rational expression is not so easy to find. In case of the 17-gon we used (and will use) a multiplication table, in case of the 257-gon and the 65537-gon it's exactly the purpose of the Java program, we are going to develop in chap.6, to find the desired representation of the product of two Gaussian periods as rational expression or even as linear combination of periods of the preceding level.

In other words, the Java program is the experimental  proof, that this representation is always possible and that the value of the periods is always a real number. However, the program does not give a hint, why it's just this kind of splitting the sums of roots of unity, using successive powers of a primitive element as exponents, that works. We will try to answer this question in the next chapter by inspecting the product of Gaussian periods in more detail.

But let us first finish the example of the 17-gon. We continue where we stopped a few paragraphs ago and split the periods of length $8$: \[p_{1,0} = \zeta^1 + \zeta^9+ \zeta^{13} +\zeta^{15}+\zeta^{16}+\zeta^{8}+\zeta^{4}+\zeta^{2}\eqncomma\] \[p_{1,1} = \zeta^3 + \zeta^{10} + \zeta^{5}+\zeta^{11}+\zeta^{14}+\zeta^{7}+\zeta^{12}+\zeta^{6}\eqndot\] yield after the splitting: \[p_{2,0} = \zeta^1 + \zeta^{13} +\zeta^{16}+\zeta^{4}\eqncomma\] \[p_{2,2} = \zeta^9 +\zeta^{15}+\zeta^{8}+\zeta^{2}\eqndot\] \[p_{2,1} = \zeta^3 + \zeta^{5}+\zeta^{14}+\zeta^{12}\eqncomma\] \[p_{2,3} = \zeta^{10} +\zeta^{11}+\zeta^{7}+\zeta^{6}\eqndot\] Why the periods got by splitting $p_{1,0}$ are called $p_{2,0}$ and $p_{2,2}$ will become clear later on, for the moment you have to take it as arbitrary notation. Hence, we have two multiplication tabels for $p_{2,0} \cdot p_{2,2}$ and $p_{2,1} \cdot p_{2,3}.$ As before, the tables contain only the exponents:

and

You see, that all exponents appear as products with multiplicity $1$ in each of the tables. Thus we have \[p_{2,0} \cdot p_{2,2} = p_{1,0} + p_{1,1} = p_{0,0}\] and \[p_{2,1} \cdot p_{2,3} = p_{1,0} + p_{1,1} = p_{0,0}\eqndot\]

We take the solution formula for quadratic equations from above, and replace $x_0+x_1$ and $x_0\cdot x_1$ by $p_{2,0}+p_{2,2} = p_{1,0}$ and $p_{2,0} \cdot p_{2,2} = p_{0,0}$ respectively. Hence we get \[p_{2,0} = \tfrac{p_{1,0} + \sqrt{p_{1,0}^2 - 4p_{0,0}}}{2}\eqncomma\] \[p_{2,2} = \tfrac{p_{1,0} - \sqrt{p_{1,0}^2 - 4p_{0,0}}}{2}\] and the same with $p_{2,1}$ and $p_{2,3}$ \[p_{2,1} = \tfrac{p_{1,1} + \sqrt{p_{1,1}^2 - 4p_{0,0}}}{2}\eqncomma\] \[p_{2,3} = \tfrac{p_{1,1} - \sqrt{p_{1,1}^2 - 4p_{0,0}}}{2}\eqndot\] As before, we do not yet justify, why we set the signs in just this way.

Now we are almost done, as we need only to look at the two periods of length $2$, created by splitting of $p_{2,0}$: \[p_{3,0} = \zeta^1 + \zeta^{16}\eqncomma\] \[p_{3,4} = \zeta^{13} +\zeta^{4}\eqndot\] $p_{3,0}$ equals, as we have seen before, $2\cos(2\pi/17),$ and again I ask for your patience concerning the reason for the notation $p_{3,4}.$

We have trivially \[p_{3,0} + p_{3,4} = p_{2,0}\] and give again a multiplication table for the product $p_{3,0} \cdot p_{3,4}$

A short search among the periods of length $4$ gives the desired representation as linear combination \[p_{3,0} \cdot p_{3,4} = p_{2,1}\eqncomma\] so we get the solutions \[p_{3,0} = \tfrac{p_{2,0} + \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqncomma\] \[p_{3,4} = \tfrac{p_{2,0} - \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqndot\]

By inserting successively the expressions for $p_{2,0}, p_{2,1}, \dots$ etc. into the expression for $p_{3,0}$ we finally get a square root expression with only rational coefficients for $\cos(2\pi/17) = \frac{1}{2}p_{3,0}.$ In chap.7 these computations are completely presented in case of the 17-gon.

You see that it has been wise on behalf of the young Gauss, to give only the construction description for the 17-gon. Already the 257-gon would require multiplication tables of such size, that one gets totally lost. On the other hand, the algorithm itself is so simple, that it cries out for implementation by a computer program – and that's exactly what shall be done in the next but one chapter.