If I remember correctly(from what I read), Gauss proved that
We can factor a rational multiple of $x^{17} - 1$ as $(x-1)(P(x)^2 + aP(x) + b)$
Where $P(x)$ is an $8^{th}$ degree polynomial with rational coefficients.
This $P(x)$ could in-turn be represented as a quadratic $Q(x)^2 + cQ(x) + d$, where this $Q(x)$ is an $4^{th}$ degree polynomial.
That $Q(x)$ itself was a quadratic of a quadratic!
The actual method of geometrically constructing the polygon came a few years later.
In more modern terms, basically (again, if I remember the terms correctly), the splitting field of $x^{17}-1$ lies in a tower of quadratic extensions, starting from $\mathbb{Q}$.