The following messages were sent by and in answer to Professor John Conway of Princeton
University's Mathematics Department to geometry discussion groups (geometrypuzzles,
geometryprecollege, geometrypuzzles) in answer to questions about constructing regular
polygons. An alternative simple construction of a regular pentagon
has been contributed by Floor van Lamoen ("Dr. Floor"); see also Inscribing a regular pentagon in a circle  and proving it, by Scott E. Brodie.
1. Polygons with compass and straightedge
It's a VERY famous theorem of Gauss that the only regular polygons
with a prime number of sides that can be constructed with straightedge
and compass are those for which the prime is one of the Fermat primes
3, 5, 17, 257, 65537, ...
(that is, primes of the form 2^n + 1). Nobody knows if there are
any Fermat primes larger than 65537.
The only constructible regular polygons with an odd number of
sides are those for which this number is a product of distinct
Fermat primes (so for instance 15 = 3 times 5, 51 = 3 times 17),
and the only ones with an even number of sides are those obtained
by repeatedly doubling these numbers (including 1), thus:
(1,2), 4, 8, 16, 32, 64, ...
3, 6, 12, 24, 48, ...
5, 10, 20, 40, 80, ...
15, 30, 60, ...
17, 34, 68,...
51, ...
85,...
Some people might like the following little observation.
Write out the Pascal triangle modulo 2 :
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
...................
then by reading the first 31 rows as the binary expansions of
numbers, you get
1, 3, 5, 15, 17, 51, 85, 255, 257, ...
which give the first few oddsided constructible polygons (and
very probably all there are).
John Conway
2. Construction of a regular pentagon
Let N,S,E,W be the points of a circle with center O in the four
compass directions, M be the midpoint of ON and MX (with X on OE)
the bisector of the angle OME:
Then the line through X perpendicular to OE hits the circle
in two points of the regular pentagon that has a vertex at E. You
can either get the other two points by stepping around the circle with
a compass set to the edgelength so found for the pentagon, or by
replacing X in the above by the point Y where the EXTERNAL bisector
of OME meets OW.
How about septagons?
Well, for one thing the proper name is "heptagon", not "septagon." There
isn't a construction for a regular heptagon using ruler and compass according
to Euclid's rules, but there is a construction using an angletrisector
which you can find in "The Book of Numbers" that I wrote with Richard Guy.
That book also gives an angletrisector construction that uses ruler and
compasses in a manner not sanctioned by Euclid, so you can combine them to
give such a construction for the regular heptagon. The book also gives
similar constructions for the regular polygons with 13 and 17 sides (for the
regular 11gon there's a construction using an anglequinquesector, but it
was too complicated for us to put into the book).
John Conway
3. Construction of a 17sided regular polygon
The neatest construction I know is due to Richmond  I call it the
"quadruple quadrisection constriction":
1) quadrisect the perimeter of the circle, by points N,S,E,W;
2) quadrisect the radius ON by the point A;
3) quadrisect the angle OAE by the line AB;
4) quadrisect the straight angle BAC by the line AD:
N
I 
 J
C 
F
A

WGDOBHE






S
5) draw the semicircle DFE, cutting ON in F;
6) draw the semicircle GFH, centred at B;
7) cut the semicircle WNE by the perpendiculars GI and HJ to WE.
Then I and J are points of the regular heptakaidecagon on the
circle ENWS that has one vertex at E.
I first saw this in Hardy and Wright's book on The Theory
of Numbers, which is where I've just checked up on it.
H & W confirm my impression of the history. They say
that Gauss worked out the general theory in Paragraphs
335366 of his Disquisitiones, but that the first explicit
construction was given by Erchinger, for whom they refer
to Gauss' Werke, vol II, pp186187.
This "Quadruple Quadrisection" construction (my name) is due
to Richmond, who gave it in the Quarterly Journal of Math, 1893.
Of the four or five constructions I have seen, it is definitely
the nicest. If you intersect the other quadrisectors of that
straight angle with WE and treat the resulting points similarly,
you can get more vertices in the same way  but it's easier to
use your compasses to step around the circle from the ones given,
for which the constructing points are the most conveniently
situated.
John Conway
John, I discovered another nice construction by Henri Lebesgue.
Let me tell the story:
Henri Lebesgue published in 1937 the following paper:
Lebesgue, Henri: Sur une construction du polygone regulier de 17 cotes,
due a AndreMarie Ampere, d'apres des documents conserves dans les
archives de l'academie des sciences.
C. R. Acad. Sci., Paris 204(1937) 925928.
[Republished in: Enseign. Math., II. Ser. 3(1957) 3134]
Also, he is the author of the book:
Henri Lebesgue: Lecons sur les constructions geometriques au college
de France en 19401941. Paris : Gauthier  Villars, 1950
In pp. 148 49 he describes the construction of the r. heptakaidecagon
(and in p. 145 of the r. pentagon).
I haven't seen HL's paper/book, only brief descriptions of his
constructions (in the book) published in a Greek periodical.
Here is the construction of the r. heptakaidecagon:
Let (O) be a circle of center O.
Y
A_6  A_4

K




XF*D*HE*COFDGEA

B






Z
1. Draw the diameters XA perpendicular to YZ
2. Quadrisect the radius OZ by B.
3. Draw CB perpendicular to BA (C lies on OX)
4. Draw the semicircle (C, CB) intersecting XA at D, D*
5. Draw the semicircle (D, DB) intersecting XA at E,E*
6. Draw the semicircle (D*, D*B) intersecting XA at F,F*
7. Draw the semicircle of diameter AE*, intersecting OY at K
8. Draw the semicircle (F, FK) intersecting XA at G, H.
9. Draw the perpendiculars from G, H, intersecting the (O) at A_4, A_6.
Now, A:=A_1, A_4, A_6 are vertices of the r. 17gon.
(We have arc(A_4A_6) = 4Pi/17. We bisect it to find A_5, and therefore
the r.17gon's side).
It is a memorizable construction: 5 semicircles and 4 perpendiculars.
The question is: Is it a construction of AndreMarie Ampere (see paper above)
or H. Lebesque's himself ? (My source calls it as Lebesgue's.)
Antreas P. Hatzipolakis
Construction of a regular pentagon:
Let N,S,E,W be the points of a circle C with center O in the four
compass directions, and let M be the midpoint of ON.
Let E' and E" be the points where the circle with center M through E
meets the line NS.
Finally, let P' and P" be the points where the circle with center E
through E' meets C and let Q' and Q" be the points where the circle with
center E through E" meets C.
Then E, P', P", Q' and Q" form a regular pentagon.
 Floor van Lamoen