Ways to prove the fundamental theorem of algebra This seems to be a favorite question everywhere, including Princeton quals. How many ways are there?
Please give a new way in each answer, and if possible give reference. I start by giving two:


*

*Ahlfors, Complex Analysis, using Liouville's theorem.

*Courant and Robbins, What is Mathematics?, using elementary topological considerations.
I won't be choosing a best answer, because that is not the point.
 A: When you consider how polynomial $f$ of degree $n$ acts on a big circle $R$, it gives rise to a map $S^1 \to S^1$ of degree $n$. Such a map cannot be continued to a map of a disk $D \to D-\{0\}$, thus $f(D)$ contains point 0.
A: Here is the proof by Pukhlikov (1997) at 
http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mp&paperid=6&option_lang=eng
which Ilya mentioned as being only in Russian so far. What I present below is not a literal translation (as if anyone on this site cares...).
The argument will use only real variables: there is no use of complex numbers anywhere.
The goal is to show for every $n \geq 1$ that each monic polynomial of degree $n$ in ${\mathbf R}[X]$ is a product of linear and quadratic polynomials. 
This is clear for $n = 1$ and 2, so from now on let $n \geq 3$ and assume by induction 
that nonconstant polynomials of degree less than $n$ admit 
factorizations into a product of linear and quadratic polynomials. 
First, some context: we're going to make use of proper mappings.  A complex-variable proof on this page listed by Gian depends on the fact that a nonconstant one-variable complex polynomial is a proper mapping $\mathbf C \rightarrow \mathbf C$. Of course a nonconstant one-variable real polynomial is a proper mapping $\mathbf R \rightarrow \mathbf R$, but that is not the kind of proper mapping we will use.  Instead, we will use the fact (to be explained below) that multiplication of real one-variable polynomials of a fixed degree is a proper mapping on spaces of polynomials.  I suppose if you find yourself teaching a course where you want to give the students an interesting but not well-known application of the concept of a proper mapping, you could direct them to this argument.
Now let's get into the proof. It suffices to focus on monic polynomials and their monic factorizations.
For any positive integer $d$, let $P_d$ be the space of monic polynomials 
of degree $d$:
$$
x^d + a_{d-1}x^{d-1} + \cdots + a_1x + a_0.
$$
By induction, every polynomial in $P_1, \dots, P_{n-1}$ is a product of linear and quadratic polynomials.  We will show every polynomial in $P_n$ is a product of 
a polynomial in some $P_k$ and $P_{n-k}$ where $1 \leq k \leq n-1$ and therefore 
is a product of linear and quadratic polynomials. 
For $n \geq 3$ and $1 \leq k \leq n-1$, define the multiplication map 
$$\mu_k \colon P_k \times P_{n-k} \rightarrow P_n \ \ \text{ by } \ \ \mu_k(g,h) = gh.$$  Let $Z_k$ be the image of $\mu_k$ in $P_n$ and 
$$Z = \bigcup_{k=1}^{n-1} Z_k.$$
These are the monic polynomials of degree $n$ which are composite.  We want 
to show $Z = P_n$.  To achieve this we will look at topological properties of $\mu_k$.
We can identify $P_d$ with ${\mathbf R}^d$ by associating to the polynomial displayed way up above the vector $(a_{d-1},\dots,a_1,a_0)$. This makes $\mu_k \colon P_k \times P_{n-k} \rightarrow P_n$ a continuous mapping.  The key point 
is that $\mu_k$ is a proper mapping: its inverse images of compact sets are 
compact.  To explain why $\mu_k$ is proper, we will use an idea of Pushkar' to "compactify"  $\mu_k$ 
to a mapping on projective spaces. (In the journal where Pukhlikov's paper appeared, the paper by Pushkar' with his nice idea comes immediately afterwards.  Puklikov's own approach to proving $\mu_k$ is proper is more complicated and I will not be translating it!)
Let $Q_d$ be the nonzero real polynomials of degree $\leq d$  considered 
up to scaling.  There is a bijection
$Q_d \rightarrow {\mathbf P}^d({\mathbf R})$ associating to a class of polynomials 
$[a_dx^d + \cdots + a_1x + a_0]$ in $Q_d$ the point $[a_d,\dots,a_1,a_0]$. 
In this way we make $Q_d$ a compact Hausdorff space. 
The monic polynomials $P_d$, of degree $d$, embed into 
$Q_d$ in a natural way and are identified in ${\mathbf P}^d({\mathbf R})$ 
with a standard copy of ${\mathbf R}^d$. 
Define $\widehat{\mu}_k \colon Q_k \times Q_{n-k} \rightarrow Q_n$
by $\widehat{\mu}_k([g],[h]) = [gh]$. 
This is well-defined and restricts on the embedded subsets of monic polynomials to the 
mapping $\mu_k \colon P_k \times P_{n-k} \rightarrow P_n$. In natural homogeneous coordinates, $\widehat{\mu}_k$ is a polynomial mapping so 
it is continuous.  Since projective spaces are compact and Hausdorff, 
$\widehat{\mu}_k$ is a proper map.  Then, since 
$\widehat{\mu}_k^{-1}(P_n) = P_k \times P_{n-k}$,
restricting $\widehat{\mu}_k$ to $P_k \times P_{n-k}$ shows $\mu_k$ is proper.
Since proper mappings are closed mappings, 
each $Z_k$ is a closed subset of $P_n$, so $Z = Z_1 \cup \cdots \cup Z_{n-1}$ 
is closed in $P_n$.  Topologically, $P_n \cong {\mathbf R}^n$ is connected, 
so if we could show $Z$ is also open in $P_n$ then we immediately 
get $Z = P_n$ (since $Z \not= \emptyset$), which was our goal. Alas, it will not be easy to show $Z$ is open directly, but a modification of this 
idea will work.
We want to show that if a polynomial $f$ is in $Z$ then all polynomials in $P_n$ that are near
$f$ are also in $Z$.  The inverse function theorem is a natural tool to use in 
this context: supposing $f = \mu_k(g,h)$, is the Jacobian determinant of 
$\mu_k \colon P_k \times P_{n-k} \rightarrow P_n$ nonzero at $(g,h)$?
If so, then $\mu_k$ has a continuous local inverse defined in a neighborhood of $f$.
To analyze $\mu_k$ near $(g,h)$, we 
write all (nearby) points in $P_k \times P_{n-k}$ as 
$(g+u,h+v)$ where $\deg u \leq k-1$ and $\deg v \leq n-k-1$ (allowing $u = 0$ or $v = 0$ too). Then 
$$
\mu_k(g+u,h+v) = (g+u)(h+v) = gh + gv + hu + uv = f + (gv + hu) + uv.
$$
As functions of the coefficients of $u$ and $v$, the coefficients of $gv + hu$ are all linear 
and the coefficients of $uv$ are all higher degree polynomials.  
If $g$ and $h$ are relatively prime then 
every polynomial of degree less than $n$ is uniquely of the form 
$gv + hu$ where $\deg u < \deg g$ or $u = 0$ and $\deg v < \deg h$ or $v = 0$, 
while if $g$ and $h$ are not relatively prime then 
we can write $gv + hu = 0$ for some nonzero polynomials 
$u$ and $v$ where $\deg u < \deg g$ and $\deg v  < \deg h$.
Therefore the Jacobian of $\mu_k$ at $(g,h)$ is invertible if $g$ and $h$ are relatively prime 
and not otherwise.   
We conclude that if $f \in Z$ can be written somehow as a product 
of nonconstant relatively prime polynomials then a neighborhood of $f$ in $P_n$ is inside $Z$.
Every $f \in Z$ is a product of linear and quadratic polynomials, so 
$f$ can't be written as a product of nonconstant relatively prime 
polynomials precisely when it is a power of a linear or quadratic polynomial. Let $Y$ be all these "degenerate" polynomials in $P_n$:
all $(x+a)^n$ for real $a$ if $n$ is  odd and all $(x^2+bx+c)^{n/2}$ for real $b$ and $c$ if $n$ is even. (Note when $n$ is even that $(x+a)^n = (x^2 + 2ax + a^2)^{n/2}$.) We have shown $Z - Y$ is open in $P_n$.  This is weaker than our hope of 
showing $Z$ is open in $P_n$.  But we're in good shape, as long as 
we change our focus from $P_n$ to $P_n - Y$. If $n = 2$ then $Y = P_2$ and $P_2 - Y$ is empty.
For the first time we will use the fact that $n \geq 3$.  
Identifying $P_n$ with ${\mathbf R}^n$ using polynomial coefficients, 
$Y$ is either an algebraic curve ($n$ odd) or algebraic surface ($n$ even) sitting in 
${\mathbf R}^n$.  For $n \geq 3$, the complement of an algebraic curve 
or algebraic surface in ${\mathbf R}^n$ for $n \geq 3$ is path connected, and thus
connected.  
The set $Z-Y$ is nonempty since $(x-1)(x-2)\cdots(x-n)$ is in it. Since $Z$ is closed in $P_n$, $Z \cap (P_n - Y) = Z - Y$ is closed in $P_n - Y$.
The inverse function theorem tells us that 
$Z - Y$ is open in $P_n$, so it is open in $P_n - Y$.
Therefore $Z - Y$ is a nonempty open and closed subset of $P_n - Y$.
Since $P_n - Y$ is connected and $Z - Y$ is not empty, $Z - Y = P_n - Y$. 
Since $Y \subset Z$, we get $Z = P_n$ and this completes Pukhlikov's "real" proof 
of the Fundamental Theorem of Algebra. 
Mы доказывали, доказывали и наконец доказали. Ура! :)
A: There's a linear algebra proof by Harm Derksen: https://www.jstor.org/stable/3647746. You can also find the article posted here: https://math.berkeley.edu/~ribet/110/f03/derksen.pdf
A: This is one of the proofs currently on the nLab. My goal in writing it was to see how elementary I could make it, that if you squint a little it might have been a proof from the late $18^{th}$ century. I think it's pretty close; it uses the Bolzano-Weierstrass theorem, proven by Bolzano in 1817. (It's also similar in form to the answer by Timothy Gowers https://mathoverflow.net/a/16671/2926, but with more detail, suitable perhaps for a presentation to an advanced calculus class.)
Let $f\colon \mathbb{C} \to \mathbb{C}$ be a nonconstant polynomial mapping, and suppose $f$ has no zero.

*

*Let $s$ be the infimum of values ${|f(z)|}$; choose a sequence $z_1, z_2, z_3, \ldots$ such that ${|f(z_n)|} \to s$. Since $\lim_{z \to \infty} f(z) = \infty$, the sequence $z_n$ must be bounded; by the Bolzano-Weierstrass theorem it has a subsequence $z_{n_k}$ that converges to some point $z_0$. Then ${|f(z_{n_k})|}$ converges to ${|f(z_0)|}$ by continuity, and converges to $s$ as well, so ${|f(z)|}$ attains its absolute minimum $s$ at $z = z_0$. By supposition, $f(z_0) \neq 0$.


*The polynomial $f$ may be uniquely written in the form
$$f(z) = f(z_0) + g(z)(z - z_0)^n$$
where $g$ is polynomial and $g(z_0) \neq 0$. Put
$$F(z) = f(z_0) + g(z_0)(z - z_0)^n$$
and choose $\delta \gt 0$ small so that
$${|z - z_0|} = \delta \Rightarrow {|g(z) - g(z_0)|} \lt {|g(z_0)|}.$$


*$F$ maps the circle $C = \{z : {|z - z_0|} = \delta\}$ onto a circle of radius $r = {|g(z_0)|}\delta^n$ centered at $f(z_0)$. (This uses the fact that any complex number has an $n^{th}$ root; an $18^{th}$ century mathematician might have invoked Euler's formula or De Moivre's formula.) Choose $z' \in C$ so that $F(z')$ is on the line segment between the origin and $f(z_0)$ (we can always choose $\delta$ so that also $r \lt {|f(z_0)|}$). Then
$${|F(z')|} = {|f(z_0)|} - r.$$
We also have
$${|f(z') - F(z')|} = {|g(z') - g(z_0)|} {|z' - z_0|^n} \lt {|g(z_0)|} \delta^n = r$$
according to how we chose $\delta$ in 2. We conclude by observing the strict inequality
$${|f(z')|} \leq {|F(z')|} + {|f(z') - F(z')|} \lt {|f(z_0)|} - r + r = {|f(z_0)|},$$
which contradicts the fact that ${|f(z)|}$ attains an absolute minimum at $z = z_0$.
A: Re Gauss's first proof, Smale pointed out the following (discussed by Weber in the collected papers of Gauss):   In order to show that the zero sets of the real and imaginary parts of a complex polynomial intersect, Gauss  states (paraphrasing): "If a [polynomial] curve C in the plane enters a region, it must leave it.  No one to whom I have explained the meaning of this result doubts it.  I will give a proof in a later paper."  This seems to mean, for example, that no point has an open  neighborhood in the plane meeting C in a half open interval, or in a set homeomorphic to 9.  In modern terms:  (A) For every p in C the number of branches containing p is even. This is true-- but to use it Gauss would have to prove it without using FTA!  (A) follows from a vast generalization due independently to D. Sullivan and Deligne:  (A') Let p be a point in an analytic variety X over C or R, and S the boundary of a sufficiently small ball  centered at p. Then the Euler characteristic of the intersection of S and X is 0 in the complex case, and even in the real case.   So Gauss's celebrated proof has an enormous gap.
A: Two very short proofs, mostly topological, that a nonconstant polynomial map $f:{\bf C} \to \bf C$ is surjective (joint work with Robert Palais):
(1)  Complex analysis shows that  $f$ is an open map (images of open sets are open).  A standard estimate, $|f(z)|\to\infty$ as $|z|\to\infty$, implies$f$ is also a closed map (images of closed sets are closed).  Thus $f(\bf C)$ is an open, closed, nonempty subset of the connected space  $\bf C$, therefore  $ f(\bf C)=\bf C$.
The  openness of $f$ is nontrivial, but it can be replaced by elementary algebra and topology:
(2)  The set $K$ of roots of $f'$ is finite.  The inverse function theorem shows that the set $A:=f({\bf C})\setminus f(K)$ is open, with finite boundary  $A'=f(K) \setminus A$ because $f$ is closed.  Thus $A$ has closure  $\bar A = f({\bf C})$.  Since a finite set cannot disconnect the plane, $\bar A = \bf C$.
A nice feature of these proofs is that they have straightforward (but not trivial) generalizations to higher dimensions:
Theorem:  Every nonconstant, closed, holomorphic map between connected, complex n-dimensional manifolds, is surjective.
A: You can prove it using only basic facts about continuity/compactness and the same estimate which makes the winding number/fundamental group of $S^1$ proofs work: first check that if $p(z)=z^n + a_{n-1}z^{n-1} + \ldots + a_0$ is a polynomial then $|p(z)|$ tends to infinity as $|z|$ tends to infinity (this is the "leading term dominates" estimate for large $|z|$). It follows easily that $|p|$ attains a minimum value, since outside a large disc centered at $0$ the value of $|p|$ is really big, and the disc is compact, so $|p|$ attains a minimum on it. We want this minimum value to be zero, so suppose for the sake of contradiction it isn't, then we can change coordinates if necessary so that minimum is attained at $0$, and rescale $p$ so the minimum is $1$. 
Then you just have to show that if $p(z) = 1+b_kz^k + \ldots + b_n z^n$ (where $k \geq 1$) then you can make $|p|$ smaller than $1$ for some nonzero $z$. But this is just the same kind of estimate as before: the term $b_kz^k$ dominates the other terms for $z$ small, and we can easily arrange for $b_kz^k$ to be a negative real giving the required contradiction.
The proof has the advantage that it makes the theorem "obvious" once you have some notion of compactness in the plane, so you could use this proof pretty early in a course that talks about functions on $\mathbb R^n$ or $\mathbb C$. As I said before though, what makes the proof tick is the same as what makes the $\pi_1(S^1)$ proofs work, it just uses simpler techniques to get a contradiction. Unfortunately I have no idea who it's due to (which is why I explained it rather than giving a reference...)
A: I came across this article when I was pondering teaching the FTA to my multi-variable calculus class.  In the end, I didn't have time to include it.  It is nice in that it relies only on Green's theorem which we get through in the first semester.  On the other hand, it is clear that they are largely being clever at avoiding introducing new definitions or standard theorems (for instance they use Cauchy-Riemann equations for polynomials without really saying so).  I think it's nice nevertheless.
https://web.archive.org/web/20080807182256/http://www.math.binghamton.edu/paul/papers/LoyaFundThmAlg.pdf
A: There is  an alternative proof for FTA using "Fredholm operators on Hilbert spaces":
Assume that $P(z)=z^n+a_{n-1}z^{n-1}+\ldots+a_1 z+a_0$ has no root in $\mathbb{C}$. Then for  every $\epsilon$ the polynomial $Q(z)=\epsilon^nP(z/\epsilon)=z^n+\epsilon a_{n-1} z^{n-1} +\ldots+\epsilon^{n-1}a_1z+\epsilon^n a_0$ has no root in $\mathbb{C}$, too.
The space of entire  Holomorphic functions $Hol(\mathbb{C)}$ is densely  embedded in $\ell^2$ via $f(z)=\sum_{n=0}^{\infty} a_nz^n \mapsto (a_0,a_1,\ldots)$. We  substitute "$z$" in $Q(z)$ by the shift operator on $\ell^2$. Then  it turns out  that  every polynomial $Q(z) $  defines a  bounded linear operator $Q$ on $\ell^2$ which restricts to "multiplicative operator" by polynomial $Q(z)$ on $Hol(\mathbb{C})$ so the operator $Q$ keeps $Hol(\mathbb{C})$ invariant. Moreover a  non vanishing polynomial $Q(z)$ determines  an operator on $\ell^2$ which  restricts to a surjective operator on $Hol(\mathbb{C})$. 
Note that the operator $Q\in B(\ell^2)$ described above is  a  perturbation of the $n$-shift operator so $Q$ is a  fredholm operator of index $-n$. On the other hand it is  a  perturbation of the $n$-shift operator which is  an  isometry. So $Q$ satisfies $|Q(v)|>k|v|$ for  all $v \in \ell^2$ and for  some constant $k$. Then $Q$ is  an injective operator so it can not be a surjective operator  on $\ell^2$ since its index( $-n$ )is nonzero. On the other hand,  since  the restriction of $Q$ to a dense subspace of $\ell^2$ is surjective and  $Q$ satisfies $|Q(v)>k|v|$, then $Q$ must be  a  surjective operator on $\ell^2$, a contradiction.
Added: This proof is based on the following  note in arxiv however this arxived paper was not written well.(Full of typos, grammar problem, mistakes in english writing).
https://arxiv.org/abs/math/0509113v1
A: Here's an extract of my post to sci.math.research from 2001. The proof definitely
uses a "sledgehammer method", but perhaps it has some pedagogical  value. I have no
doubt that other people may have come up with similar arguments.

Sketch: It suffices to check that any complex monic polynomial has 
a root. Any such polynomial is the characteristic polynomial of 
some matrix (one can use the so called companion matrix). 
Thus one is reduced to showing that an $n\times n$ complex matrix $A$ has 
an eigenvalue or equivalently an eigenvector. $A$ may be assumed 
to be invertible, since otherwise $0$ is an eigenvalue. Then 
$A$ acts on complex projective space $P = \mathbb{C}\mathbb{P}^{n-1}$ by sending the 
span of $v$ to the span of $Av$. An eigenvector corresponds to 
a fixed point under this action. Since the general linear group 
of $\mathbb{C}$ is connected, $A$ can be connected by a path to the identity I 
(this can be done explicitly by writing $A$ as a product of elementary 
matrices and deforming these to $I$ in the obvious way). It follows 
that the $A$ is homotopic to $I$, and therefore its Lefschetz number on 
$P$ coincides with the Euler characteristic of $P$ which is nonzero. 
Therefore, $A$ has a fixed point on $P$. 
Added: I should probably have pointed that the conclusion follows from the Lefschetz fixed point theorem, which was the sledgehammer that I was alluding to.
A: This proof uses the open mapping theorem, which I found in Narasimhan's book.
Theorem: Let $f\in C^\omega(\mathbb{C})$, and suppose that $|f(z)|\to\infty$ as $|z|\to\infty$.
Then $f(\mathbb{C})=\mathbb{C}$.
Proof:
Obviously $f$ is not constant, and so the open mapping theorem implies that $f(\mathbb{C})$ is open. Let us show that $f(\mathbb{C})$ is also closed.
Suppose that $f(z_k)\to w\in\mathbb{C}$ as $k\to\infty$.
Then $\{z_k\}$ is bounded, so taking a subsequence if necessary, there is $z\in\mathbb{C}$ such that $z_k\to z$.
By continuity $f(z_k)\to f(z)$, concluding that $w=f(z)$.
A: There seems to be a new elementary proof using only Bolzano–Weierstraß and an inequality:

*

*Oswaldo Rio Branco de Oliveira, The fundamental theorem of algebra: A most elementary proof, American Mathematical Monthly 119:9 (2012) 753-758, doi:10.4169/amer.math.monthly.119.09.753, arXiv:1109.1459
A: Another probabilistic proof:
Pascu, Mihai N.
A probabilistic proof of the fundamental theorem of algebra. (English summary)
Proc. Amer. Math. Soc. 133 (2005), no. 6, 1707–1711 (electronic).
Summary: "We use Lévy's theorem on invariance of planar Brownian motion under conformal maps and the support theorem for Brownian motion to show that the range of a non-constant polynomial of a complex variable consists of the whole complex plane. In particular, we obtain a probabilistic proof of the fundamental theorem of algebra.'' 
It is different from the probabilistic proof already listed among answers to this question, which uses martingale convergence theorem.
A: I don't have it on hand, but Ronald Solomon's Abstract Algebra has an interesting proof using symmetric polynomials and induction on the 2-adic valuation of the degree.
A: In this post the OP wonders how one can prove the FTA using the hairy ball theorem, after having read a book of Ian Stewart containing an allusion to such a proof. The answer I gave could be added to the current list of proofs as well. There is no doubt that this proof is known. However, it does not seem to be mentioned in the other items of this list.
The main idea of proof is already present when one wants to show that a polynomial $f\in\mathbf C[z]$ of degree $2$ has a zero using the hairy ball theorem. Suppose that it does not have any zeros. Then the holomorphic vector field
$$
f\tfrac{\partial}{\partial z}
$$
is a nonvanishing vector field on the Riemann sphere $S^2$. This is because $f$ has a pole of order $2$ at infinity, while $\partial/\partial z$ has a zero of order $2$ at infinity. The contradiction comes from the hairy ball theorem that states that such vector fields cannot exist. The general case of a polynomial $f$ of even degree $2d$ can be proved by arguing that the vector field
$$
\sqrt[d]{f\cdot\left(\tfrac{\partial}{\partial z}\right)^{\otimes d}}
$$
is well defined, and nonvanishing on $S^2$ if $f$ does not have any zeros in $\mathbf C$. See here for more details.
A: Gauss's first proof contained an enormous gap, since he presumed facts equivalent to the Jordan curve theorem to be true. Jordan curve theorem was proven a century later.
There is a modification on Gauss's first proof that uses only basic real analysis concepts (continuity and least upper bound principle for real numbers) on the real and complex parts of a complex polynomial (which are bivariate polynomials in either $(r,\theta)$ or $(x,y)$: On Gauss's first proof of the fundamental theorem of algebra
Sorry for the self promotion, I am an author in the proof.
A: Here is a nice proof that was posted on the ALGTOP list recently. See also the ensuing discussion.

An algebraic extension of $\mathbb{C}$ is a unital division algebra over $\mathbb{C}$, say
  of dimension $n$, so induces 
        $$\mathbb{CP}^{n-1} \times \mathbb{CP}^{n-1} \to \mathbb{CP}^{n-1}$$
  satisfying 
        $$ y \mapsto 1 \otimes y + y \otimes 1 $$ 
  in second integral cohomology.  Since $y^n = 0$, we must have $n=1$.

A: Not quite an answer, but relevant:
Eilenberg and Niven proved that every "polynomial" in the quaternions has a root (provided
it has only one term of highest degree).  The trick is familiar:  they show that such a polynomial is homotopic to $q\mapsto q^n$, which induces a map of degree $n$ on the one-point compactification  of $\mathbb{H}$, namely $S^4$.
A: A recent and very important contribution to the literature on the fundamental theorem of algebra is Joe Shipman's article "Improving the Fundamental Theorem of Algebra," Math. Intelligencer 29 (2007), 9-14, doi:10.1007/BF02986170. Here is one of his results: A field with the property that every polynomial whose degree is a prime number has a root is algebraically closed.  This result is sharp in the sense that if any prime is omitted then the conclusion is false.
Shipman's paper should go a long way towards addressing Andrew L's question of whether there is a "purely algebraic proof" of the FTA.  The above result of Shipman's shows that we can limit the topology/analysis to proving that every polynomial over $\mathbb{C}$ of prime degree has a root; the rest is pure algebra.  If you wanted to try to limit the use of topology or analysis even further, then this part of the proof is where you should focus your attention.
A: Two (or three) more complex analysis approaches, the first is "essentially the same" as the proof in Alfors I think, but the second is different (I'm afraid I don't have a reference, but I can type up the full proofs if you want):
Let p be a polynomial and n be its degree.


*

*apply the residue theorem to $1/[zp(z)]$. If $p$ has no roots, then this function is analytic except at $z=0$, where it has a simple pole of non-zero residue. But $1/[zp(z)]$ is bounded, so integrating it along a circular contour centred at the origin gives something inversely proportional to the length of this contour ie this integral can be made as small as possible, which contradicts the residue at $z=0$ being non-zero.

*a variant of the above: If p has no roots, then Cauchy's integral formula implies $$\int_{|z|=r}\frac{dz}{zp(z)}=\frac{2\pi i}{p(0)}\ne0.$$ Now let $r\to\infty$: The integral on the left vanishes in the limit, and we have a contradiction. See Anton R. Schep: A simple complex analysis and an advanced calculus proof of the fundamental theorem of algebra, Amer. Math. Monthly 116 (2009) 67–68.

*by Rouche's theorem, $p(z)$ and $z^n$ have the same number of roots inside a large circular contour centred at the origin, and this number is n.
A: I have collected 15 proofs with different approaches, including all the proofs suggested here so far. They are available at
https://github.com/andreaferretti/math-notes/blob/master/TFA.pdf
Unfortunately they are in italian. I hope someone is able to read them.
A: At the risk of being highly downvoted, I can't resist reposting my comment
to Andrew L's answer (or rather, question) below:
is there a purely algebraic proof that for any non constant $P$ in $\mathbb{Q}[i][X]$
and $\epsilon>0$ in $\mathbb{Q}$, there is $q$ in $\mathbb{Q}[i]$ s.t. $|P(q)|<\epsilon$?
I think the statement above is purely algebraic, but I have to admit
I'm a bit uncertain as to where the boundary between algebra and analysis
falls.
A: Maybe I should have posted this as a comment to Gian Maria Dall'Ara very nice proof, because is a mere variation.
He uses the lemma : Any open proper map to a locally compact space surjects the connected components it reaches. Now any non-constant polynomial corestricted to its regular value locus is as in the lemma, so it is surjective.
Here is a "constructive proof" of the D'Alembert-Gauss theorem. Fix a degree $n > 0.$
Consider the $M_n$ the affine space of monic polynomials of degree $n$ and the proper map $\mathbb C^n \to M_n$, mapping a tuple $(z_1, \ldots , z_n)$ to $\Pi (X-z_i).$ Its critical values locus is non-disconnecting because it is a complex (singular) hypersurface : it is a polynomial image of the arrangement of hyperplanes { $z_i = z_j$}. 
The map is therefore surjective.
A: Let $p$ be a complex polynomial of degree $n$.  


*

*By analytic continuation arguments applied to any branch of $p^{-1}$, it can be shown that any level curve $\Lambda=\{z:|p(z)|=\epsilon\}$ of $p$ which does not contain a zero of $p'$ is a Jordan curve.

*Since $p'$ has at most $n-1$ zeros, we can find some point $z$ such that the level curve $\Lambda_z$ of $p$ which contains $z$ does not contain a critical point.

*Let $D$ denote the bounded face of $\Lambda_z$.  By the maximum modulus theorem applied to $f$ on $D$, $f$ has a zero in $D$.
$\Box$
A: In Hatcher's book http://pi.math.cornell.edu/~hatcher/AT/ATpage.html Theorem 1.8 he deduces the fundamental theorem as a corollary of the fact that the fundamental group of the circle is isomorphic to the integers.
A: Pukhlikov has a  proof using only real numbers (the page in English, full text in Russian) of the fact that indecomposable elements in $\mathbb R[x]$ have degree 1 or 2 as is part of the 1997 issue of Russian journal "Математическое Просвещение"  which dedicated 50 pages of that issue to proving the main theorem of algebra by different methods. 
In particular, the article by Tikhomirov and Uspenski (pdf, Russian) in that volume contains 10 proofs:


*

*topological, by considering a circle of big radius;

*algebro-geometric, using $\mathbb C\mathbb P^1$;

*algebro-geometric, using general facts about Riemann surfaces;

*complex-analytic, by referring to number of zeroes = number of poles or Stokes theorem;

*using topology to prove that holomorphic maps between compact surfaces are constant or surjectivet;

*similarly, but using inverse theorem from calculus;

*finding a minimum of $|p(z)|$;

*applying the Liouville's theorem to $1/p(z)$;

*applying Lefschetz theorem to $\mathbb C\mathbb P^n$ to prove that every linear operator over $\mathbb C$ has eigenvector;

*using Galois theory + simple facts about $\mathbb C$ to show that $\mathbb C$ has no algebraic extensions;


as well as extensive historical notes.
Though I don't know whether a translation exists, I think that this collection of articles deserves it and I'm sure the authors will be happy to give their permission to republish. A translation could be done as a project for an undergraduate student with knowledge of the language.
A: Gauss's first proof goes more or less like this. Let $p(z)$ be a polynomial of degree $n$ and complex coefficients. Write $p(x+iy) = a(x,y) + ib(x,y)$, where $a,b$ have real coefficients. The crucial observation is that the branches of $a=0$ and $b=0$ as real curves interlace at infinity (as can be seen from the degree $n$ terms). Also, real algebraic plane curves don't just stop somewhere in the affine plane, so a branch of $a=0$ must be connected to another branch of $a=0$. Now, in between them, there is a branch of $b=0$ which connects to another branch of $b=0$. If the connections alternate, they have to meet and we get a common zero of $a$ and $b$, which gives a complex zero of $p$. If they don't alternate, find a branch of $a=0$ in between the two connecting branches of $b=0$ and repeat. 
I think this proof really needs the Jordan curve theorem to be fully justified, which is a bit of an anachronism.
A: As in one of the previous posts, consider the projective space $CP^n$ of nonzero all polynomials
$$ c_nT^n + c_{n-1} T^{n-1} + \cdots + c_1 T + c_0 $$
considered up to nonzero scalar multiple.  We'll show directly that any such polynomial admits a factorization into linear factors.
Consider the map $\phi: CP^1 \times \cdots \times CP^1 \to CP^n$ given by
$$ ([\alpha_1:\beta_1],\dots,[\alpha_n:\beta_n]) \mapsto \prod_{i=1}^n (\alpha_i T - \beta_i) $$
In other words, this map sends a set of roots to the polynomial which has precisely those roots.  It suffices for us to show that $\phi$ is surjective. 
If the points $[\alpha_i:\beta_i]$ are distinct, it is easy to check that the differential $d\phi$ is nonzero.  Hence the polynomial $T^n - 1$ (for example) is a regular value of $\phi$ with exactly $n!$ preimages (here we've used the fact that polynomials factor uniquely into irreducibles).  Thus the map $\phi$ has positive degree.
It is a fact that any map of positive degree between compact connected complex manifolds of the same dimension is surjective.  (Proof: Since any such map is orientation preserving, the number of preimages of any regular value must be exactly equal to the degree - not just up to multiplicity.  Hence the image contains the set of regular values, which is dense by Sard's theorem.  But the image is also closed since it is the image of a compact set, hence the map is surjective.)  
We conclude that $\phi$ is surjective.  In other words, every polynomial of degree $n$ has a factorization into linear factors.
A: There is a proof using clutching functions over the sphere and the first Chern class. It is quite similar to the fundamental group proof of FTA. The trick is a polynomial without zeroes allows one to construct an isomorphism between a vector bundle with first Chern class $\deg d$ and a vector bundle with first Chern class $0$ using the polynomial restricted to circles concentric with the origin as clutching functions.
The details: From a polynomial $p: \mathbb{C} \to \mathbb{C}$, $p(z) = \sum_{j=0}^d a_j z^j$ we can construct a continuous family $p_t: \mathbb{C} \times[0,1] \to \mathbb{C}$ of polynomials such that $p_1(z)(z) = a_d z^d$ and $p_0(z) = a_0$. If $p$ has no zeroes, one can construct $p_t$ in such a way that $p_t$ has no zeroes on the unit circle.
This means that for a fixed $t \in [0,1]$ we can use $p_t$ restricted to the circle as a clutching function for $S^2$. Since $p_t$ is continuous family, this gives a vector bundle $E$ over $S^2 \times [0,1]$. It is a standard fact in the theory of vector bundles that $E$ restricted to $S^2 \times \{0\}$ isomorphic to $S^2 \times\{0\}$. But our construction allows us to read off that the former has first chern class $d$, while the latter has first chern class $0$. Hence $d = 0$ and $p$ must be constant.
A: In elementary proofs like the one elucidated in Kevin McGerthy's answer, there is usually a step where for a given $n\in \mathbb{N}_0$ and given $\alpha\in \mathbb{C}_0$ a $z\in \mathbb{C}$ has to be found so that $Re(\alpha z^n)<0$. People usually browse very quickly over this part and implicitly use something like Euler's or De Moivre's formula or use a topological method. This step can however be accomplished in a more 'direct' way. Indeed, for this task it suffices to show that $\forall n \in \mathbb{N}_0:\,\forall \beta \in \{1,i,-1,-i\}$ the polynomial $z^n-\beta$ has a root. This can be shown using the Cartesian formula for the square root
$$(x+yi)^{\frac{1}{2}}=\left(\frac{x+(x^2+y^2)^{\frac{1}{2}}}{2}\right)^{\frac{1}{2}}+\text{sgn}(y)\left(\frac{-x+(x^2+y^2)^{\frac{1}{2}}}{2}\right)^{\frac{1}{2}}i$$
and an induction argument (on $n$). As I suspect that many people find such a remark 'pedantic', I'll waste no more words on it :)
A: Volume I of Diffusions, Markov processes and martingales by Rogers and Williams has a probabilistic proof of the fundamental theorem (Prop. 19.5, page 41).
A: Here is another short proof, showing that no finite extension of $\mathbb{C}$ exists. If $A$ were such an extension of dimension $d$,
then the projective space $\mathbb{P} A \cong \mathbb{CP}^{d-1}$
were a compact commutative Lie group, hence a torus. 
There are plenty of ways showing that $\mathbb{CP}^{m}$ is not a torus (if $m>0$). Take your favorite one, and the proof is complete.
A: Also The Fundamental Theorem of Algebra: A Visual Approach by Velleman.
A: I add another proof separately since it is rather different.
It is based on the observation that an irreducible polynomial of degree $n$ on a field $F$ gives rise to a field structure on $F^n$, compatible with the vector addition (just quotient out polynomials with coefficients in $F$ by the maximal ideal generated by the irreducible).
Then the FTA is a consequence of the non-existence of real commutative division algebras in dimension greater than $2$. 
This last assertion follows from the observation that in such a $R^n$ you can define an $exp$ which gives an epimorphism $R^n\rightarrow R^n$ \ $0$, and hence a homeo $S^j \times R^k\cong R^n$ \ $0$, which is forbidden by a fundamental group computation (this was in Andrea Ferretti's notes).
In fact you can use this argument to prove that any real irreducible polynomial has degree $1$ or $2$.
A: A proof using dynamical systems:
If $p$ is a non-constant polynomial without roots then $f = \text{Re}(\frac{1}{p})$ is a bounded harmonic function which goes to zero at infinity.  Consider the gradient flow for $f$.  This flow is area preserving because $f$ is harmonic.  Also, the value of $f$ is strictly increasing along the orbit of any non-singular point.  
Consider the bounded set where $f > \epsilon > 0$.  This set is invariant for the flow and by Poincarè's recurrence theorem almost all orbits in it are recurrent.  However because of the monotonicity of the values of $f$ along orbits this is impossible unless all these orbits are singular.  Hence the derivative of $f$ on the set where it is positive is zero.  The same argument applied to $-f$ shows that the derivative of $f$ is zero on the set where $f$ is negative.  Hence $f$ is constant.
The same argument applied to the imaginary part of the reciprocal of $p$ implies that $p$ is constant.
A: Here is the proof of the equivalent statement "Every complex non-constant polynomial $p$ is surjective".
1) Let $C$ be the finite set of critical points , i.e. $p'(z)=0$ for all $z\in C$. $C$ is finite by elementary algebra.
2) Remove $p(C)$ from  the codomain and call the resulting open set $B$ and remove from the domain its inverse image $p^{-1}\left( p (C) \right)$, and call the resulting open set $A$. Note that the inverse image is again finite.
3) Now you get an open map from $A$ to $B$, which is also closed, because any polynomial is proper (inverse images of compact sets are compact). But $B$ is connected and so $p$ is surjective.  
I like this proof because you can try it for real polynomials and it breaks down at step 3) because if you remove a single point from the line you disconnect it, while you can remove a finite set from a plane leaving it connected.
A: This is not a serious answer, but one can "prove" the fundamental theorem of algebra by applying the spectral theorem to the matrix
$$ A := \begin{pmatrix} 0 & 1 & 0 & \ldots & 0 \\\ 0 & 0 & 1 & \ldots & 0 \\\ \vdots & \vdots & \vdots & \ddots & \vdots \\\ -a_0 & -a_1 & -a_2 & \ldots & -a_{n-1} \end{pmatrix} $$
to locate an eigenvalue $\lambda$, which is then a root of the monic polynomial $z^n + a_{n-1} z^{n-1} + \ldots + a_0$.
Of course, this argument is usually circular, because most of the standard proofs of the spectral theorem for matrices requires the fundamental theorem of algebra (either by explicitly citing that theorem, or implicitly, by borrowing one of the proofs given here, e.g. by applying Liouville's theorem to the resolvent $(A-zI)^{-1}$) in the first place...
However, one could imagine a weird proof of the spectral theorem that somehow avoids the fundamental theorem and would thus give a non-circular proof of that theorem.  I thought about proceeding by showing that the set of diagonalisable matrices is a generic subset of the set of all matrices, but I realised that in order to have enough algebraic geometry to talk about "generic", I need to know the ambient field is algebraically closed, which of course is precisely the fundamental theorem of algebra.  Deducing the spectral theorem for matrices from the spectral theory of more general objects, such as elements of a C^* algebra, doesn't work either, for much the same reason.
Perhaps it is best to view the above arguments not as proofs of the fundamental theorem of algebra, but rather as "consistency checks" that show that this result is compatible with the basic theory of other mathematical subjects, such as linear algebra and algebraic geometry.
A: When I was a freshman, I was asked to prove the fundamental theorem of algebra on the final exam for multivariable calculus (I'm completely serious: I think the problem just stated the FTA and asked us to give a proof.)
I didn't succeed, but what I was supposed to do (I think) was apply the Gauss-Bonnet Theorem.  One version of this proof appeared recently:
Yet another application of the Gauss-Bonnet Theorem for the sphere
J. M. Almira and A. Romero
Source: Bull. Belg. Math. Soc. Simon Stevin Volume 14, Number 2 (2007), 341-342; projecteuclid. 
In this paper the authors use the version of Gauss-Bonnet that relates the Gaussian curvature to the Euler characteristic.  
I guess there's another version of this in which one instead uses the version of Gauss-Bonnet saying that the Euler characteristic is the same as the sum of the indices of any vector field (sometimes this theorem is attributed to Poincaré).
The vector field to consider is just $z \mapsto 1/p(z)$, which is well-defined for non-constant polynomials $p(z) = z^n + a_{n-1} z^{n-1} + \cdots + a_0$ without roots, because it vanishes at infinity.  The index at infinity for this vector field is the degree of $p$.  So if $p$ is a non-constant polynomial without roots, we'd need to have deg$(p) = \chi(S^2) = 2$.  Since degree 2 polynomials have roots (the quadratic formula!), this completes the proof.
A: See the book The fundamental theorem of algebra by Fine and Rosenberger.
A: Here is a translation into English of a second "real" proof from the journal Ilya mentioned in his answer.  This proof is due to Petya Pushkar', in the 1997 paper titled О некоторых топологических доказательствах основной теоремы алгебры; this is on mathnet.ru here.
The proof is based on the notion of the degree of a map.  Recall that for a smooth proper mapping of oriented manifolds, its degree is defined by picking a regular value and adding up the signs of the determinants of the differential of the mapping at the points in the inverse image.  That the degree is well-defined is rather complicated to prove, but it explains the following topological fact.
Fact:  Let $M^n$ and $N^n$ be smooth connected oriented manifolds and
$f \colon M^n \rightarrow N^n$ be a smooth proper mapping of degree
not equal to zero.  Then $f$ is surjective.
To prove the Fundamental Theorem of Algebra in a "real" version, we will focus on polynomials of even degree (any of odd degree have a real root). We will show that
any real polynomial of degree $2n$ can be factored into a product of $n$ polynomials
of the second degree.
We identify each monic polynomial $x^d + a_{d-1}x^{d-1} + \cdots + a_1x + a_0$ with the point $(a_{d-1},\dots,a_0)$ in $\mathbf R^d$.  We will be particularly interested in the space of monic quadratic polynomials $x^2 + ax + b$, which are identified with the plane $\mathbf R^2$.  Consider the multiplication mapping
$$
u \colon (\mathbf R^2)^n \rightarrow \mathbf R^{2n} \ \ \text{ where} \ \ \ (f_1,f_2,\dots,f_n) \mapsto  f_1f_2\cdots f_n.
$$
Proving the Fundamental Theorem of Algebra amounts to showing that $u$ is surjective.
First we show $u$ is proper.
For any $d \geq 1$, identify the nonzero polynomials of degree at most $d$, considered up to scaling by nonzero real numbers, with $\mathbf P^d(\mathbf R)$ by $[a_dx^d + a_{d-1}x^{d-1} +\cdots + a_0]  \mapsto 
[a_d,a_{d-1},\dots,a_0]$. (The polynomials of exact degree $d$, after being scaled to be monic, are a copy of $\mathbf R^d$ in $\mathbf P^d(\mathbf R)$.) Consider the multiplication mapping
$$
\widehat{u} \colon (\mathbf P^2(\mathbf R))^n \rightarrow \mathbf P^{2n}(\mathbf R) \ \ \text{ where} \ \ \ ([f_1],[f_2],\dots,[f_n]) \mapsto  [f_1f_2\cdots f_n].
$$
The mapping $\widehat{u}$ is proper since it is defined on a compact manifold and is continuous.
The mapping $\widehat{u}$ is a natural "compactification" of the mapping $u$. The space
$(\mathbf P^2(\mathbf R))^n$ can be written as the union of $(\mathbf R^{2})^n$ and an "infinitely distant part" $B_1$ ($n$-tuples of polynomials of degree at most 2 where at least one polynomial has degree less than 2), while $\mathbf P^{2n}(\mathbf R)$ can be written as the union of $\mathbf R^{2n}$ and an "infinitely distant part" $B_2$ (polynomials of degree less than $2n$).  From this point of view, $\widehat{u}$ on $(\mathbf R^2)^n$ agrees with $u$ and, clearly, $\widehat{u}^{-1}(B_2) = B_1$. Therefore the map $u$ is proper.
Next we show the degree of $u$ is equal to $n!$.
Orient the space of monic polynomials of degree 2 (we denote this space as $\mathbf R^2$) arbitrarily and give $(\mathbf R^2)^n$ the product orientation (as a product of oriented manifolds). As an exercise, show
the polynomial $p(x) = \prod_{i=1}^n (x^2+i)$ is a regular value of the mapping $u$. (Hint:
This polynomial is a product of distinct monic irreducibles.  Now use the description of the regular values of the multiplication mappings $\mu_k$ in Pukhlikov's proof of the Fundamental Theorem of Algebra, which is written in a separate answer on this page.)
The polynomial $p(x)$ has $n!$ inverse images under $u$:  all ordered $n$-tuples
with coordinates $x^2+i$ for $i = 1,\dots,n$. Let's prove that these points
all contribute the same sign to the degree.
The mapping $u$ is invariant under permutations of its arguments, and
any such permutation preserves orientation (exercise).  Therefore the
sign of the determinant of the differential at all the inverse images is the same, which shows $u$ has degree $n!$.  By the topological fact at the start, $u$ is surjective, so all monic real polynomials of degree $2n$ are a product of monic quadratic real polynomials.
A: Perhaps it could be of interest for you to know that there exists purely geometric proofs of this result. Concretely, it can be shown that, if the FTA fails then there exists a plane Riemannian metric over the Sphere S^2. Of course, this produces a contradiction since the sphere is not flat. This proof can be located at the very recent paper by J M Almira and A Romero: "Some Riemannian Geometric proofs of the fundamental theorem of algebra", which is available at: http://www.mathem.pub.ro/dgds/v14/D14-al.pdf
J. M. Almira
A: Here is a standard algebraic proof. It suffices to show that if $L/\mathbb{C}$ is a finite extension, then $L=\mathbb{C}$. By passing to a normal closure we assume that $L/\mathbb{R}$ is Galois with Galois group $G$. Let $H$ be the Sylow-2 subgroup of $G$ and $M=L^H$.
By the Fundamental Theorem of Galois Theory, $M/\mathbb{R}$ has odd degree. Let $\alpha\in M$ and $f(x)$ be its minimal polynomial. Then $f(x)$ has odd degree and by the Intermediate Value Theorem, a real root. As $f(x)$ is irreducible, it must have degree one. Then $\alpha\in\mathbb{R}$ and $M=\mathbb{R}$. So $G=H$ is a 2-group. Then $G_1:=Gal(L/\mathbb{C})$ is a 2-group as well. 
Assuming that $G_1$ is not trivial, there must exist a degree 2 subextension $K$ of $\mathbb{C}$. But every quadratic complex polynomial has a root (by the quadratic formula), so we have a contradiction.
A: I'm partial to Milnor's proof in Topology from the Differentiable Viewpoint, a slightly simpler variant of the "every complex non-constant polynomial $p$ is surjective" proof given above, published somewhat earlier (1965). In brief:
Definition: Let $f: M \to N$, $M,N \subset \mathbb{R}^n$, $M$ compact, then, for each regular value $y \in N$,
$$\#f^{-1}(y) = \text{number of points in the inverse image of $y$}.$$
Lemma: $\#f^{-1}$ is locally constant on the set of regular values.
Proof of lemma: Since $f$ is a diffeomorphism in a neighborhood of each $x_i \in f^{-1}(y)$, we can choose pairwise disjoint neighborhoods $U_i$ for the $x_i$, let $V_i = f(U_i)$, and then
$$\#f^{-1}(V_1 \cap \cdots \cap V_k - f(M - U_1 - \cdots - U_k)) = \{\#f^{-1}(y)\}.$$
Proof of the F.T.A.: Using stereographic projection, we can consider the polynomial as a smooth map $f: S^2 \to S^2$. Since $f$ has only a finite number of critical points, the set of regular values is connected; the locally constant $\#f^{-1}$ is therefore constant on this set. As $\#f^{-1}$ cannot be zero for all regular values of $f$, it must be zero for none. Thus $f$ is surjective, and the polynomial has a root.
A: Gersten and Stallings gave a proof using free groups:
On Gauss's first proof of the fundamental theorem of algebra, Proc. Amer. Math. Soc. 103 (1988), 331-332
of course giving all of the credit to Gauss.
A: Thanks to Tim Chow for citing me. Technically, you don't need to show every polynomial of prime degree in F[x] has a root, you just need to show that there is a field G such that every polynomial of odd prime degree in G[x] has a root and every element or its additive inverse has a square root; then G[i] will be algebraically closed. Even more interesting, to show that all polynomials of degree d have a root, all you need is that all polynomials of degree p have a root for those p which divide d, plus the existence of any sufficiently large degree d' such that all polynomials of degree d' have a root (an explicit algorithm for how large d' must be is easily derivable from my proof).
Of course, this is not a proof of the Fundamental Theorem of Algebra, what I did was identify the pure algebraic core of the requirement that a field be algebraically closed. To show that the complex numbers are algebraically closed, you still need some way of showing that real polynomials of odd prime degree have roots, which depends on the Intermediate Value Theorem or some other analytical or topological argument in all the proofs I know.
A: Here is a variant of d'Alembert's argument using the minimum of $|p(z)|$. It has the advantage that it proves more generally the Gelfand-Mazur theorem (usually proved by complex analysis): Any Banach field $K$ over $\mathbb C$ is $\mathbb C$ itself. Indeed, this gives the fundamental theorem of algebra by applying it to any putative finite extension of $\mathbb C$.
Let $x\in K$. The map
$$
\mathbb C\to \mathbb R_{\geq 0}: z\mapsto |x-z|
$$
is continuous and gets large for $|z|$ large, so attains its minimum at some $z\in \mathbb C$. Replacing $x$ by $x-z$, we get $(\ast)$: for all $w\in \mathbb C$, one has $|x-w|\geq |x|$. We claim that then $x=0$. If not, we can rescale $x$ by a real number so that $|x|=2$. Now take some large $n$ and consider the identity
$$ \prod_{i=0}^{n-1} (x-\zeta_n^i) = x^n-1.$$
Each factor on the left is of norm at least $|x|=2$ (by $(\ast)$), so the left-hand side is of norm at least $|x-1|2^{n-1}\geq 2^n$. The right-hand side is bounded in norm by $2^n+1$. Taking the limit as $n\to \infty$, we see that $|x-1|=2$. Applying this argument to $x-1$ in place of $x$, this gives the absurd $2=|x|=|x-1|=|x-2|=\ldots=|x-5|\geq 5-|x|=3$.
Edit: This proof is due to Ostrowski, see Section 7 in "Über einige Lösungen der Funktionalgleichung $\varphi(x) \varphi(y) = \varphi(xy)$", 1916. (h/t Mohan Ramachandran!)
The proof uses the existence of infinitely many roots of unity; but $\zeta_4=i$ and if $\zeta_{2^n} = a_n + b_n i$ then $\zeta_{2^{n+1}} = a_{n+1} + b_{n+1} i$ where $a_{n+1}=\sqrt{\frac{1+a_n}2}$ and $b_{n+1}=\sqrt{\frac{1-a_n}2}$. (But one can also rewrite the proof so as to only use the existence of $\zeta_8=\frac{1+i}{\sqrt{2}}$.)
A: Here's another complex analysis proof that I heard about for the first time under a week ago (because it was set as a question on a course I am teaching for). Pick a circle large enough for the modulus of p(z) to be greater than |p(0)| everywhere in that circle. Inside that circle take a point w where the modulus of p is minimal (which obviously you can do by compactness). There are many ways of proving that p(w)=0. One can use the minimum modulus theorem (that any point of minimum modulus not on the boundary must be a zero), the open mapping theorem, the local mapping theorem, or an elementary bare-hands argument.
A: There is one short proof on wikipedia, that shows the statement that any endomorphism $A$ of a finite-dimensional vector space $V$ of positive dimension has an eigenvalue. Look at the resolvent function $R_A:z \mapsto (A-z)^{-1}$. Outside the disc of radius $\|A\|$, it can be developped into a geometric series. Use this geometric series to compute the integral of $R_A$ around a big circle; the result is $2 \pi i \cdot id_V$. On the other hand, if the spectrum were empty, then the resolvent were holomorphic and by Cauchy's theorem, the integral is zero. This is a contradiction if $dim (V) >0$.
To derive the FTA from the existence of eigenvalues (without using determinants), let $p(z)$ be a normed polynomial of degree $n$ and look at the vector space $V:= \mathbb{C}[z]/(p(z))$ and let $A:V \to V$ be the multiplication by $z$. $dim (V)=n$ is easy to see (division with remainder) and clearly $p(A)=0$. Take a nonzero $v \in V$ with $Av=\lambda v$. Then $0=p(A) v = p(\lambda) v$ shows that $\lambda$ is a zero of $p$.
A: I believe the following proof had not appeared before, though it is motivated by this previous answer   and a comment by Benjamin Steinberg to this answer.

Consider a field extension $F$ of $\mathbb{R}$ of finite degree $d>1$.
We'll see that $d=2$, which forces $F\simeq \mathbb{C}$.
Note that the map $\alpha(x)=x^2$ is an endomorphism of the multiplicative group $F^\times$. The differential of $\alpha$ at $x$ is the multiplication by $2x$ operator, which is invertible, so the image of $\alpha$ is open in $F^\times$. 
Since $F^\times$ is connected (it is homeomorphic to $\mathbb{R}^d-\{0\}$ and $d>1$), and a connected topological group has no proper open subgroup (open subgroups are closed), we conclude that $\alpha$ is onto.
Since $\mathbb{R}^\times=\alpha^{-1}(\mathbb{R}^\times_+)$ we get that $\alpha$ induces a continuous isomorphism
$F^\times/\mathbb{R}^\times\simeq F^\times/\mathbb{R}^\times_+$.
This yields a homeomorphism $\mathbb{P}^{d-1}(\mathbb{R}) \simeq S^{d-1}$. There are several ways to see that there is no such a homeomorphism unless $d=2$ (the most standard one is by using the simply-connectedness of the sphere, but using an ad-hoc argument would make the above proof available for younger students), thus I leave the end game to the reader.
A: I'm surprised that no-one's mentioned the proof using Roueche's theorem:
Given $f,g$ holomorphic and $C$ a closed contour if $|g(z)|< |f(z)|$ on $C$ then $f$ and $f+g$ have the same number of zeros (counting multiplicity) in the interior of $C$.  There's an easy proof of this using the Cauchy integral formula.
If Let $g(z) = a_{n-1} z^{n-1} + \cdots + a_0$, and $f(z) = z^n$. If $R$ is sufficiently big then $|g(z)|<|f(z)|$ on the circle of radius $R$ with the center at 0.  Thus $p(z) := z^n + g(z)$ has $n$ zeros inside that circle.
[As a side note, when I was taught this by Lipman Bers, he picturesquely referred to it as the "dog on the leash theorem" -- it's essentially a winding number argument]
