Proof. First of all, note that a primitive
$n$ root of unity is a constructible number if and only if
$\displaystyle \cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$ is a constructible number. See the entry on
roots of unity for more details. Therefore,
without loss of generality, only the constructibility of the
number $\displaystyle \cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$ will be considered.
Sufficiency: If a regular $n$ gon is constructible, then so is the angle whose vertex is the center of the polygon and whose rays pass through adjacent vertices of the polygon. The measure of this angle is $\displaystyle \frac{2\pi}{n}$
By the theorem on constructible angles, $\displaystyle \sin\left(\frac{2\pi}{n}\right)$ and $\displaystyle \cos\left(\frac{2\pi}{n}\right)$ are constructible numbers. Note that $i$ is also a constructible number. Thus, $\displaystyle \cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$ is a constructible number.
Necessity: If $\displaystyle \omega=\cos\left(\frac{2\pi}{n}\right)+i\sin\left(\frac{2\pi}{n}\right)$ is a constructible number, then so is $\omega^m$ for any integer $m$
On the complex plane, for every integer $m$ with $0\le m<n$ construct the point corresponding to $\omega^m$ Use line segments to connect the points corresponding to $\omega^m$ and $\omega^{m+1}$ for every integer $m$ with $0\le m<n$ (Note that $\omega^0=1=\omega^n$ ) This forms a regular $n$ gon. 
