ruler and compass construction of regular polygons

The problem of which regular polygons can be constructed by ruler and compass alone goes back to the ancient Greeks. They could certainly construct a regular pentagon, for example. Fast forward a couple of thousand years and the nineteen year-old wunderkind Gauss made the first new progress on the problem when he constructed the regular 17-gon. Gauss discovered necessary and sufficient conditions for constructibility of the regular n-gon and he recorded his result in Section VII of Disquisitiones Arithemeticae published in 1801. To explain Gauss's result we need a definition.

Definition A number of the form 2²ⁿ+1 with n a nonnegative integer is called a Fermat number.

The first 5 Fermat numbers are: 3, 5, 17, 257, 65537. All of these are prime and Fermat conjectured in 1640 that all the Fermat numbers are prime. Rather surprisingly it wasn't until 1732 that Euler pointed out that the next Fermat number 4294967297 is not prime. It is divisible by 641. In fact the first 5 are the only know prime Fermat numbers and it seems reasonable that there are no others.

Theorem (Gauss) A regular n-gon is constructible by ruler and compass alone if and only if

n = 2^kp₁...p_t

where k and t are nonnegative integers and p_i are distinct prime Fermat numbers.

Interestingly, to construct a regular p-gon with p a Fermat prime, the first step is to construct sqrt(p).

Other random facts about constructing polygons with straightedge and compass:

• Gauss requested that his construction of the 17-gon be inscribed on his tombstone (apparently it wasn't).
• The proof of Gauss' theorem stated by Noether (the E2 user, not the Emily Noether!) uses Galois theory.
• Gauss couldn't have known about Galois theory.

To construct a polygon of a non-prime number of sides, your best bet is to factor it into its powers of two and Fermat primes, and then happen to have lying around polygons with the number of sides specified by the prime factors. From there, if your primes are p1, p2 and p3, for example, you will have access to angles of size 2π/p1, 2π/p2 and 2π/p3. It is now up to you to use linear Diophantine equations to determine how to construct an angle of 2π/(p1*p2*p3), a process described in regular 17476-gon, and then halve this angle as many times as you have powers of two. Then, walk that angle around any circle and connect the dots.

But you say you don't have polygons of prime number of sides to begin with? Well, I'll do what little I can to remedy that.

Construction of a triangle
Open your compass as large as you like and make a circle. Now put the point of the compass on the edge of the circle (never change the compass opening unless I tell you to!) and draw a second circle. Congratulations, you have a vesica piscis. And come to think of it, you have a triangle too. Use your ruler to connect one of the intersections of the circles to each of the circle's centers, then connect the centers together. Voila! If you want a bigger triangle, extend the two lines stemming from the intersection to the opposite edges of the circles, and then connect these intersections together as well.

Construction of a square Yeah, 4 isn't a Fermat prime -- still might be useful
Construct a vesica piscis... you know, the two circles, each one with its center on the other's circumference. Now connect the centers of the two circles, and connect their intersection points with the ruler. Move the point of the compass to the intersection of these perpendicular lines, and close it until the pencil rests on the center of one of the circles. Draw a circle. Connect the four points where the new circle's edge touches a line or the center of another circle. Doesn't look like a square? Tilt the page 45 degrees.

Construction of a pentagon
Construct a vesica piscis. Now, use the ruler to connect the two centers, and to connect the intersection points of the circles. Call these lines A and B, respectively. Where these two perpendicular lines cross we'll call point C. Place the point of the compass on C, and close the compass until the pencil is resting on the center of one of the circles. Inscribe a circle inside the vesica piscis, and call it O. Now, move the point of the compass to the center of one of the original circles. Make another small circle. Draw a line (D) connecting the intersections of the small circles. Place the point of the compass where D meets A, and open it until the pencil can rest on the point where line B meets circle O. Draw an arc from this point down until you reach line A, and call this point E. Place the compass point on the intersection of O and B, and open the pencil to point E. The compass opening now represents an angle of 72 degrees on the small circle. From where the point is located, make a mark with the pencil on circle O. Move the point to the new mark, and make a second mark along the circle. Keep walking the compass around the circle until you reach your starting point. If you didn't screw up, you have five equally spaced points which you will take great pleasure in connecting.

Construction of a hexagon
Draw a circle. With the same compass opening, put the point on the edge of the circle, and make two marks with the pencil on the circle. Walk around the circle, placing the compass point on an existing mark and making a new one with the compass pencil, and when you're done you'll have the six points. Connect them. (You could just make a triangle as described above, then bisect the angles and extend the new angles until the reach the edge of the circle you started with. But that's more of a hassle, IMO)

Construction of a Heptakaidecagon (17-gon)
I'm afraid I don't know this one, and even the proof for its existence was too dense for me to wade through. If you've been blessed with this particular knowledge, feel free to add it below.