The central idea is to view the vertices of the polygon on a unit circle
as complex numbers, solutions of z^{N} = 1. The vertices are thus "Nth roots
of unity". Gauss showed certain sums of roots could be solved recursively
in terms of other sums with quadratic equations, winding up with the
sum of a conjugate pair of roots, half of which gives the real part of
a root. Since quadratic equations can be solved with ruler and compass,
the construction can be done.

Algorithm:

- Find an integer K that generates the multiplicative group of Z
_{N}. K = 3 happens to work for N = 5,17,257,65537, so we'll just use that. - List the powers of K mod N, i.e. for N = 17 we have 1, 3, 9, 10, ... This list has N-1 elements, since 0 does not occur, not being in the multiplicative group. List the N-1 roots in this order (omitting 1).
- Let S(m,i) be the sum of every m
^{th}root from the list, starting the i^{th}. We will only use powers of 2 for m. Note that S(1,0) = -1, since all N roots sum to 0 (the coefficient of z^{N-1}in z^{N}- 1 = 0), and 1 is omitted. - It turns out that S(2*m,i)*S(2*m,i+m) is a linear combination of S(m,j) and lower terms with integer coefficients. Also, S(2*m,j)+S(2*m,j+m) = S(m,j). Starting with S(1,0) = -1, we can recursively solve quadratic equations for all the S(m,i).
- For m = (N-1)/2, it turns out S(m,i) is the sum of two conjugate roots, so S((N-1)/2,i) is the x coordinate of those two roots, say U and V.
- The chord between any two roots (say 1 and U, or U and V) can be use to lay off chords around the unit circle to construct all N vertices.

a0 = -1 prod = 4*a0 a1 = (a0 + Sqrt[a0^2 - 4*prod])/2 prod = 4*a0 a2 = (a0 - Sqrt[a0^2 - 4*prod])/2 prod = 1*a0 a5 = (a1 - Sqrt[a1^2 - 4*prod])/2 prod = 1*a0 a6 = (a2 - Sqrt[a2^2 - 4*prod])/2 prod = 1*a6 a13 = (a5 + Sqrt[a5^2 - 4*prod])/2 x2 = a13/2

a0 = -1 prod = 64*a0 a1 = (a0 + Sqrt[a0^2 - 4*prod])/2 prod = 64*a0 a2 = (a0 - Sqrt[a0^2 - 4*prod])/2 prod = 16*a0 a3 = (a1 + Sqrt[a1^2 - 4*prod])/2 prod = 16*a0 a4 = (a2 + Sqrt[a2^2 - 4*prod])/2 prod = 16*a0 a5 = (a1 - Sqrt[a1^2 - 4*prod])/2 prod = 16*a0 a6 = (a2 - Sqrt[a2^2 - 4*prod])/2 prod = 5*a0 - 1*a1 - 2*a3 a7 = (a3 + Sqrt[a3^2 - 4*prod])/2 prod = 5*a0 - 1*a2 - 2*a4 a8 = (a4 - Sqrt[a4^2 - 4*prod])/2 prod = 5*a0 - 1*a1 - 2*a5 a9 = (a5 + Sqrt[a5^2 - 4*prod])/2 prod = 5*a0 - 1*a2 - 2*a6 a10 = (a6 - Sqrt[a6^2 - 4*prod])/2 prod = 5*a0 - 1*a1 - 2*a3 a11 = (a3 - Sqrt[a3^2 - 4*prod])/2 prod = 5*a0 - 1*a2 - 2*a4 a12 = (a4 + Sqrt[a4^2 - 4*prod])/2 prod = 5*a0 - 1*a1 - 2*a5 a13 = (a5 - Sqrt[a5^2 - 4*prod])/2 prod = 5*a0 - 1*a2 - 2*a6 a14 = (a6 + Sqrt[a6^2 - 4*prod])/2 prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9 a15 = (a7 + Sqrt[a7^2 - 4*prod])/2 prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10 a16 = (a8 + Sqrt[a8^2 - 4*prod])/2 prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11 a17 = (a9 + Sqrt[a9^2 - 4*prod])/2 prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12 a18 = (a10 + Sqrt[a10^2 - 4*prod])/2 prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13 a19 = (a11 + Sqrt[a11^2 - 4*prod])/2 prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14 a20 = (a12 + Sqrt[a12^2 - 4*prod])/2 prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7 a21 = (a13 - Sqrt[a13^2 - 4*prod])/2 prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8 a22 = (a14 + Sqrt[a14^2 - 4*prod])/2 prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9 a23 = (a7 - Sqrt[a7^2 - 4*prod])/2 prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10 a24 = (a8 - Sqrt[a8^2 - 4*prod])/2 prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11 a25 = (a9 - Sqrt[a9^2 - 4*prod])/2 prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12 a26 = (a10 - Sqrt[a10^2 - 4*prod])/2 prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13 a27 = (a11 - Sqrt[a11^2 - 4*prod])/2 prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14 a28 = (a12 - Sqrt[a12^2 - 4*prod])/2 prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7 a29 = (a13 + Sqrt[a13^2 - 4*prod])/2 prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8 a30 = (a14 - Sqrt[a14^2 - 4*prod])/2 prod = 1*a23 + 1*a24 + 1*a25 + 1*a28 a39 = (a23 - Sqrt[a23^2 - 4*prod])/2 prod = 1*a24 + 1*a25 + 1*a26 + 1*a29 a40 = (a24 - Sqrt[a24^2 - 4*prod])/2 prod = 1*a30 + 1*a15 + 1*a16 + 1*a19 a46 = (a30 + Sqrt[a30^2 - 4*prod])/2 prod = 1*a15 + 1*a16 + 1*a17 + 1*a20 a47 = (a15 - Sqrt[a15^2 - 4*prod])/2 prod = 1*a16 + 1*a17 + 1*a18 + 1*a21 a48 = (a16 - Sqrt[a16^2 - 4*prod])/2 prod = 1*a22 + 1*a23 + 1*a24 + 1*a27 a54 = (a22 + Sqrt[a22^2 - 4*prod])/2 prod = 1*a23 + 1*a24 + 1*a25 + 1*a28 a55 = (a23 + Sqrt[a23^2 - 4*prod])/2 prod = 1*a30 + 1*a40 - 1*a46 a71 = (a39 - Sqrt[a39^2 - 4*prod])/2 prod = 1*a22 + 1*a48 - 1*a54 a111 = (a47 + Sqrt[a47^2 - 4*prod])/2 prod = 1*a7 - 1*a15 - 1*a55 - 1*a71 a239 = (a111 - Sqrt[a111^2 - 4*prod])/2 x32 = a239/2

References:

- Carl Friedrich Gauss, Disquitiones Arithmeticae, 1801, section VII. (English translation by Arthur A. Clarke, 1965 (Yale).)
- Christian Gottlieb, "The Simple and Straightforward Construction of the Regular 257-gon," Mathematical Intelligencer, vol. 21, no. 1, 1999, p. 31-37.

Back to constructions.

Back to Ken Brakke's home page.

Susquehanna University assumes no responsibility for the content of this personal website. Please read the disclaimer.